3.3 分治排序：归并与快排

这一节，你能解决什么问题

学完这一节，你能够：

1. 理解分治策略的设计范式，不只是"分成小块"，而是知道为什么这样做有效
2. 分析归并排序和快速排序的复杂度，理解 Θ(n log n) 是怎么来的
3. 推导快速排序的期望复杂度，用指示器随机变量分析比较概率
4. 判断什么时候快排会被攻击，理解确定性算法的脆弱性
5. 审查 agent 给出的排序实现，发现隐藏的 Θ(n²) 风险

---

问题情境

你的朋友写了一个排序程序，说"用了快速排序，很快"。

你问："最坏情况是什么？"

朋友说："理论上是 Θ(n²)，但几乎不会遇到。"

你问："如果有人故意构造一个特殊输入呢？"

朋友愣住了。

这不是假设。1999年，有人真的发现某些 qsort() 实现可以被"杀手序列"攻击——构造一个输入，让 Θ(n log n) 退化成 Θ(n²)。

问题：为什么确定性快排可以被攻击？怎么避免？

这个问题引出了一个更大的问题：分治策略到底是怎么工作的？

---

直观思路

"分治"听起来很抽象，其实就是：

把大问题切成小块，分别解决，再把答案拼起来。

想想怎么排序一叠扑克牌：

方法一（插入排序）：一张一张插入，每次处理一个新元素

方法二（分治排序）：分成两堆，分别排序，然后合并

方法二有什么好处？

• 两堆可以并行处理（如果有多人）
• 两堆排序后，合并很简单（比较两个堆的顶部，取小的）

但关键问题是：为什么分治更快？

---

这个方法是怎么想到的

归并排序的思路

问题：怎么排序 n 个元素？

朴素想法：一张一张比较，Θ(n²)。

洞察：如果分成两半，两半分别排序，合并只需要 Θ(n)。

关键：合并两个有序数组很简单——比较两个顶部，取小的。

代价：需要额外空间存储临时数组。

快速排序的思路

问题：能不能原地排序？

朴素想法：原地排序，每次找一个元素的位置，Θ(n²)。

洞察：如果选一个"参照点"（pivot），把所有比它小的放到左边，比它大的放到右边，然后递归处理两边。

关键：分割后，不需要合并——左右两边各自排序，pivot 已经在正确位置。

代价：pivot 选择很关键。如果总是选到极端值，分割不均匀，退化成 Θ(n²)。

---

规范定义

分治范式

分治策略的三个步骤：

1. 分解（Divide）：把问题分成若干子问题
2. 解决（Conquer）：递归解决子问题
3. 合并（Combine）：合并子问题的解

归并排序和快速排序

两者都用分治，但侧重不同：

算法	分解	解决	合并	主要工作
归并排序	平均分割	递归排序	合并两个有序数组	合并 Θ(n)
快速排序	按 pivot 分割	递归排序	无需合并	分割 Θ(n)

关键差异：

• 归并排序：分解是简单的（切成两半），合并是复杂的（需要额外空间）
• 快速排序：分解是复杂的（需要选 pivot），合并是简单的（原地完成）

---

算法实现

归并排序

MERGE-SORT(A, p, r):
    if p < r:
        q = (p + r) // 2           # 中点
        MERGE-SORT(A, p, q)        # 排左半
        MERGE-SORT(A, q+1, r)      # 排右半
        MERGE(A, p, q, r)          # 合并

MERGE 是核心：合并两个有序数组。

MERGE(A, p, q, r):
    # A[p..q] 和 A[q+1..r] 都已有序
    创建临时数组 L = A[p..q]
    创建临时数组 R = A[q+1..r]
    
    i = 0, j = 0, k = p
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            A[k] = L[i]; i++
        else:
            A[k] = R[j]; j++
        k++
    
    # 复制剩余元素
    复制 L[i..] 到 A[k..]
    复制 R[j..] 到 A[k..]

一步步执行：

初始：[5, 2, 4, 7, 1, 3, 2, 6]

分解：分成 [5, 2, 4, 7] 和 [1, 3, 2, 6]

递归排序左半：[5, 2, 4, 7] → [2, 4, 5, 7]
递归排序右半：[1, 3, 2, 6] → [1, 2, 3, 6]

