选择排序

选择排序慢在哪？它没有"提前结束"的机会：哪怕数组本来就有序，每一趟也得把未排序区从头扫到尾才能确认最小值。比较次数固定是 n²/2，省不掉。

第 i 趟开始前，下标 0..i-1 已经是整个数组里最小的 i 个数、且排好序。所以第 i 趟只要在剩下的未排序区找最小值，换到下标 i，前缀就又长一格——这个不变量是选择排序成立的根。

第 1 趟 · 假设 5 最小：第 1 趟从下标 0 开始。先假设当前位 5 就是未排序区最小值（min 记在下标 0），再往右逐个比对。

比 5 和 2 · 2 更小：拿下标 1 的 2 和当前最小 5 比：2 小于 5，更新 min 到下标 1。

比 4 和 2 · 不更新：再看下标 2 的 4：4 大于 2，不是更小，min 不动。这就是一次"比较后发现不需要更新"的负例——大多数比较其实都走这条分支。

比 1 和 2 · 1 更小：下标 3 的 1 小于 2，更新 min 到下标 3。

比 3 和 1 · 不更新：最后下标 4 的 3 大于 1，min 仍是下标 3。整趟扫完，确认未排序区最小值是 1。

第 1 趟 · 把 1 换到最前：把下标 0 的 5 和最小值 1 交换。1 归位，已排序前缀 = [1]。注意整趟只交换了这一次——这正是选择排序相比冒泡的特点：交换次数最少。

第 2 趟 · 在 [2,4,5,3] 找最小：第 2 趟从下标 1 开始，未排序区 [2,4,5,3] 扫一遍：最小是 2，正好已经在下标 1。

第 2 趟 · 自己换自己：最小值就在原位，无需真正移动（代码里是和自己交换）。2 归位，前缀扩到 [1,2]。

第 3 趟 · 最小 3 换上来：未排序区 [4,5,3] 扫一遍最小是 3（在下标 4），和下标 2 交换。3 归位，前缀 [1,2,3]。

第 4 趟 · 4 换到位：未排序区 [5,4] 最小是 4，和下标 3 交换。4 归位。

收尾 · 最后一个自动到位：只剩一个 5 时它必然已是最大、自动落在末位，所以外层只需跑到倒数第二个。整个数组 [1,2,3,4,5] 有序。

选择排序的思路是"为每个空位选对的数"，冒泡是"让对的数自己浮上去"。同为 O(n²)，但选择的交换更省。它和堆排序同源——堆排是用堆在 O(log n) 内更快地选出最大。