《算法导论（第 3 版）》2.3「算法设计」习题精解：归并排序、无哨兵 MERGE 与二分搜索-平芜编程栈

文档
教程
教育

【免费下载链接】CLRS

📚 Solutions to Introduction to Algorithms Third Edition

项目地址：https://gitcode.com/gh_mirrors/clr/CLRS

本篇技术指南以 docs/Chap02/2.3.md 为主体，系统讲解《算法导论（Introduction to Algorithms, Third Edition）》第 2.3 节「算法设计（Designing algorithms）」的 7 道课后习题：从归并排序（merge sort）的完整分治演示、无哨兵版本的 MERGE 重写，到递归式求解、二分搜索及其在插入排序与两数和问题中的运用。读完本文，你将掌握归并排序的底层合并机制与复杂度分析、数学归纳法证明递归式的完整范式，以及二分搜索两种写法的正确性与时间复杂度论证。文中所有答案均可在本仓库 CLRS Solutions 中找到对应文档，并附带源码级的伪代码与推导过程，可直接用于复习与刷题对照。

1. 章节定位：第 2.3 节在全书中的角色

第 2 章「Getting Started」是《算法导论》正文算法的起点，前两节分别介绍了插入排序（docs/Chap02/2.1.md）与算法分析（docs/Chap02/2.2.md），而 docs/Chap02/2.3.md 则正式引入本书第一个重要的分治算法——归并排序，并由此带出三个核心方法论：

分治法（divide-and-conquer）：分解（divide）→ 解决（conquer）→ 合并（combine）的三步范式；
递归式（recurrence）分析：用递归式刻画分治算法运行时间，如归并排序的 $T(n) = 2T(n/2) + \Theta(n)$；
问题归约（problem reduction）：利用有序性与二分思想，把搜索等问题的复杂度从线性降到对数级。

该节在仓库导航中位于 mkdocs.yml 的「2 Getting Started」下（2.3 Designing algorithms: docs/Chap02/2.3.md），全部内容以 Markdown + KaTeX 渲染，适合在移动设备上阅读。下文按习题编号逐一精解，并在每节补充实现原理与相关章节的交叉引用。

2. 习题 2.3-1：以图 2.4 为模型演示归并排序全过程

以教材 Figure 2.4 为模型，在数组 $A = \langle 3, 41, 52, 26, 38, 57, 9, 49 \rangle$ 上演示归并排序的操作过程。

该数组共有 $n = 8$ 个元素，恰好是 $2$ 的幂，因此归并排序的递归树是完全平衡的。整个过程分为两个阶段：

分解阶段：不断把数组从中间一分为二，直到每个子数组只含单个元素（单元素数组天然有序）：

$$ [3] \quad [41] \quad [52] \quad [26] \quad [38] \quad [57] \quad [9] \quad [49] $$

合并阶段：自底向上两两合并，先合并成 4 个长度为 2 的有序子数组，再合并成 2 个长度为 4 的有序子数组，最后合并成完整的有序数组：

$$ \downarrow $$

$$ [3|41] \quad [26|52] \quad [38|57] \quad [9|49] $$

$$ \downarrow $$

$$ [3|26|41|52] \quad [9|38|49|57] $$

$$ \downarrow $$

$$ [3|9|26|38|41|49|52|57] $$

每一步合并都对应一次 MERGE 调用。以第一层为例：[3]与[41]合并时，比较 3 与 41，先取 3，再取 41，得到[3|41]；[52]与[26]合并时，26 更小先取，得到[26|52]。第二层[3|41]与[26|52]合并时，依次比较 3、26、41、52，得到[3|26|41|52]。最终层把[3|26|41|52]与[9|38|49|57]合并，经过 3 与 9、26 与 9、26 与 38、41 与 38、41 与 49、52 与 49、52 与 57 共 7 次比较得到完全有序的[3|9|26|38|41|49|52|57]。

