选择排序（Selection Sort）是最基础的排序算法之一，虽然效率不高，但逻辑简单、易于实现，非常适合排序入门学习。本文将详解其原理、执行过程、Python代码、复杂度分析等内容。
📌一、算法原理
核心思想：
每一轮从待排序区间中找出最小（或最大）元素，放到已排序区间的末尾，重复进行。
流程如下：
每次遍历剩余数组，找到当前最小值的下标。
与当前轮的起始位置交换。
重复 n 次后，整个数组即为有序。
🧪二、Python 代码实现（选择排序）
以下是我写的代码：
def select_sort(arr):n = len(arr)for i in range(n):min_index = i# 在 [i+1, n) 中找最小元素的下标for j in range(i + 1, n):if arr[j] < arr[min_index]:min_index = j# 交换当前位置和最小值的位置arr[i], arr[min_index] = arr[min_index], arr[i]return arr# 示例数组
arr = [29, 10, 14, 37, 13]
print('select_sorted:', select_sort(arr))
输出示例：
select_sorted: [10, 13, 14, 29, 37]
🔍三、代码过程详解
以 [29, 10, 14, 37, 13] 为例：
第1轮：
起始索引 i = 0，最小值为 10（索引1）
交换 29 和 10 →
[10, 29, 14, 37, 13]
第2轮：
i = 1，最小值为 13（索引4）
交换 29 和 13 →
[10, 13, 14, 37, 29]
第3轮：
i = 2，最小值为 14 → 无需交换
第4轮：
i = 3，最小值为 29（索引4）
交换 37 和 29 →
[10, 13, 14, 29, 37]
⏱️四、时间复杂度分析
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好情况 | O(n²) | 仍需 n 次选择和比较 |
| 最坏情况 | O(n²) | 与最好一样，无法提前终止 |
| 平均情况 | O(n²) | 所有情况均需两层遍历 |
空间复杂度：O(1)，原地排序。
稳定性：不稳定，例如
[5, 5, 3]会交换两个 5 的相对位置。
🎯五、选择排序 vs 冒泡排序
| 特性 | 选择排序 | 冒泡排序 |
|---|---|---|
| 是否稳定 | ❌ 不稳定 | ✅ 稳定 |
| 比较次数 | 固定 O(n²) | 最好 O(n) |
| 交换次数 | 最少（O(n)） | 最多（O(n²)） |
| 适用场景 | 交换代价大时 | 对稳定性要求高时 |
🔧六、选择排序的改进方向
尽管选择排序简单易懂，但其性能在大数据量场景中较差。改进方向包括：
双向选择排序（每轮找最大和最小）
使用堆结构替代线性扫描
实际开发中，建议使用快排或内置排序
🧠七、总结
选择排序的思路是“先选最小，再放前面”，虽然效率不高，但非常适合初学者理解排序机制。掌握此算法是理解更复杂排序（如堆排序）的基础。