01先从一个问题出发
两叠已经排好序的卡片,如何高效合成一叠?
[4,1,3,2];先递归,再合并。
先回答一个更小的问题:两段有序数组怎么合并
面对 [1,4] 与 [2,3],全体最小值一定是两段头部中的较小者,因为各段其余元素都不小于自己的头部。取 1 后只移动左指针;再比较 4 与 2,取 2;再取 3;最后追加左侧剩下的 4。每个元素恰好输出一次。
于是困难只剩下『如何让两段有序』。把每段继续平分,直到长度为 0 或 1,可以直接视为有序;子调用返回后,再执行刚刚理解的合并。递归负责把前提变真,合并负责把结论扩大。
拆分并不等于排序已经发生
对 [4,1,3,2],拆成 [4,1]、[3,2] 时,两个片段仍无序。继续拆成单项,才得到最基础的有序片段。返回时合成 [1,4]、[2,3],最外层再合成 [1,2,3,4]。
本课使用半开区间 [left,right)。mid 将它准确分成 [left,mid) 和 [mid,right),无重叠也无遗漏。right−left≤1 才是终止判断;不能把 right 当作有效下标访问。
02最直接的办法,为什么慢?
反复找未排序区域中的最小值。
每次选择都重新扫描剩余元素,累计平方级比较。
03一步步,推导出优化思路
先学会合并两段有序数据
两个有序数组可以只比较当前头部,用 O(n) 时间合并。
递归拆到天然有序的单项
把问题不断平分,单元素天然有序。
返回时逐层合并
自底向上合并;每一层总共处理 n 个元素,层数约 log₂ n。
合并时,缓冲区已排序,且不大于两个输入区间中尚未取出的元素。
拿一个小输入,逐步手算
[4,1,3,2];先递归,再合并。
| 阶段 | 两个输入区间 | 选择 / 结果 |
|---|---|---|
| 拆分 | [4,1] 与 [3,2] | 还未有序,继续拆 |
| 左子问题返回 | [4] 与 [1] | 取 1,再取 4 → [1,4] |
| 右子问题返回 | [3] 与 [2] | 取 2,再取 3 → [2,3] |
| 顶层合并 | [1,4] 与 [2,3] | 比较 1、2,取 1 |
| 继续 | [4] 与 [2,3] | 依次取 2、3 |
| 一侧耗尽 | [4] 与 [] | 追加 4 → [1,2,3,4] |
为什么可以整段追加剩余元素?它们内部已有序,另一段又已取空,不再有竞争者需要比较。
递归与合并分别证明
- 长度≤1 的区间有序,基础情形成立。假设两个更短区间已经被递归正确排序。
- 合并时,每次选择两个未取头部中的较小者,它就是所有剩余元素中的最小者;已输出部分始终有序。
- 所有元素被输出且没有丢失或重复,再写回原区间,因此父问题有序。对区间长度归纳,最外层也有序。
04让每一步,都看得见
试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。
从左到右观察数组。橙色表示当前比较,绿色表示已确定的位置。
动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。
代码里的每个关键决定
sort(left, mid)- 先把左半段完整排好,返回后才开始右半段。递归树画在同一层,不代表代码并行执行。
if a[i] <= a[j]:- 相等时取左段,原先较早的元素仍先输出,保证稳定性。
merged.extend(a[i:mid])- 循环结束后补上左边剩余项;右边也做同样处理,其中至少一段为空。
a[left + offset] = value- 把临时合并结果写回当前区间。这个偏移是相对于 left,不能总是从数组下标 0 覆盖。
05复杂度,来自具体的工作量
递推 T(n)=2T(n/2)+O(n),共有 O(log n) 层,每层 O(n),最好和最坏均为 O(n log n)。
合并缓冲区峰值 O(n),递归栈 O(log n),合计 O(n)。
把工作量具体数出来
n=8 时,最底层合并 4 组长度 2,总处理 8 项;上层 2 组长度 4 仍共 8 项;最上层处理 8 项。合并工作约 8×3。
一般有 O(log n) 层,每层合并区间总长度 O(n),因此 O(n log n)。n 不是 2 的幂时两半略不等长,增长阶不变。
临时合并数组峰值 O(n),递归栈 O(log n),合计 O(n)。累计分配量可能大于峰值空间,分析空间复杂度通常关注同时存活的数据。
06看到什么,应该想到它?
关键词只是线索,继续检查适用条件07这些细节,容易踩坑
相等时先选左边
使用 <= 保证跨区间的同值元素仍稳定。
半开区间
本实现处理 [left, right),不要把 right 当作有效下标。
把不相邻的两个问题混成同一个区间
若左递归也包含 mid、右递归也从 mid 开始,mid 被重复处理;长度为 2 时还可能让一个子问题与父问题一样大,无法结束。
怎样修正:固定半开约定,左右区间分别 [left,mid)、[mid,right)。手算长度 0、1、2 与奇数长度,检查每次都严格变小。
08把想法带进真实题目
有相等元素时选谁
合并 [1A,3] 与 [1B,2],A 原先在 B 左边。写出稳定的输出顺序,并说明相等时选右边会怎样。
需要一点提示
第一次比较就是稳定性决策。
查看完整推导与答案
- 先取 1A,再取 1B,然后 2、3,得到 [1A,1B,2,3]。
- 若第一次取右边的 1B,结果数值仍有序,但 A、B 的相对顺序被改变。
- 排序正确性与稳定性是两件事,稳定性需要额外检查相等时的处理。
完成上面的手算练习,再把思路迁移到这些题目。
09不用背模板,回答这几个问题
01为什么每层合并是 O(n)?
02相等时先选哪个?
03常规数组归并的额外空间?
你已经走完了这次推导。
能用自己的话解释复杂度和不变量,再标记为掌握。