合并阶段的核心不变式（loop invariant）：在 MERGE 主循环每轮迭代开始时，子数组 $A[p..k-1]$ 中存放的是 $L$ 与 $R$ 中 $k-p$ 个最小元素，且已按升序排列。初始化时 $k = p$，$A[p..k-1]$ 为空，不变量平凡成立；迭代中每次把 $L[i]$ 与 $R[j]$ 中较小者放入 $A[k]$，保证了「剩余元素的最小值」被正确安置；终止时 $k = r + 1$，$A[p..r]$ 完全有序。

运行时间：归并排序满足递归式 $T(n) = 2T(n/2) + \Theta(n)$，其解为 $T(n) = \Theta(n\lg n)$，这也是教材 2.3 节与习题 2.3-3 的分析基础。空间方面，每次 MERGE 需额外 $\Theta(n)$ 的辅助数组，因此归并排序不是原地排序算法。

3. 习题 2.3-2：去掉哨兵（sentinels）重写 MERGE

重写 MERGE 过程，使其不使用哨兵，而是在 $L$ 或 $R$ 中任一数组的所有元素都已被复制回 $A$ 时立即停止，然后把另一数组的剩余元素直接复制回 $A$。

教材原版 MERGE 通过在 $L$、$R$ 末尾放置哨兵 $\infty$ 来简化边界判断，但习题要求去掉哨兵。解法是在主循环中先检查两个数组是否已经耗尽：

MERGE(A, p, q, r) n1 = q - p + 1 n2 = r - q let L[1..n1] and R[1..n2] be new arrays for i = 1 to n1 L[i] = A[p + i - 1] for j = 1 to n2 R[j] = A[q + j] i = 1 j = 1 for k = p to r if i > n1 A[k] = R[j] j = j + 1 else if j > n2 A[k] = L[i] i = i + 1 else if L[i] ≤ R[j] A[k] = L[i] i = i + 1 else A[k] = R[j] j = j + 1

要点解析：

参数含义与哨兵版本完全一致：$A[p..q]$ 与 $A[q+1..r]$ 是两个已经有序的子数组，$p \le q < r$；$n_1 = q - p + 1$、$n_2 = r - q$ 分别是左右两段的长度。
两个耗尽检查的顺序很关键：必须先检查i > n1（左数组先空），再检查j > n2（右数组先空）。若先检查右数组，当两个数组同时耗尽时（$i = n_1 + 1$ 且 $j = n_2 + 1$），L[i]与R[j]都越界，行为未定义；按上述顺序，循环在最后一轮由i > n1分支把R[n2]写入后结束，天然规避了越界。
相比哨兵版本，无哨兵版本的代价是每轮迭代都要多做至多两次边界判断，常数因子略有增加；好处是避免了「哨兵值必须大于所有元素」的假设，当待排序元素是浮点数、自定义对象等没有天然 $\infty$ 值的类型时，这个版本更具通用性。

工程延伸：这一「手动检查边界」的思想与第二章 Problem 2-1（docs/Chap02/Problems/2-1.md）一脉相承——该问题讨论在归并排序中，当子问题规模足够小时改用插入排序来「粗化（coarsen）」递归树叶，从而利用插入排序在小型输入上更小的常数因子；合并阶段依旧使用标准合并机制。二者的结合点在于：无论子列表如何生成，合并逻辑的正确性都依赖上述边界处理的完备性。

4. 习题 2.3-3：数学归纳法证明 $T(n) = n\lg n$

用数学归纳法证明：当 $n$ 是 $2$ 的精确幂时，递归式

$$ T(n) = \begin{cases} 2 & \text{if } n = 2, \ 2T(n / 2) + n & \text{if } n = 2^k, \text{for } k > 1 \end{cases} $$

的解是 $T(n) = n\lg n$。

这是归并排序递归式 $T(n) = 2T(n/2) + \Theta(n)$ 在「$n$ 恰好为 2 的幂」这一特殊情形下的精确解（忽略常数因子）。证明分两步：

