选择排序在做什么
选择排序的思路非常直观：就像打扑克牌时，你每次从桌上剩下的牌里挑出最小的一张，放到手里已排好序列的末尾。重复这个过程，直到所有牌都排好。换句话说，每一轮从未排序部分选出最小的元素，放到已排序部分的末尾。
一轮的流程：选最小、交换归位
每一轮只做两件事：找最小和交换归位。首先，在未排序区间（初始为整个数组）中扫描，记录最小元素的位置。然后，将该最小元素与未排序区间的第一个元素交换。这样，最小元素就放到了已排序部分的末尾，未排序区间缩小一个位置。重复 n-1 轮，数组即有序。
为什么是 O(n²)
| 操作 | 次数 |
|---|---|
| 比较 | 第一轮 n-1 次，第二轮 n-2 次，……，最后一轮 1 次，总和约 n²/2 |
| 交换 | 每轮最多 1 次，总共 n-1 次 |
比较次数是等差数列求和，为 O(n²)；交换次数是 O(n)。因此总时间复杂度由比较主导，为 O(n²)。无论数据是否有序，比较次数固定，所以最好、最坏、平均都是 O(n²)。
和冒泡排序的对比（交换次数）
| 特性 | 选择排序 | 冒泡排序 |
|---|---|---|
| 交换次数 | 最多 n-1 次 | 最多 n(n-1)/2 次 |
| 比较次数 | O(n²) | O(n²) |
选择排序每轮只做一次交换，而冒泡排序每轮可能多次交换。因此当交换成本很高时（如移动大对象），选择排序更优。但两者比较次数相同，都是 O(n²)。
稳定性与适用场景
稳定性：选择排序是不稳定的。例如数组 [5a, 5b, 1]，第一轮选出 1 与 5a 交换，结果 [1, 5b, 5a]，两个 5 的相对顺序改变了。因此它不适合需要保持相等元素原顺序的场景。
适用场景：由于 O(n²) 的时间复杂度，选择排序只适合小规模数据（如 n < 1000）。当交换成本远高于比较成本时，它比冒泡排序更合适。另外，它的思路简单，适合教学入门。