选择排序
选择排序每轮扫描未排序部分，找出最小值，再把它交换到未排序部分的开头。最好、平均和最坏时间复杂度都是 O(n²)，额外空间为 O(1)，交换次数最多为 n - 1。标准交换版本不稳定。
可以把它想成按身高排队：走过剩余队伍，记下最矮的人，扫描结束后才让这个人到前面。一次扫描，最多一次交换。比较很多，移动很少。
选择排序如何工作
外层循环的 i 从 0 到 n - 2，位置 i 是本轮要填的位置。每轮先设 min_idx = i，再让 j 从 i + 1 扫描到 n - 1。当 arr[j] < arr[min_idx] 时，更新 min_idx = j。
扫描结束后，只有 min_idx != i 才交换 arr[min_idx] 和 arr[i]。如果最小值已经位于本轮开头，就跳过交换。
第 i 轮结束后，前 i + 1 个位置存放最小的 i + 1 个值，且已经有序。选择排序扩展左侧的有序前缀；冒泡排序扩展右侧的有序后缀。
选择排序逐步演示
默认输入为 [25, 49, 25, 64, 12, 37, 15]。两个 25 用来展示稳定性问题。
第 1 轮，i = 0，min_idx 指向第一个 25。向右扫描：49 更大，第二个 25 与当前最小值相等，严格的 < 条件不成立；64 更大；下标 4 的 12 成为最小值，后面的 37 和 15 都没有替代它。交换 arr[0] 与 arr[4]，得到 [12, 49, 25, 64, 25, 37, 15]。
12 已就位。但原来位于下标 0 的 25 被移到下标 4，越过了原来位于下标 2 的 25。两个相等元素的顺序在第一轮就反转了，这说明选择排序不稳定。
第 2 轮，i = 1，最小值从 49 开始。扫描到 25 时更新记录，后面的另一个 25 不会替换它；扫描到下标 6 的 15 后再次更新。交换后得到 [12, 15, 25, 64, 25, 37, 49]。
第 3 轮，未排序部分的最小值就是下标 2 的 25，没有更小的值，min_idx 不变，本轮不交换。
第 4 轮把另一个 25 放到下标 3，得到 [12, 15, 25, 25, 64, 37, 49]。第 5 轮选择 37，得到 [12, 15, 25, 25, 37, 64, 49]。第 6 轮选择 49，结果为 [12, 15, 25, 25, 37, 49, 64]。
动画中的 j 扫描未排序部分，min 指向目前找到的最小值。每轮扫描结束后最多交换一次；最小值已经在目标位置时，直接确认该位置。
时间与空间复杂度
| 情况 | 时间复杂度 |
|---|---|
| 最好 | O(n²) |
| 平均 | O(n²) |
| 最坏 | O(n²) |
算法原地排序，额外空间为 O(1)。每轮的交换都有 min_idx != i 检查，因此不计无效的自交换。
长度为 n 的数组总要比较 n(n - 1) / 2 次，交换却最多只有 n - 1 次。当移动元素比比较元素昂贵时，这种取舍可能有用，例如记录较大或写入较慢的场景。
选择排序不会利用已有顺序。即使输入已经有序，每轮仍要扫描整个剩余部分，所以最好时间复杂度也是 O(n²)。
边界情况
- 空数组或一个元素：外层循环不执行。
- 已有序：每轮最小值都位于
i，没有交换，但比较次数不变。 - 所有值相等：严格的
<条件从不成立，min_idx不移动，也没有交换。 - 存在重复值：长距离交换可能改变相等元素的顺序。例如
[2a, 2b, 1]排序后成为[1, 2b, 2a]。需要保持原顺序时，应选择稳定排序。
常见错误
- 忘记每轮重置
min_idx = i：上一轮的最小值位置会影响本轮，搜索范围随之出错。 - 始终与
arr[i]比较：应与arr[min_idx]比较，才能保留扫描期间发现的最小值。 - 无条件交换：缺少
min_idx != i检查会执行自交换，增加无效操作。 - 误以为使用
<就能保证稳定：问题来自长距离交换。需要稳定性时，可以考虑插入排序、稳定的归并排序或 Timsort。