基础情形（Base case）：当 $n = 2^1$ 时，递归式直接给出 $T(2) = 2$，而 $n\lg n = 2\lg 2 = 2$，等式成立。

归纳步骤（Inductive step）：假设当 $n = 2^k$ 时成立，即 $T(n) = n\lg n = 2^k \lg 2^k = 2^k k$。对 $n = 2^{k+1}$：

$$ \begin{aligned} T(n) & = 2T(2^{k + 1} / 2) + 2^{k + 1} \ & = 2T(2^k) + 2^{k + 1} \ & = 2 \cdot 2^k k + 2^{k + 1} \ & = 2^{k + 1}(k + 1) \ & = 2^{k + 1} \lg 2^{k + 1} \ & = n\lg n. \end{aligned} $$

由数学归纳法原理（P.M.I.），当 $n$ 是 $2$ 的精确幂时，$T(n) = n\lg n$。

补充说明：这一结论是后续第 4 章「主定理（master method）」（见 docs/Chap04/4.5.md）的直接特例——递归式 $T(n) = 2T(n/2) + \Theta(n)$ 满足主定理情形 2（$f(n) = \Theta(n^{\log_2 2}) = \Theta(n)$），故 $T(n) = \Theta(n^{\lg 2} \lg n) = \Theta(n \lg n)$。习题 2.3-3 的价值在于，当 $n$ 恰为 2 的幂时，可以把 $\Theta$ 记号中的常数全部确定下来，得到精确等式 $T(n) = n\lg n$。

5. 习题 2.3-4：递归版插入排序的递归式

插入排序可以写成递归过程：为排序 $A[1..n]$，先递归排序 $A[1..n-1]$，再把 $A[n]$ 插入到有序数组 $A[1..n-1]$ 中。写出该递归版插入排序运行时间的递归式。

分析与答案：把 $A[n]$ 插入有序的 $A[1..n-1]$，最坏情况下需要从右向左扫描并移动全部 $n-1$ 个元素，耗时 $\Theta(n)$。因此递归式为

$$ T(n) = \begin{cases} \Theta(1) & \text{if } n = 1, \ T(n - 1) + \Theta(n) & \text{if } n > 1. \end{cases} $$

展开得 $T(n) = T(n-1) + \Theta(n) = \Theta(1) + \Theta(2) + \cdots + \Theta(n) = \Theta(n^2)$。该递归式的解是 $\Theta(n^2)$，与迭代版插入排序（docs/Chap02/2.1.md 中的INSERTION-SORT）的最坏情况复杂度一致。

要点辨析：这恰好说明了分治策略的优势所在——插入排序每次只把问题规模减少 1（每次递归解决一个规模为 $n-1$ 的子问题），导致递归式呈「线性衰减」，累计代价为 $\Theta(n^2)$；而归并排序把问题对半分解，递归式呈「对数深度」，代价为 $\Theta(n\lg n)$。从递归式的形态即可直观判断一个递归算法的效率，这也是教材把 2.3 节命名为「算法设计」的原因之一。

6. 习题 2.3-5：二分搜索的迭代与递归实现

回顾搜索问题（见习题 2.1-3），若序列 $A$ 已排序，可先检查序列中点与 $v$ 的关系，从而把剩余搜索范围缩小一半。二分搜索重复这一过程。写出二分搜索的伪代码（迭代或递归均可），并论证最坏情况运行时间为 $\Theta(\lg n)$。

二分搜索有效的前提是序列已有序——这与习题 2.1-3 的线性搜索（docs/Chap02/2.1.md 中的LINEAR-SEARCH）形成对比：线性搜索不要求有序，但最坏情况要检查全部 $n$ 个元素；二分搜索通过每次舍弃一半区间，把最坏情况比较次数降到 $\lfloor \lg n \rfloor + 1$ 的量级。

迭代版本：