合并：[2, 4, 5, 7] 和 [1, 2, 3, 6]
      比较 2 和 1 → 取 1
      比较 2 和 2 → 取 2（左）
      比较 4 和 2 → 取 2（右）
      比较 4 和 3 → 取 3
      比较 4 和 6 → 取 4
      ...

结果：[1, 2, 2, 3, 4, 5, 6, 7]

快速排序

QUICKSORT(A, p, r):
    if p < r:
        q = PARTITION(A, p, r)     # 分割
        QUICKSORT(A, p, q-1)       # 排左边（< pivot）
        QUICKSORT(A, q+1, r)       # 排右边（> pivot）

PARTITION 是核心：把数组分成两堆。

PARTITION(A, p, r):
    x = A[r]                       # 选最后一个作为 pivot
    i = p - 1                      # "< pivot" 区域的边界
    for j = p to r-1:
        if A[j] <= x:
            i++
            swap A[i] and A[j]     # 加入 "< pivot" 区域
    swap A[i+1] and A[r]           # pivot 放到正确位置
    return i + 1                   # 返回 pivot 位置

一步步执行：

初始：[3, 7, 2, 9, 5, 1, 8]  pivot = 8

j=0: 3 ≤ 8 → i++, swap → [3, |7, 2, 9, 5, 1, 8]
j=1: 7 ≤ 8 → i++, swap → [3, 7, |2, 9, 5, 1, 8]
j=2: 2 ≤ 8 → i++, swap → [3, 7, 2, |9, 5, 1, 8]
j=3: 9 > 8 → 无操作
j=4: 5 ≤ 8 → i++, swap → [3, 7, 2, 5, |9, 1, 8]
j=5: 1 ≤ 8 → i++, swap → [3, 7, 2, 5, 1, |9, 8]

最后：swap pivot → [3, 7, 2, 5, 1, 8, |9]

分割结果：pivot 左边都 ≤ 8，右边都 > 8

---

正确性分析

归并排序：循环不变式证明 MERGE

不变式：在 MERGE 的每次迭代开始时，A[p..k-1] 包含了 L[0..i-1] 和 R[0..j-1] 中最小的 (k-p) 个元素，且已排序。

证明：

1. 初始化

k = p，A[p..k-1] 是空集，包含最小的 0 个元素。成立。

2. 保持

迭代时，比较 L[i] 和 R[j]，较小的放入 A[k]。

推导过程：

• L 和 R 都是有序的（前提）
• L[i] 是 L 中最小的未放入元素
• R[j] 是 R 中最小的未放入元素
• min(L[i], R[j]) 是所有未放入元素中最小的
• 放入 A[k] 后，A[p..k] 包含最小的 (k-p+1) 个元素

无论取 L[i] 还是 R[j]，A[p..k] 都包含了最小的 (k-p+1) 个元素，且有序。

保持成立。

3. 终止

循环结束时，L 或 R 已空。剩余元素复制到 A 后，A[p..r] 包含所有元素，且有序。

证毕。

快速排序：循环不变式证明 PARTITION

不变式：每次迭代开始时：

• A[p..i] 所有元素 ≤ pivot
• A[i+1..j-1] 所有元素 > pivot
• A[j..r-1] 未处理
• A[r] 是 pivot

证明：

1. 初始化

i = p-1，j = p。两个区域都是空集。成立。

2. 保持

情况 A[j] ≤ pivot：

• i++，然后 swap A[i] 和 A[j]
• A[j]（≤ pivot）进入 A[p..i] 区域
• A[i+1..j-1] 区域不变（j-1 == i，空集）
• 推导过程：
  • swap 前：A[p..i] ≤ pivot（不变式成立），A[j] ≤ pivot（刚检测）
  • swap 后：A[p..i+1] ≤ pivot（新元素 ≤ pivot）
  • A[i+2..j] = 原来的 A[i+1..j-1]，都是 > pivot

情况 A[j] > pivot：

• 不操作
• A[j] 进入 A[i+1..j-1] 区域（j 增加）
• 推导过程：
  • A[j] > pivot，自然留在 > pivot 区域

无论哪种情况，不变式保持。

3. 终止

j = r 时，swap A[i+1] 和 A[r]。pivot 进入正确位置。

推导过程：

