学习顺序主线第 04 / 22 课 · 阶段 2

为什么现在学:接着冒泡理解另一种有序边界,为后面的局部维护做准备。

前置知识 冒泡排序
返回算法课程
排序基础

插入排序Insertion Sort

像整理手中的扑克牌,把新元素插入已经有序的前缀。

30 分钟前置:数组 · 冒泡排序

学完这一课,你应该能做到

  • 保存待插入值,准确追踪空位
  • 说明有序前缀不等于最终就位
  • 用移动次数解释近乎有序输入的优势

01先从一个问题出发

手里已经排好几张牌,新摸一张,不必把所有牌重新排列。

一个具体的例子

[4,2,3,1];表中重复项是赋值移动时的真实中间状态。

已有序的部分值得保留

数组第一个元素单独看天然有序。从第二个元素开始,假定左侧前缀已排序,把当前值插进合适位置。这里没有必要重新排列整个前缀,只需为一个新值腾出空位。

设前缀 [2,4],新值 key=3。4 比 3 大,先把 4 右移;2 不大于 3,可以停下来,把 3 放在 2 后面。这个动作与数组基础课中的中间插入相同,只是不会改变数组总长度。

key 为什么必须独立保存

执行 a[j+1]=a[j] 时,原来 a[i] 的位置很快就会被前一个元素覆盖。保存 key 后,数组里暂时出现重复值没关系:缺少的那个值仍保存在变量中,最后会被写回。

有序前缀以后还可能整体右移。例如 [2,4] 已排好,再读到 1 时,两项都得给 1 腾位置。所以不要把它理解成冒泡的最终就位后缀。保持条件必须精确,才知道下一轮能复用什么。

02最直接的办法,为什么慢?

每加入一个元素,就重新冒泡排序整个前缀。

暴力 · O(n³)

反复排序忽略了已有序的部分。

03一步步,推导出优化思路

1

保留已经有序的前缀

前缀已排序时,新元素只需要寻找一个插入点。

2

保存新值,向右腾出空位

先保存 key,把所有大于 key 的前缀元素右移。

3

把新值插入,扩展前缀

空位出现后写入 key,有序前缀扩展一个元素。

贯穿算法的不变量

第 i 轮开始前,a[0:i] 已有序。

拿一个小输入,逐步手算

[4,2,3,1];表中重复项是赋值移动时的真实中间状态。

i / key动作数组已保存的值
1 / 24 右移,再放入 2[2,4,3,1]前缀 [2,4] 有序
2 / 34 从下标 1 移到 2[2,4,4,1]3 保存在 key
2 / 32≤3,写入下标 1[2,3,4,1]前缀 [2,3,4] 有序
3 / 14、3、2 依次右移[2,2,3,4]1 保存在 key
3 / 1j=−1,写入 j+1=0[1,2,3,4]全部有序

不要在移动过程中拿整个数组判断元素是否丢失;需要同时看 key。完成一轮后,数组才恢复完整的元素集合。

有序前缀如何扩展

  1. i=1 时,长度为 1 的前缀天然有序。
  2. 从前缀末尾开始,把所有严格大于 key 的值右移;它们的相对顺序不变。停止位置左边的值都不大于 key,右边的值都大于 key。
  3. 把 key 填进空位后,前缀长度增加 1 且仍有序。处理到最后一项,整个数组就成为有序前缀。

04让每一步,都看得见

试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。

Insertion Sort交互演示
STEP 01 / 19
4
0
2
1
3
2
1
3
当前处理已处理 / 已确定未处理
01

从左到右观察数组。橙色表示当前比较,绿色表示已确定的位置。

insertion_sort.py参考实现 · 当前第 2 行
正在载入代码编辑器…

动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。

代码里的每个关键决定

key, j = a[i], i - 1
先保存本轮新元素,j 指向有序前缀的最后一项。不要在移动后才读取 a[i] 当作 key。
while j >= 0 and a[j] > key:
先检查下标合法,再比较大小。严格大于才移动,相等时停止,以保持相等元素的原次序。
a[j + 1] = key
停止时 j 指向最后一个不大于 key 的元素;真正空位是 j+1。若 j=−1,就填到下标 0。

05复杂度,来自具体的工作量

时间复杂度
O(n2)O(n^2)

逆序输入下每个元素最多向前走 i 步,总和为 O(n²)。近乎有序时很快;有序输入为 O(n)。

辅助空间
O(1)O(1)

原地版本仅保存 key 和下标。教学函数复制输入,额外复制占 O(n)。

拖动 n,看看增长速度

把工作量具体数出来

逆序的 n 项在第 i 轮要移动 i 项,总计 1+2+…+(n−1),最坏 O(n²)。

有序输入每轮只比较前一项,无需移动,总共 O(n)。近乎有序输入需要消除的逆序较少,因此常常比最坏情况快很多。

原地实现只需 key 与下标,辅助空间 O(1);本课函数为保留输入而复制数组,实际额外分配 O(n)。

06看到什么,应该想到它?

这些特征值得停下来想一想:

关键词只是线索,继续检查适用条件

07这些细节,容易踩坑

01

保存 key

移动前必须保存原值,否则会被右移覆盖。

02

有序前缀不是最终位置

未来更小元素仍可能插到前面。

用反例检查前提

相等也移动会损害稳定性

把值相同但有身份的两项记作 2A、2B。如果条件改成 ≥,后来读到 2B 会把 2A 推向右边,顺序就变成 2B、2A。

怎样修正:只移动严格大于 key 的项。稳定排序要求相同键的相对次序保留,不是只要求数值非递减。

08把想法带进真实题目

合上答案,自己推一次

解释空位在哪里

数组 [1,4,5,2] 处理 i=3 时,依次移动哪些值?j 最终是多少?key 应写入哪个下标?

需要一点提示

遇到 1≤2 时停止,j 此时还指向 1。

查看完整推导与答案
  1. 保存 key=2,先移动 5,再移动 4。
  2. j 从 2 减到 0,发现 a[0]=1≤2 后退出。
  3. 写入 a[j+1]=a[1],结果为 [1,2,4,5]。

完成上面的手算练习,再把思路迁移到这些题目。

09不用背模板,回答这几个问题

01最适合插入排序的输入?

02右移前为什么保存 key?

03稳定性需要什么条件?

你已经走完了这次推导。

能用自己的话解释复杂度和不变量,再标记为掌握。

把知识连起来

继续阅读

本课例子与推导为本站编写。需要另一种表述或进一步学习时,可对照这些公开课程与文档:

MIT 6.006 · 算法讲义Princeton Algorithms · 课程资料

能独立完成本课练习,再标记掌握。也可以直接用上面的链接继续学习。