ITERATIVE-BINARY-SEARCH(A, v, low, high) while low ≤ high mid = floor((low + high) / 2) if v == A[mid] return mid else if v > A[mid] low = mid + 1 else high = mid - 1 return NIL

递归版本：

RECURSIVE-BINARY-SEARCH(A, v, low, high) if low > high return NIL mid = floor((low + high) / 2) if v == A[mid] return mid else if v > A[mid] return RECURSIVE-BINARY-SEARCH(A, v, mid + 1, high) else return RECURSIVE-BINARY-SEARCH(A, v, low, mid - 1)

正确性与复杂度论证：每次将 $v$ 与中点元素 $A[mid]$ 比较后，搜索区间都会缩小一半——若 $v > A[mid]$，则 $v$ 只可能落在 $[mid+1, high]$，因为序列升序且 $A[mid]$ 及其左侧元素都不大于 $A[mid]$；反之只可能落在 $[low, mid-1]$。区间为空的判定是 $low > high$，此时返回NIL。

设 $T(n)$ 为规模为 $n$ 的搜索区间所需时间，则每次递归只处理一个规模减半的子问题，加上常数时间的比较与中点计算，递归式为

$$ T(n) = \begin{cases} \Theta(1) & \text{if } n = 1, \ T(n / 2) + \Theta(1) & \text{if } n > 1. \end{cases} $$

该递归式的解为 $T(n) = \Theta(\lg n)$，即二分搜索的最坏情况运行时间。注意这里与归并排序递归式的关键区别：归并排序每个规模为 $n$ 的问题要递归处理两个规模为 $n/2$ 的子问题，所以是 $2T(n/2)$；二分搜索每层只深入一个子区间，所以是 $T(n/2)$——这是 $\Theta(\lg n)$ 与 $\Theta(n\lg n)$ 差异的根源。

7. 习题 2.3-6：二分搜索能否把插入排序改进到 $\Theta(n\lg n)$？

观察 2.1 节INSERTION-SORT中第 5–7 行的 while 循环用线性扫描方式在有序子数组 $A[i..j-1]$ 中（从右向左）寻找插入位置。能否改用二分搜索（见习题 2.3-5）把插入排序的整体最坏情况运行时间改进到 $\Theta(n\lg n)$？

答案：不能。

理由：INSERTION-SORT第 5–7 行的 while 循环（见 docs/Chap02/2.1.md 中INSERTION-SORT的伪代码）在做两件事：一是查找$A[j]$ 的正确插入位置，二是移动所有比 $A[j]$ 大的元素各向右挪一位（对应 while 循环体中的赋值操作）。当 $A[j]$ 比它前面全部 $j-1$ 个元素都小时，元素移动需要 $\Theta(j)$ 时间。

用二分搜索确实可以把「查找插入位置」的代价从 $\Theta(j)$ 降到 $\Theta(\lg j)$，但元素移动的代价依然高达 $\Theta(j)$，且无法用二分搜索消除——因为数组是连续存储结构，腾出空位必须物理搬移元素。最终每个 $j$ 的主导项仍是 $\Theta(j)$，累加后整体复杂度仍为

$$ \sum_{j=1}^{n} \Theta(j) = \Theta(n^2)。 $$

因此，无法把插入排序的整体最坏情况运行时间改进到 $\Theta(n\lg n)$。这一习题揭示的教训具有普遍意义：复杂度瓶颈可能不在「比较」，而在「数据搬移」。若改用链表存储（插入 $O(1)$ 但随机访问退化），又会在二分搜索的取中点操作上付出 $\Theta(j)$ 代价——这正是后续章节（如第 10 章「基本数据结构」与各种平衡树）反复权衡的核心矛盾。

8. 习题 2.3-7 ★：$\Theta(n\lg n)$ 时间的两数和判定问题

设计一个 $\Theta(n\lg n)$ 时间的算法：给定一个含 $n$ 个整数的集合 $S$ 和另一个整数 $x$，判定 $S$ 中是否存在两个元素之和恰好等于 $x$。

