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最直接的办法,为什么慢?
每加入一个元素,就重新冒泡排序整个前缀。
反复排序忽略了已有序的部分。
03一步步,推导出优化思路
保留已经有序的前缀
前缀已排序时,新元素只需要寻找一个插入点。
保存新值,向右腾出空位
先保存 key,把所有大于 key 的前缀元素右移。
把新值插入,扩展前缀
空位出现后写入 key,有序前缀扩展一个元素。
第 i 轮开始前,a[0:i] 已有序。
拿一个小输入,逐步手算
[4,2,3,1];表中重复项是赋值移动时的真实中间状态。
| i / key | 动作 | 数组 | 已保存的值 |
|---|---|---|---|
| 1 / 2 | 4 右移,再放入 2 | [2,4,3,1] | 前缀 [2,4] 有序 |
| 2 / 3 | 4 从下标 1 移到 2 | [2,4,4,1] | 3 保存在 key |
| 2 / 3 | 2≤3,写入下标 1 | [2,3,4,1] | 前缀 [2,3,4] 有序 |
| 3 / 1 | 4、3、2 依次右移 | [2,2,3,4] | 1 保存在 key |
| 3 / 1 | j=−1,写入 j+1=0 | [1,2,3,4] | 全部有序 |
不要在移动过程中拿整个数组判断元素是否丢失;需要同时看 key。完成一轮后,数组才恢复完整的元素集合。
有序前缀如何扩展
- i=1 时,长度为 1 的前缀天然有序。
- 从前缀末尾开始,把所有严格大于 key 的值右移;它们的相对顺序不变。停止位置左边的值都不大于 key,右边的值都大于 key。
- 把 key 填进空位后,前缀长度增加 1 且仍有序。处理到最后一项,整个数组就成为有序前缀。
04让每一步,都看得见
试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。
从左到右观察数组。橙色表示当前比较,绿色表示已确定的位置。
动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。
代码里的每个关键决定
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复杂度,来自具体的工作量
逆序输入下每个元素最多向前走 i 步,总和为 O(n²)。近乎有序时很快;有序输入为 O(n)。
原地版本仅保存 key 和下标。教学函数复制输入,额外复制占 O(n)。
把工作量具体数出来
逆序的 n 项在第 i 轮要移动 i 项,总计 1+2+…+(n−1),最坏 O(n²)。
有序输入每轮只比较前一项,无需移动,总共 O(n)。近乎有序输入需要消除的逆序较少,因此常常比最坏情况快很多。
原地实现只需 key 与下标,辅助空间 O(1);本课函数为保留输入而复制数组,实际额外分配 O(n)。
06看到什么,应该想到它?
关键词只是线索,继续检查适用条件07这些细节,容易踩坑
保存 key
移动前必须保存原值,否则会被右移覆盖。
有序前缀不是最终位置
未来更小元素仍可能插到前面。
相等也移动会损害稳定性
把值相同但有身份的两项记作 2A、2B。如果条件改成 ≥,后来读到 2B 会把 2A 推向右边,顺序就变成 2B、2A。
怎样修正:只移动严格大于 key 的项。稳定排序要求相同键的相对次序保留,不是只要求数值非递减。
08把想法带进真实题目
解释空位在哪里
数组 [1,4,5,2] 处理 i=3 时,依次移动哪些值?j 最终是多少?key 应写入哪个下标?
需要一点提示
遇到 1≤2 时停止,j 此时还指向 1。
查看完整推导与答案
- 保存 key=2,先移动 5,再移动 4。
- j 从 2 减到 0,发现 a[0]=1≤2 后退出。
- 写入 a[j+1]=a[1],结果为 [1,2,4,5]。
完成上面的手算练习,再把思路迁移到这些题目。
09不用背模板,回答这几个问题
01最适合插入排序的输入?
02右移前为什么保存 key?
03稳定性需要什么条件?
你已经走完了这次推导。
能用自己的话解释复杂度和不变量,再标记为掌握。