选择排序 Selection Sort
选择排序 · 交换次数最少
什么是选择排序
选择排序的思路像「每次挑最小的先站队」：在未排序区间里扫一遍、找出最小值，把它换到未排序区的最前面，这个位置就此定下来。然后在剩下的区间里再找次小的……前缀有序区从左往右一格格长大。它和冒泡都是 O(n²)，但有个鲜明特点——每一轮最多只交换一次，总交换次数只有 n-1 次。
它怎么做
第 i 轮：从下标 i 往右扫，用 minIndex 记住当前最小值的位置（扫描时被记录的最小值高亮），扫完把 a[i] 和 a[minIndex] 交换。点「下一步」看 [7, 6, 5, 10, 9, 8, 4, 3, 2, 1]：注意整轮都在「找」、只有轮末那一下才「换」——比较很多、交换极省。
第 1 轮：先假定位置 0 最小
1function selectionSort(a: number[]): number[] {
2 const n = a.length;
3 for (let i = 0; i < n - 1; i++) {
4 let minIdx = i;
5 for (let j = i + 1; j < n; j++) {
6 if (a[j] < a[minIdx]) {
7 minIdx = j;
8 }
9 }
10 if (minIdx !== i) {
11 [a[i], a[minIdx]] = [a[minIdx], a[i]];
12 }
13 }
14 return a;
15}
n10
i0
j0
minIdx0
a[j]7
a[minIdx]7
swapCount0
sortedUpTo0
1 / 131
复杂度与适用
时间恒为 O(n²)（无论数据是否有序都要扫满）、常数额外空间、不稳定（跨越式交换会打乱相等元素的相对次序）。它的比较次数和冒泡一样多，但交换/写入次数最少——当「写」的代价远高于「比较」（如元素很大、或写入闪存有损耗）时，这个特性有实际意义。
选择 vs 冒泡：比较次数相同，但选择每轮只换一次、冒泡边扫边换。
选择的高效版：堆排序——用二叉堆在 O(log n) 内「选出最大值」，把 O(n²) 降到 O(n log n)。
选择的高效版：堆排序——用二叉堆在 O(log n) 内「选出最大值」，把 O(n²) 降到 O(n log n)。
当你觉得「每次都线性扫描找最值太慢」，就该看堆排序怎么用堆结构加速这个「选择」动作——它正是选择排序的进化终点。