专题进阶 · 排序算法推荐总顺序 · 第 28 / 148 课

区分比较与交换成本,用有序前缀证明选择排序,并识别不稳定性。

先学会这些,再进入本课 数组 冒泡排序
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 排序算法

选择排序Selection Sort

每轮选未排序区间的最小值放到前面;比较 O(n²),交换 O(n),通常不稳定。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

区分比较与交换成本,用有序前缀证明选择排序,并识别不稳定性。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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为什么这个方法成立

  1. 初始有序前缀为空。
  2. 每轮将剩余元素中的最小者放在边界,前缀仍有序且不大于后缀所有元素。
  3. 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 · 复现与理解

[1,2,3,4] 比较几次?

需要一点提示

后缀长度逐次减一。

查看解析与答案

3+2+1=6 次,交换 0 次。

练习 2 · 边界与辨析

怎样保持相同键次序?

需要一点提示

不要让元素跨过相等键交换。

查看解析与答案

找到最小元素后取出,将 i 到 best−1 右移一位,再放到 i;可稳定但写入更多。

练习 3 · 变式与迁移

只要最小的 k 个值是否适合完整排序?

需要一点提示

思考完成前 k 轮的代价。

查看解析与答案

可只做 k 轮,成本 O(nk);k 较大时可考虑堆、快速选择或完整 O(n log n) 排序。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 排序

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。