算法思路（先排序，再对每个元素二分搜索其补数）：

排序：对 $S$ 排序，耗时 $\Theta(n\lg n)$；
逐元素补数搜索：对每个元素 $s_i$（$i = 1, \dots, n$），在 $A[i+1..n]$ 中二分搜索 $s_i' = x - s_i$，单次耗时 $\Theta(\lg n)$：
- 若找到 $s_i'$，返回其位置，算法结束；
- 否则继续下一个元素。

为什么只搜索 $A[i+1..n]$ 而非整个数组：若在 $A[1..n]$ 中搜索，会重复统计形如 $(s_i, s_j)$ 与 $(s_j, s_i)$ 的同一对组合；只搜索当前元素之后的后缀区间，可保证每对无序组合只被检查一次，同时也能避免出现 $i = j$（同一元素自配）的假阳性。

复杂度分析：

$$ \Theta(n\lg n) + n \cdot \Theta(\lg n) = \Theta(n\lg n)。 $$

排序是第一步的代价，而 $n$ 次二分搜索每次 $\Theta(\lg n)$，总代价依然被 $\Theta(n\lg n)$ 支配。这一「排序 + 二分」的套路是算法设计中的经典组合，也是本题被标星（$\star$，表示较难）的原因——它要求你把学过的排序算法与搜索算法组合成一个新问题的解法。本题在工程界的知名形态是「Two Sum」问题：在有序数组上对每个元素二分搜索补数，或者用哈希表做到期望线性时间（但那需要额外的 $O(n)$ 空间，且属于第 11 章哈希表的内容）。

9. 延伸阅读：归并排序思想在第二章问题的进一步应用

本节习题中的归并排序与二分思想，在第二章的 Problem 中有两个直接延伸，强烈建议配合阅读：

Problem 2-1：归并排序中的小数组插入排序：讨论把归并排序与插入排序结合——当递归到达足够小的子问题时改用插入排序，整体最坏情况时间变为 $\Theta(nk + n\lg(n/k))$。当取 $k = \Theta(\lg n)$ 时复杂度仍为 $\Theta(n\lg n)$，而实践中 $k$ 应取「插入排序比归并排序更快的最长子列表长度」。这是对 2.3 节「分治 + 常数因子优化」思想的实战演练。
Problem 2-4：统计逆序对：题目 d 问给出一个 $\Theta(n\lg n)$ 最坏情况算法统计数组逆序对个数，提示「修改归并排序」。解答给出COUNT-INVERSIONS与MERGE-INVERSIONS两个过程：前者递归统计左右两半内部的逆序对，后者在合并时统计「左半元素大于右半元素」的跨区间逆序对——每当L[i] > R[j]时，左半剩余 $n_1 - i + 1$ 个元素全部大于 $R[j]$，一次累加即可。整体复杂度与归并排序相同，仍是 $\Theta(n\lg n)$。

这两个 Problem 充分说明了 2.3 节习题的价值：归并排序不只是「一个排序算法」，更是一个可改造、可复用的分治框架——把合并时的比较逻辑替换为计数逻辑，就能在同样的 $\Theta(n\lg n)$ 时间内解决看似无关的问题。

小结：2.3 节的全部 7 道习题围绕「分治 + 递归分析」这一主线展开——用归并排序的完整演示建立直觉（2.3-1），用去哨兵 MERGE 理解合并的边界细节（2.3-2），用归纳法把递归式解到精确形式（2.3-3），用递归式对比插入排序与归并排序的效率差异（2.3-4、2.3-6），用二分搜索展示「有序 + 减半」的 $\Theta(\lg n)$ 范式（2.3-5），最后用两数和问题体会算法组合的威力（2.3-7）。在 docs/Chap02/2.3.md 中可以找到以上全部原始答案，配合本文的推导注释阅读效果更佳。