排序算法系列 03：选择排序——每轮挑个最小的出来
选择排序和冒泡排序一样简单，但思路完全不同。
冒泡是一路交换把大的往后推，选择排序更"淡定"——先扫一遍找到最小的，然后一步到位放到正确位置。交换次数少了，但比较次数一个没省。
核心思想
每一轮从还没排好的部分里，找到最小的那个，跟当前位置的元素换一下。
就像你从一堆牌里挑最小的放第一个，再从剩下的里挑最小的放第二个……依此类推。
用 [5, 2, 9, 1, 7] 举例：
- 第一轮：扫一遍，最小的是
1，跟第一个位置的5交换 →1, 2, 9, 5, 7 - 第二轮：从第二个位置开始找，最小的是
2，已经在正确位置 → 不动 - 第三轮：从第三个位置开始找，最小的是
5，跟9交换 →1, 2, 5, 9, 7 - 第四轮：从第四个位置开始找，最小的是
7，跟9交换 →1, 2, 5, 7, 9
搞定。
走一遍过程
再用 [5, 2, 9, 1, 7] 详细跑一次：
第一轮：
未排序区域：5, 2, 9, 1, 7
找到最小值：1（在下标 3）
交换下标 0 和下标 3
结果：1, 2, 9, 5, 7
第二轮：
未排序区域：2, 9, 5, 7
最小值：2，已经在位
结果：1, 2, 9, 5, 7
第三轮：
未排序区域：9, 5, 7
最小值：5（在下标 3）
交换下标 2 和下标 3
结果：1, 2, 5, 9, 7
第四轮：
未排序区域：9, 7
最小值：7（在下标 4）
交换下标 3 和下标 4
结果：1, 2, 5, 7, 9
代码实现
function selectionSort(arr) {
const result = [...arr];
for (let i = 0; i < result.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < result.length; j++) {
if (result[j] < result[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
const temp = result[i];
result[i] = result[minIndex];
result[minIndex] = temp;
}
}
return result;
}
console.log(selectionSort([5, 2, 9, 1, 7]));
// [1, 2, 5, 7, 9]
关键变量是 minIndex——内层循环跑完之后，它记录的就是当前未排序区域里最小元素的位置。然后只需要一次交换。
和冒泡的区别
乍一看都是 O(n²)，都是两层循环，但干活方式不一样：
- 冒泡：一边扫一边换，走一趟可能换好多次
- 选择：先扫一遍只记录位置，最后换一次
所以选择排序的交换次数最多 n - 1 次，而冒泡最坏情况下交换次数是 n(n-1)/2 次。如果交换操作本身代价很高（比如交换的是很大的对象），选择排序会占点便宜。
但比较次数两者差不多，都是 O(n²) 级别。
复杂度
| 情况 | 时间复杂度 |
|---|---|
| 最好 | O(n²) |
| 平均 | O(n²) |
| 最坏 | O(n²) |
注意：即使数组已经有序，选择排序也得老老实实跑完所有比较。它没有冒泡那个"提前结束"的优化空间。所以最好情况也是 O(n²)。
空间复杂度 O(1)。
稳定性：不稳定。一次长距离交换就可能打乱相等元素的相对顺序。
举个例子：[5a, 5b, 3]，第一轮找到最小值 3，跟 5a 交换后变成 [3, 5b, 5a]——原来 5a 在 5b 前面，现在反过来了。
说点实话
选择排序的定位和冒泡差不多：学习用。
它的价值在于让你理解"每轮选最值"这个思想。后面学堆排序的时候你会发现，堆排序本质上也是在"选最值"，只不过用堆结构把"找最值"这一步从 O(n) 优化到了 O(log n)。
所以选择排序虽然简单，但它是通向堆排序的思想桥梁。
下一篇来看插入排序——同样是 O(n²) 家族，但在特定场景下表现出人意料地好。
系列导航