• A[p..i] ≤ pivot
• A[i+1..r-1] > pivot
• A[r] = pivot
• swap 后：A[p..i] ≤ pivot，A[i+1] = pivot，A[i+2..r] > pivot

证毕。

---

复杂度分析

归并排序：递归方程

T(n) = 2T(n/2) + Θ(n)

• 2T(n/2)：两个子问题，各一半大小
• Θ(n)：合并时间

求解（展开法）：

展开递归：

T(n) = 2T(n/2) + cn
     = 2(2T(n/4) + cn/2) + cn
     = 4T(n/4) + cn + cn
     = 8T(n/8) + cn + cn + cn
     = ...
     = nT(1) + cn × (log₂ n)
     = Θ(n) + Θ(n log n)
     = Θ(n log n)

关键：每层合并成本是 Θ(n)，有 log n 层。

层数推导：

n → n/2 → n/4 → ... → 1

设经过 k 层后变成 1：
n / 2^k = 1
n = 2^k
k = log₂ n

快速排序：期望复杂度推导

快排的复杂度依赖分割的均匀性。

理想情况：每次分割成相等的两半

T(n) = 2T(n/2) + Θ(n) = Θ(n log n)

最坏情况：每次 pivot 是最小或最大

T(n) = T(n-1) + Θ(n) = Θ(n²)

期望情况：随机输入或随机选择 pivot

用指示器随机变量分析。

指示器随机变量方法

定义：设 X 为快排的比较次数。定义指示器变量：

X_ij = 1  如果元素 i 和 j 在排序过程中被比较
X_ij = 0  如果元素 i 和 j 没有被比较

其中 i < j（假设元素按某种方式编号）。

总比较次数：

X = Σ_{1≤i<j≤n} X_ij

期望 E[X] = Σ_{1≤i<j≤n} E[X_ij]
          = Σ_{1≤i<j≤n} P(i 和 j 被比较)

关键洞察：什么时候 i 和 j 会被比较？

观察：快排的比较发生在 PARTITION 过程中。

元素 i 和 j 被比较的唯一条件是：它们中第一个被选为 pivot。

为什么？

1. 如果在 i 和 j 都还没被选为 pivot 之前，某个在 i 和 j 之外的元素被选为 pivot：

   • 如果 pivot < i：i 和 j 都进入 > pivot 区域，继续在一起
   • 如果 pivot > j：i 和 j 都进入 < pivot 区域，继续在一起
   • 如果 pivot 在 i 和 j 之间：i 进入 < pivot，j 进入 > pivot，分离了！不再会比较

2. 如果 pivot 是 i 或 j：比较 i 和 j（因为 PARTITION 会把所有元素和 pivot 比较）

3. 如果 i 和 j 已经分离了（被某个中间 pivot 分开）：它们永远不会比较

结论：i 和 j 被比较 iff 在 i 和 j 被任何中间 pivot 分开之前，i 或 j 被选为 pivot。

计算 P(i 和 j 被比较)

考虑元素集合 S = {i, i+1, ..., j}（共 j-i+1 个元素）。

这 j-i+1 个元素中，第一个被选为 pivot 的概率是：

P(i 或 j 是 S 中第一个 pivot) = 2 / (j-i+1)

推导过程：

• 随机选择 pivot，每个元素被选的概率相等
• S 中有 j-i+1 个元素
• 第一个被选为 pivot 的概率，每个元素都是 1/(j-i+1)
• i 或 j 是第一个的概率 = 1/(j-i+1) + 1/(j-i+1) = 2/(j-i+1)

期望比较次数

E[X] = Σ_{i<j} P(i 和 j 被比较)
     = Σ_{i<j} 2/(j-i+1)

分组计算（按间隔 k = j-i）：

E[X] = Σ_{k=1}^{n-1} Σ_{i=1}^{n-k} 2/(k+1)
     = Σ_{k=1}^{n-1} (n-k) × 2/(k+1)
     ≈ 2n × Σ_{k=1}^{n-1} 1/k
     ≈ 2n × ln n
     = Θ(n log n)

精确估计：

Σ_{k=1}^{n-1} (n-k) × 2/(k+1)

k=1: (n-1) × 2/2 = n-1
k=2: (n-2) × 2/3 ≈ 2n/3
...

总和 ≈ 2n × H_n ≈ 2n ln n

其中 H_n 是调和级数，H_n ≈ ln n + γ（γ 是欧拉常数）。

