选择排序的原理是什么？为什么它不稳定？

简化版

选择排序每一轮从未排序部分选出最小的元素，放到已排序部分的末尾（和未排序部分的第一个交换）。n-1 轮后完成。时间不管数据如何都是 O(n²)（即使已有序也要全扫）、空间 O(1)、不稳定（交换时可能把相等元素的相对顺序打乱）。它的交换次数很少（每轮最多一次），是它唯一的小优点。

详细版

void selectionSort(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {    // 在 [i, n) 里找最小值的下标
            if (a[j] < a[minIdx]) minIdx = j;
        }
        if (minIdx != i) {                    // 把最小值交换到位置 i
            int t = a[i]; a[i] = a[minIdx]; a[minIdx] = t;
        }
    }
}

每轮在未排序区 [i, n) 找到最小元素的下标 minIdx，与 a[i] 交换。
交换后 [0, i] 是已排好的部分。
比较次数固定 n(n-1)/2 次，与数据是否有序无关，所以最好=最坏=平均都是 O(n²)。
交换次数最多 n-1 次（每轮至多一次），这是它比冒泡「省交换」的地方。

完整版教学

一、核心思想：每轮选一个最小值归位

选择排序的逻辑非常直白：把数组分成「已排序」和「未排序」两部分，每一轮从未排序部分挑出最小的，放到已排序部分的末尾。就像整理扑克牌，每次从手里剩下的牌里抽出最小的一张，依次排好。n-1 轮后，未排序部分只剩一个（自然是最大的），排序完成。

二、逐步走一遍

初始: [5, 3, 8, 4, 2]  (| 分隔已排序/未排序)
轮1: 未排序[5,3,8,4,2] 最小是2 → 和 a[0]=5 交换 → [2 | 3,8,4,5]
轮2: 未排序[3,8,4,5]   最小是3 → 已在位  → [2,3 | 8,4,5]
轮3: 未排序[8,4,5]     最小是4 → 和 a[2]=8 交换 → [2,3,4 | 8,5]
轮4: 未排序[8,5]       最小是5 → 和 a[3]=8 交换 → [2,3,4,5 | 8]
完成: [2,3,4,5,8]

三、为什么最好情况也是 O(n²)

这是选择排序和冒泡、插入的关键区别。选择排序每一轮都必须把未排序部分完整扫一遍才能确定最小值——哪怕数组已经完全有序，它也不知道，还是要扫。所以比较次数恒定为 n(n-1)/2，没有「提前退出」的可能，最好、最坏、平均全是 O(n²)。相比之下冒泡和插入在近乎有序时能到 O(n)。

四、为什么选择排序不稳定（重点）

选择排序不稳定，原因在于「交换」这一步可能跨越相等元素，打乱它们的相对顺序。经典反例：

数组: [5a, 5b, 3]   （5a、5b 值相等，a 在前）
轮1: 未排序最小是 3 → 和 a[0]=5a 交换 → [3, 5b, 5a]
现在 5b 跑到了 5a 前面 —— 相等元素的相对顺序被打乱了！

一次远距离交换就把 5a 甩到了 5b 后面，所以选择排序不稳定。（可以改成「不交换、而是把最小值插入、其余后移」来实现稳定选择排序，但那样就失去了「省交换」的优点，一般不这么做。）

五、复杂度与特点

时间：最好=最坏=平均都是 O(n²)（比较次数固定）。
空间 O(1)：原地。
交换次数少：每轮最多 1 次，总共 ≤ n-1 次。当「交换成本很高」（比如元素很大、移动昂贵）而「比较成本低」时，选择排序的少交换是个优点。
不稳定。

六、和冒泡、插入的对比

三个 O(n²) 简单排序里：

比较次数：选择固定 n²/2；冒泡、插入在有序时可减少。
交换/移动次数：选择最少（≤n-1 次交换）；冒泡最多；插入是移动。
稳定性：冒泡、插入稳定，选择不稳定。
自适应性（近乎有序时变快）：插入最好、冒泡（带优化）次之，选择完全没有。

所以选择排序的定位是「交换少但不自适应、不稳定」，实际很少用。

七、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：第 i 轮开始时 [0,i) 已是最终最小前缀，本轮从后缀选最小值放到 i。

对应的状态推进是：扫描未排序区记录最小下标，轮末最多交换一次。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。比较次数恒为 n(n-1)/2，因此最好、平均、最坏均 O(n²)。

带数字走一遍：[3a,3b,1] 首轮把 1 与 3a 交换，3a 越过 3b，说明不稳定。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	仅在数据很小且写操作比比较昂贵时可能有意义
时间复杂度	最好/平均/最坏 O(n²)
额外空间	O(1)
关键边界	最小值下标初始化为 i；远距离交换会改变相等键相对顺序
替代方案	近乎有序数据优先插入排序

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“仅在数据很小且写操作比比较昂贵时可能有意义”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写最好/平均/最坏 O(n²) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“比较次数恒为 n(n-1)/2，因此最好、平均、最坏均 O(n²)”。
误区：重复值和边界值不会改变代码。 最小值下标初始化为 i；远距离交换会改变相等键相对顺序。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“第 i 轮开始时 [0,i) 已是最终最小前缀，本轮从后缀选最小值放到 i”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“[3a,3b,1] 首轮把 1 与 3a 交换，3a 越过 3b，说明不稳定”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“近乎有序数据优先插入排序”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

选择排序：每轮从未排序部分选最小值，与未排序区首元素交换归位，n-1 轮。最好=最坏=平均都是 O(n²)（每轮必须全扫找最小、无法提前退出）、空间 O(1)、不稳定（远距离交换会跨越相等元素，如 [5a,5b,3] 排后 5b 跑到 5a 前）。唯一优点是交换次数少（≤n-1 次）。不自适应、不稳定，实际很少用。

简化版

详细版