01先把问题说具体
给 [4,2,3,1] 排序。冒泡不停交换,能否每轮只做一次交换?
02一步步得到方法
先找位置,再移动元素
设 i 左边已经排好序。在 a[i:] 中扫描最小值的位置 best,扫描结束才交换 a[i] 与 a[best]。选择排序减少的是交换次数,并没有省掉寻找最小值所需的比较。
与冒泡比较:冒泡让大数通过相邻交换向右移动,选择排序直接把最小数放到左端。两者都建立逐轮扩大的确定区域,但中间数组状态和写入次数不同。
把扫描中的保证说清楚
当内层走到 j 时,best 指向 a[i:j+1] 的最小值。遇到更小值才更新 best;扫描完整个后缀后,best 就是这一轮应放在 i 的元素。若已经在 i,则可以跳过交换。
直接跨位置交换会越过其他相等键,因此一般不稳定。稳定版本可以取出最小值再整体右移区间,但会增加写操作,改变这个版本的优势。
比较次数与交换次数是两笔账
第1轮比较 n−1 次,第2轮 n−2 次,总比较为 n(n−1)/2,与输入原来是否有序无关。每轮至多一次交换,所以交换仅 O(n),这与冒泡的移动行为不同。
若记录还带有相同键的先后身份,一次远距离交换可能把同键记录的相对顺序颠倒。因此标准选择排序不稳定,不能因为只交换最小项就推断稳定。
03把一个小例子完全算清楚
[4,2,3,1] 升序排序。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| i=0 | 最小值 1 在下标 3;交换得 [1,2,3,4] | 位置 0 确定 |
| i=1 | 扫描 [2,3,4],best=1 | 无需交换,仍要比较 |
| i=2 | 比较 3、4,best=2 | 最后位置自动正确 |
窄屏可左右滑动表格,阅读完整计算与理由。
第一次交换已使整个数组有序,但普通选择排序仍会扫描余下后缀。
04为什么这个方法成立
- 初始有序前缀为空。
- 每轮将剩余元素中的最小者放在边界,前缀仍有序且不大于后缀所有元素。
- n−1 轮后只剩一个元素,整个数组有序。
05把推导翻译成代码
Python · 可独立运行的教学实现
def selection_sort(values):
a = list(values)
for i in range(len(a) - 1):
best = i
for j in range(i + 1, len(a)):
if a[j] < a[best]:
best = j
if best != i:
a[i], a[best] = a[best], a[i]
return a逐个理解关键决定
best = i- 每轮重置候选;不能沿用上一轮的位置。
best != i- 避免无意义自交换,但不影响比较次数。
06时间、空间与实现范围
比较次数始终为 n(n−1)/2,最好和最坏均为 Θ(n²)。最多 n−1 次非自交换。
核心可原地运行,只用 O(1) 辅助变量;本函数为保留输入而复制,额外空间 O(n)。
07改变条件,检查哪里会出错
交换少就一定更快
比较仍是平方级,只在写入昂贵等特殊条件下可能有相对优势。
用严格小于就一定稳定
[2a,2b,1] 第一轮交换为 [1,2b,2a],相同键次序已反转。
把少交换当作总复杂度更低
渐近时间仍由二次比较次数主导;只有特定写入成本模型下,少交换才可能特别有价值。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
[1,2,3,4] 比较几次?
需要一点提示
后缀长度逐次减一。
查看解析与答案
3+2+1=6 次,交换 0 次。
怎样保持相同键次序?
需要一点提示
不要让元素跨过相等键交换。
查看解析与答案
找到最小元素后取出,将 i 到 best−1 右移一位,再放到 i;可稳定但写入更多。
只要最小的 k 个值是否适合完整排序?
需要一点提示
思考完成前 k 轮的代价。
查看解析与答案
可只做 k 轮,成本 O(nk);k 较大时可考虑堆、快速选择或完整 O(n log n) 排序。