结论

期望时间复杂度：Θ(n log n)

最坏时间复杂度：Θ(n²)

---

什么时候不该用这个方法

归并排序

该用的情况：

• 大数据排序（稳定 Θ(n log n)）
• 外部排序（数据在磁盘，可以分块合并）
• 需要稳定性（相等元素保持原顺序）
• 并行排序（可以并行处理两半）

不该用的情况：

• 内存紧张（需要 Θ(n) 额外空间）
• 小数据（Θ(n) 的额外开销不值得）
• 原地排序必须（无法分配额外数组）

快速排序

该用的情况：

• 一般场景（实践中最快，缓存友好）
• 原地排序需要
• 随机输入（期望 Θ(n log n)）

不该用的情况：

• 实时系统（不能接受 Θ(n²) 最坏）
• 攻击风险（用户可能构造恶意输入）
• 需要稳定性（快排不稳定）

改进策略

快排改进：

1. 随机化 pivot：消除对输入分布的依赖
2. 三数取中：选第一个、中间、最后一个的中位数
3. 小数组切换插入排序：n < 50 时用插入排序

关键洞察：随机化快排消除了对输入分布的依赖，但仍然依赖 RNG 的质量。在实践中，RNG 可控性比用户输入分布更可控。

---

本节小结

解决了什么问题？

• Θ(n log n) 排序，比 Θ(n²) 快得多
• 归并排序稳定但需额外空间
• 快排原地但最坏 Θ(n²)

核心方法是什么？

• 分治策略：分解 → 递归解决 → 合并
• 归并排序：分解简单，合并复杂
• 快速排序：分解复杂，合并简单

为什么正确？

• 循环不变式证明 MERGE 和 PARTITION
• 递归保证子问题正确
• 合并/分割保证整体正确

代价是什么？

算法	最坏时间	期望时间	空间	稳定
归并排序	Θ(n log n)	Θ(n log n)	Θ(n)	✓
快速排序	Θ(n²)	Θ(n log n)	Θ(log n)	✗

适用场景？

• 归并：大数据、需要稳定、有额外空间
• 快排：一般场景、原地排序、可以接受概率性快

能否自己使用？

能。关键是理解：

• 归并牺牲空间换取稳定和最坏保证
• 快排牺牲最坏保证换取速度和原地
• 随机化快排消除对输入分布的依赖

---

练习

基本理解

练习 1：对数组 [5, 2, 4, 7, 1, 3, 2, 6]，画出归并排序的完整递归过程（包括分解和合并）。

练习 2：对数组 [3, 7, 2, 9, 5, 1, 8]，画出 PARTITION 的执行过程，标注 i 和 j 的变化。

练习 3：为什么归并排序稳定，快排不稳定？

指示器变量分析

练习 4：计算快排对 [1, 2, 3, 4, 5, 6] 排序的期望比较次数。

• 列出所有 (i, j) 对
• 计算 P(i 和 j 被比较)
• 求和验证 Θ(n log n)

练习 5：解释为什么 P(i 和 j 被比较) = 2/(j-i+1)，而不是 1/n 或其他值。

错误诊断

练习 6：以下快排实现有什么问题？

def quicksort_bug(arr, p, r):
    if p < r:
        q = partition(arr, p, r)
        quicksort_bug(arr, p, q)    # ← 这里
        quicksort_bug(arr, q+1, r)

提示：考虑 q 的含义，以及递归范围。

练习 7：为什么 PARTITION 用 A[j] <= x 而不是 A[j] < x？对稳定性有什么影响？

方案比较

练习 8：比较三种 Θ(n log n) 排序：

维度	归并排序	快速排序	堆排序
最坏时间
期望时间
空间复杂度
是否稳定
缓存友好度

填完后，给出一个场景匹配建议。

开放设计

练习 9：杀手序列构造。

对"选第一个元素作为 pivot"的确定性快排，构造一个使其退化的输入序列。

分析：构造后，比较次数是多少？

练习 10：随机化快排验证。

让 agent 实现随机化快排和确定性快排，对比它们在以下输入上的运行时间：

1. 随机数组
2. 已有序数组
3. 逆序数组
4. 构造的杀手序列

写一份实验报告，分析差异。

---

上一节：3.2 插入排序

下一节：3.4 堆排序