408 高频考点精讲:归并排序(Merge Sort)¶
模块归属:数据结构 · 排序
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
- 近十年考查频次:3 次(2016~2025 年:2017#10、2022#10、2024#10)
- 历年总考查频次:5 次(统考历史考查还包含 2011#9、外部排序多路归并等)
- 出题形式:单项选择题为主,算法设计题中常作为经典分治范式出现
- 命题特点:
- 考查归并(Merge)核心操作的形式化语义与底层指针扫描执行机制。
- 考查双子表合并过程中关键字比较次数的精确计算,重点考察“一侧提前耗尽导致零比较直接拷贝”的边界陷阱。
- 考查归并排序在时间复杂度、空间复杂度、稳定性等多维指标上与其他主流内部排序算法的横向综合对比。
- 考查二路归并树的拓扑形态、归并总趟数以及递归树深度的代数推导。
二、 具体考察内容¶
1. 归并与分治算法思想的形式化定义¶
(1) 归并操作的形式化定义¶
归并(Merge)的核心语义是将两个或两个以上彼此有序的子序列,组合为一个全局有序的新序列。 二路归并(2-Way Merge)特指将两个相邻的有序子表合并为一个更大的有序表的操作。设存在两个升序子表: $\(L_1 = (x_1, x_2, \dots, x_m), \quad x_1 \le x_2 \le \dots \le x_m\)$ $\(L_2 = (y_1, y_2, \dots, y_n), \quad y_1 \le y_2 \le \dots \le y_n\)$ 二路归并操作生成包含全部 \(m + n\)$ \text{个元素的单一升序序列} $\(L = (z_1, z_2, \dots, z_{m+n})\)。
(2) 基于分治范式(Divide-and-Conquer)的递归实现¶
二路归并排序严格遵循分治策略的三步范式:
1. 分解(Divide):将当前包含 \(n\)$ \text{个待排元素的区间} $\([low, high]\)$ \text{划分为两个规模大致相等的子区间} $\([low, mid]\)$ \text{与} $\([mid + 1, high]\)$ \text{,其中分割中点} $\(mid = \lfloor (low + high) / 2 \rfloor\);
2. 解决(Conquer):递归调用归并排序算法,分别对左子区间与右子区间执行排序。递归终止基准情形(Base Case)为区间长度为 1(\(low \ge high\)),此时单个元素自身天然有序;
3. 合并(Combine):调用核心合并过程 Merge(A, low, mid, high),利用双指针同步扫描已排序的左右两个子区间,将结果暂存至辅助数组,最终写回原数组。
(3) 核心算法 C 语言标准实现¶
// 辅助数组 B,全局分配以避免频繁递归申请释放开销
int *B = (int *)malloc((n + 1) * sizeof(int));
// 核心合并过程:将有序的 A[low..mid] 和 A[mid+1..high] 合并为有序的 A[low..high]
void Merge(int A[], int low, int mid, int high) {
int i, j, k;
// 将待合并区间的全部元素复制至辅助数组 B
for (k = low; k <= high; k++) {
B[k] = A[k];
}
i = low; // 左半区段指针
j = mid + 1; // 右半区段指针
k = low; // 目标写回位置指针
// 双指针比对扫描,较小者优先写回原数组
while (i <= mid && j <= high) {
if (B[i] <= B[j]) { // 此处取 "<=" 是保证算法稳定性的关键
A[k++] = B[i++];
} else {
A[k++] = B[j++];
}
}
// 若左半区段尚有剩余元素,直接依次复制回原数组
while (i <= mid) {
A[k++] = B[i++];
}
// 若右半区段尚有剩余元素,直接依次复制回原数组
while (j <= high) {
A[k++] = B[j++];
}
}
// 自顶向下递归归并排序主函数
void MergeSort(int A[], int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2; // 防止下标溢出
MergeSort(A, low, mid); // 递归排序左半区
MergeSort(A, mid + 1, high); // 递归排序右半区
Merge(A, low, mid, high); // 合并两个有序区间
}
}
2. 核心合并过程(Merge)比较次数的上界与下界严格推导¶
给定两个待归并的有序子表 \(L_1\)$ \text{(长度为} $\(m\)$ \text{)与} $\(L_2\)$ \text{(长度为} $\(n\)$ \text{),二者关键字之间的比较次数记为} $\(C\)。
(1) 比较操作的物理本质¶
在双指针扫描比对循环(while (i <= mid && j <= high))中:
* 每执行一次关键字比较(B[i] <= B[j]),必然能够确定且仅能确定一个元素输出到目标数组中,对应指针后移一位;
* 一旦某一个子表的指针越界(即该子表的所有元素均已输出),比对循环立即终止;
* 另一个未耗尽子表中的所有剩余元素,无需进行任何关键字比较,直接通过顺序内存拷贝追加到目标数组尾部。
(2) 比较次数下界推导(最好情况,Best Case)¶
- 触发条件:某一个子表中的最大元素严格小于另一子表中的最小元素。 设 \(\max(L_1) < \min(L_2)\)$ \text{,且} $\(m \le n\)。
- 执行轨迹: \(L_1\)$ \text{中的元素依次与} $\(L_2\)$ \text{的第一个元素比较,每次比较均是} $\(L_1\) 的当前元素较小并被输出。 当 \(L_1\)$ \text{的全部} $\(m\)$ \text{个元素输出完毕后,共执行} $\(m\)$ \text{次比较。此时} $\(L_1\)$ \text{指针越界,循环退出。} $\(L_2\)$ \text{的所有} $\(n\) 个元素直接批量复制。
- 比较次数下界: $\(C_{\min} = \min(m, n)\)$
(3) 比较次数上界推导(最坏情况,Worst Case)¶
- 触发条件:两个子表的元素交替穿插排列。 例如 \(L_1 = (1, 3, 5), L_2 = (2, 4, 6)\)。
- 执行轨迹: 在输出前 \(m + n - 1\) 个元素的过程中,每一次输出都必须进行一次关键字比较。 当输出第 \(m + n - 1\) 个元素后,必定恰有一个子表全部输出完毕,而另一个子表仅剩余最后 1 个全局最大元素。该元素无需与任何对象比较,直接复制到输出数组末端。
- 比较次数上界: $\(C_{\max} = m + n - 1\)$
(4) 比较次数界定理¶
对任意两个长度分别为 \(m\)$ \text{与} $\(n\)$ \text{的有序表进行二路归并,关键字之间的比较次数} $\(C\) 严格满足不等式: $\(\min(m, n) \le C \le m + n - 1\)$
若两子表等长(即 \(m = n\)),则比较次数范围为: $\(n \le C \le 2n - 1\)$
3. 二路归并树的形态、高度与归并趟数代数推导¶
二路归并过程在逻辑拓扑上可映射为一棵倒立的完全二叉树,称为二路归并树(2-Way Merge Tree)。
二路归并树拓扑形态示意(以 8 个元素为例):
层级 4 (根节点) [1..8] (最终有序段)
/ \
层级 3 [1..4] [5..8] <--- 第 3 趟归并
/ \ / \
层级 2 [1..2] [3..4] [5..6] [7..8] <--- 第 2 趟归并
/ \ / \ / \ / \
层级 1 (叶节点) [1] [2] [3] [4] [5] [6] [7] [8] <--- 第 1 趟归并 (初始长度 1)
(1) 归并趟数(Passes)代数推导¶
- 初始状态:\(n\)$ \text{个待排元素可视为} $\(n\) 个长度为 1 的有序归并段。
- 第 1 趟归并:两两合并,有序段长度变为 2,段数减少至 \(\lceil n / 2 \rceil\);
- 第 2 趟归并:有序段长度变为 \(2^2 = 4\)$ \text{,段数减少至} $\(\lceil n / 4 \rceil\);
- 第 \(k\)$ \text{趟归并:有序段长度变为} $\(2^k\)$ \text{,段数减少至} $\(\lceil n / 2^k \rceil\)。
- 终止条件:当归并段数量减少为 1 时,即 \(2^k \ge n\)。
因此,对含 \(n\)$ \text{个元素的数组执行二路归并排序,所需的归并总趟数} $\(k\) 为: $\(k = \lceil \log_2 n \rceil\)$
(2) 归并树的高度与节点关系¶
- 若将初始的单元素叶节点算作第 1 层,则二路归并树的总高度 \(h\) 为: $\(h = \lceil \log_2 n \rceil + 1\)$
- 树的分支节点总数等于两两合并的执行次数,恰好为 \(n - 1\) 次。
(3) 单趟归并的计算代价¶
在每一趟归并中,待处理的所有子表总元素数为 \(n\)。 各对相邻子表合并时: * 关键字比较次数至多为各子表长度之和减 1,整趟总比较次数严格小于 \(n\); * 元素由原数组复制到辅助数组并写回原数组的移动次数恒为 \(2n\)。 因此,每一趟归并的时间开销严格为线性阶 \(O(n)\)。
4. 复杂度严密数学推导与主定理证明¶
(1) 时间复杂度推导¶
二路归并排序的递归运行时间满足分治递推方程: $\(T(n) = 2 T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + \Theta(n), \quad T(1) = \Theta(1)\)$
使用主定理(Master Theorem)证明: 分治递归式通用形式为 \(T(n) = a T(n / b) + f(n)\)。 此处参数为:\(a = 2, b = 2, f(n) = \Theta(n)\)。 计算临界指数: $\(\log_b a = \log_2 2 = 1\)$ 比较 \(f(n)\)$ \text{与} $\(n^{\log_b a}\) 的渐进增长阶: $\(f(n) = \Theta(n) = \Theta(n^1) = \Theta(n^{\log_b a})\)$ 该情形严格命中主定理第 2 种情况(Case 2),直接得出解: $\(T(n) = \Theta(n^{\log_b a} \log n) = \Theta(n \log_2 n)\)$
(2) 时间复杂度与输入初始排列的独立性¶
- 最好情况:即便输入序列已处于完全正序状态,分治划分依然严格从中间二分,归并树拓扑形态与高度 \(\lceil \log_2 n \rceil\)$ \text{不发生任何改变,每层合并依然需要扫描所有元素,时间复杂度为} $\(O(n \log_2 n)\);
- 最坏情况:当输入序列为完全逆序或交替排列时,时间复杂度仍为 \(O(n \log_2 n)\);
- 平均情况:时间复杂度同样为 \(O(n \log_2 n)\)。
二路归并排序在最好、最坏与平均情况下的时间复杂度恒定为 \(O(n \log_2 n)\),其渐进运行效率不受初始序列有序程度的影响。
(3) 空间复杂度推导¶
二路归并排序的空间消耗由两部分构成: 1. 辅助工作数组:合并过程必须依赖与待排数组同等规模的外部缓冲区暂存数据,数组大小为 \(n\)$ \text{,空间开销为} $\(O(n)\); 2. 递归调用栈(Call Stack):自顶向下递归深度等于二路归并树的高度,即 \(\lceil \log_2 n \rceil + 1\)$ \text{,递归栈深度为} $\(O(\log_2 n)\)。
总空间复杂度为: $\(S(n) = O(n) + O(\log_2 n) = O(n)\)$
(4) 算法稳定性证明¶
归并排序是稳定的排序算法。其稳定性的充要条件是在核心合并函数 Merge 中,对于左右两段子表中具有相同关键字的元素,必须保证左半段中的元素优先于右半段中的元素复制到目标序列中。
代码实现层面上,判定条件必须使用弱不等式:
B[i] < B[j],则当两元素关键字相等时右半段元素会先被写入,从而破坏稳定性。
5. 多路归并(Multiway Merge)与败者树机制拓展¶
在外部排序及海量数据处理中,二路归并扩展为 \(k\)$ \text{路归并(} $\(k\)-Way Merge)。
(1) 朴素 k 路归并的瓶颈¶
若将 \(k\) 个有序归并段进行合并: * 每次选出全局最小(或最大)关键字时,需要在 \(k\)$ \text{个归并段的当前指针处进行两两比对,需比对} $\(k - 1\) 次; * 归并含有 \(N\)$ \text{个记录的序列,内部总比较次数为} $\((N - 1)(k - 1)\)$ \text{,比较时间复杂度为} $\(O(N \cdot k)\); * 当 \(k\) 增大时,内部比较时间将呈线性激增,抵消了增加归并路数减少外存 I/O 趟数的收益。
(2) 败者树(Loser Tree)优化¶
为消除 \(k\) 路归并中的比较瓶颈,引入完全二叉树结构——败者树: * 结构设计:叶节点对应 \(k\) 个归并段当前待处理记录,内部节点仅记录左右孩子比对后的“败者”(关键字较大者)所在的归并段序号,比对中的“胜者”(关键字较小者)继续上升与双亲节点中记录的历史败者比对; * 重构复杂度:每次输出一个极值后,从相应归并段补充新记录进入对应的叶节点,仅需沿该叶节点的祖先链单向攀升至根节点,单次调整只需比对 \(\lceil \log_2 k \rceil\) 次; * 总时间优化:将总比较次数降为 \((N - 1) \lceil \log_2 k \rceil\)$ \text{,内部比较时间复杂度优化为} $\(O(N \log_2 k)\)$ \text{,使得内部比较开销与路数} $\(k\) 脱钩。
6. 内部排序八大算法多维横向对比矩阵¶
| 排序算法分类 | 算法名称 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 辅助空间复杂度 | 稳定性 | 比较次数与初始状态相关性 | 每趟产生最终全局位置 |
|---|---|---|---|---|---|---|---|---|
| 插入排序 | 直接插入排序 | \(O(n)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | 稳定 | 相关 | 否 |
| 折半插入排序 | \(O(n \log_2 n)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | 稳定 | 无关(仅移动相关) | 否 | |
| 希尔排序 | \(O(n^{1.3})\) | \(O(n^2)\) | \(O(n^{1.3} \sim n^2)\) | \(O(1)\) | 不稳定 | 相关 | 否 | |
| 交换排序 | 冒泡排序 | \(O(n)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | 稳定 | 相关 | 是 |
| 快速排序 | \(O(n \log_2 n)\) | \(O(n^2)\) | \(O(n \log_2 n)\) | \(O(\log_2 n) \sim O(n)\) | 不稳定 | 相关 | 是 | |
| 选择排序 | 简单选择排序 | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | 不稳定 | 无关 | 是 |
| 堆排序 | \(O(n \log_2 n)\) | \(O(n \log_2 n)\) | \(O(n \log_2 n)\) | \(O(1)\) | 不稳定 | 相关 | 是 | |
| 归并排序 | 二路归并排序 | \(O(n \log_2 n)\) | \(O(n \log_2 n)\) | \(O(n \log_2 n)\) | \(O(n)\) | 稳定 | 相关 | 否 |
| 分配排序 | 基数排序 | \(O(d(n + r))\) | \(O(d(n + r))\) | \(O(d(n + r))\) | \(O(r)\) | 稳定 | 无关 | 否 |
归并排序在八大算法中的独特性质辨析¶
- 时空权衡的极端代表:二路归并排序是主流基于比较的内部排序算法中,唯一同时具备 \(O(n \log_2 n)\)$ \text{稳定时间下界与稳定性的算法。其代价是辅助空间开销高达} $\(O(n)\),无法实现基于数组的原地排序(In-place Sorting);
- 渐进时间与具体比较次数的哲学分野:
- 归并排序的时间复杂度渐进阶与初始排列完全无关,恒为 \(O(n \log_2 n)\);
- 但其具体的关键字比较次数与初始排列高度相关(最好情况为 \(\min(m, n)\)$ \text{,最坏情况为} $\(m + n - 1\));
- 链式存储适配性:在单链表结构下执行归并排序,合并操作只需修改指针指向,辅助空间复杂度可从数组实现的 \(O(n)\)$ \text{降为仅需栈空间的} $\(O(\log_2 n)\)。
三、 近十年真题精讲(2016~2025)¶
【真题 1】2024 年 408 第 10 题 · 有序序列二路归并的关键字总比较次数¶
题目
初始有三个升序序列 (3, 5)、(7, 9)、(6),若按从左至右的次序选择有序序列进行二路归并排序,则关键字之间的总比较次数是( )。
A. 3 B. 4 C. 5 D. 6
【解析】¶
题目明确限定了归并次序:“按从左至右的次序选择有序序列进行二路归并排序”。
初始序列集合为:\(S_1 = (3, 5), S_2 = (7, 9), S_3 = (6)\)。
整个归并过程严格划分为两轮两两归并。
1. 第一轮归并:合并 \(S_1 = (3, 5)\)$ \text{与} $\(S_2 = (7, 9)\)¶
设双指针 \(i\)$ \text{指向} $\(S_1\)$ \text{头部,} $\(j\)$ \text{指向} $\(S_2\) 头部: * 第 1 次比较:比较 \(S_1[0]\)$ \text{与} $\(S_2[0]\),即比对 3 与 7。 由于 \(3 < 7\)$ \text{,输出 3。指针后移,剩余} $\(S_1\)$ \text{为} $\((5)\),\(S_2\)$ \text{为} $\((7, 9)\); * 第 2 次比较:比较 \(S_1[1]\)$ \text{与} $\(S_2[0]\),即比对 5 与 7。 由于 \(5 < 7\)$ \text{,输出 5。指针后移,} $\(S_1\) 序列已全部输出遍历完毕(指针越界); * 提前终止判定(零比较拷贝): 此时 \(S_1\)$ \text{已空,比对扫描循环立即终止!} $\(S_2\)$ \text{中剩余的} $\((7, 9)\) 直接顺序复制到合并缓冲区尾部,无需进行任何关键字比较。 * 第一轮归并产出:合并后序列为 \((3, 5, 7, 9)\); * 第一轮比较次数:\(C_1 = 2\) 次。
2. 第二轮归并:合并新序列 \((3, 5, 7, 9)\)$ \text{与} $\(S_3 = (6)\)¶
设指针 \(i\)$ \text{指向新序列头部,指针} $\(j\)$ \text{指向} $\(S_3\) 头部: * 第 1 次比较:比对 3 与 6。 由于 \(3 < 6\)$ \text{,输出 3。当前剩余} $\((5, 7, 9)\)$ \text{与} $\((6)\); * 第 2 次比较:比对 5 与 6。 由于 \(5 < 6\)$ \text{,输出 5。当前剩余} $\((7, 9)\)$ \text{与} $\((6)\); * 第 3 次比较:比对 7 与 6。 由于 \(7 > 6\)$ \text{,输出 6。此时序列} $\(S_3\) 的全部元素已输出完毕(指针越界); * 提前终止判定(零比较拷贝): 此时 \(S_3\)$ \text{已空,比对循环终止。序列} $\((3, 5, 7, 9)\)$ \text{中剩余的元素} $\((7, 9)\) 直接顺序复制到输出序列末尾,无需继续比较。 * 第二轮归并产出:全局有序序列 \((3, 5, 6, 7, 9)\); * 第二轮比较次数:\(C_2 = 3\) 次。
3. 计算关键字总比较次数¶
对照选项,对应 C 项。
正确答案:C
【真题 2】2022 年 408 第 10 题 · 二路归并操作的功能形式化语义定义¶
题目
使用二路归并排序对含 \(n\)$ \text{个元素的数组} $\(M\) 进行排序时,二路归并操作的功能是( )。
A. 将两个有序表合并为一个新的有序表
B. 将 \(M\) 划分为两部分,两部分的元素个数大致相等
C. 将 \(M\)$ \text{划分为} $\(n\) 个部分,每个部分中仅含有一个元素
D. 将 \(M\) 划分为两部分,一部分元素的值均小于另一部分元素的值
【解析】¶
本题考查二路归并排序算法中归并操作(Merge)的严格概念与核心功能定位。
- 选项 A 正确:
归并(Merge)的科学定义是“将两个或两个以上的有序表组合成一个新的有序表”。在二路归并排序中,二路归并操作(即
Merge函数)的专有功能是将两个在物理上相邻且各自有序的子数组合并为一个局部更大的有序数组。 - 选项 B 错误: “将 \(M\)$ \text{划分为两部分,两部分的元素个数大致相等”描述的是分治法中的划分/分解(Divide)阶段(即计算中点} $\(mid = \lfloor (low + high) / 2 \rfloor\) 并进行递归子问题划分),而非归并操作(Merge)本身的功能。
- 选项 C 错误: “将 \(M\)$ \text{划分为} $\(n\) 个部分,每个部分中仅含有一个元素”描述的是递归划分的递归基(Base Case)状态,即子问题规模降为 1 时的平凡情形。
- 选项 D 错误:
“将 \(M\) 划分为两部分,一部分元素的值均小于另一部分元素的值”描述的是快速排序(Quick Sort)中的核心划分操作(
Partition),该操作以枢轴(Pivot)为基准划分左右元素,二路归并操作不具备该功能。
综上所述,二路归并操作的功能是将两个有序表合并为一个新的有序表。
正确答案:A
【真题 3】2017 年 408 第 10 题 · 归并排序与直接插入排序的综合选型对比¶
题目
在内部排序时,若选择了归并排序而没有选择插入排序,则可能的理由是( )。
I. 归并排序的程序代码更短
II. 归并排序的占用空间更少
III. 归并排序的运行效率更高
A. 仅 II B. 仅 III C. 仅 I, II D. 仅 I, III
【解析】¶
本题对归并排序与直接插入排序的代码复杂度、空间复杂度以及时间运行效率展开全方位横向对比。
- 理由 I 判定错误:
- 直接插入排序的逻辑结构极其简单,仅需使用两层循环(外层遍历元素,内层顺序后移)即可完成,核心代码仅约 5~8 行;
- 归并排序采用分治范式,需要编写递归划分函数以及包含双指针比对、剩余元素复制、辅助数组写回等繁琐逻辑的
Merge函数,代码规模与实现复杂度显著高于直接插入排序。因此,“归并排序代码更短”不符合事实。 - 理由 II 判定错误:
- 直接插入排序是典型的原地排序(In-place),只需要一个常数级的辅助变量用于暂存待插入元素,辅助空间复杂度为 \(O(1)\);
- 归并排序在合并子表阶段,必须申请一个与待排数组同等规模的辅助数组以防止元素覆盖,此外递归调用还需要占用 \(O(\log_2 n)\)$ \text{的递归调用栈,总辅助空间复杂度为} $\(O(n)\)。因此,归并排序占用的内存空间明显多于插入排序。
- 理由 III 判定正确:
- 直接插入排序在平均情况与最坏情况下的时间复杂度为 \(O(n^2)\);
- 归并排序在最好、最坏与平均情况下的时间复杂度恒定为 \(O(n \log_2 n)\);
- 当处理的数据规模 \(n\)$ \text{较大时,} $\(O(n \log_2 n)\)$ \text{的执行时间与指令步数远低于} $\(O(n^2)\)$ \text{(例如当} $\(n = 10^5\)$ \text{时,} $\(n \log_2 n \approx 1.7 \times 10^6\)$ \text{,而} $\(n^2 = 10^{10}\),二者存在数千倍的运行效率鸿沟)。因此选择归并排序的根本理由是其运行效率更高。
综上所述,可能的理由仅有 III。
正确答案:B
四、 核心解题套路与易错陷阱¶
1. 比较次数计算中“一侧耗尽提前终止”陷阱¶
命题人在考察二路归并比较次数时,常设置两个等长或不等长的有序序列让考生计算比较次数。很多考生习惯机械套用公式 \(m + n - 1\),忽略了序列元素大小分布对比较流程的影响。
快速解题规范方法:双指针笔算跟踪法¶
- 画出左右序列:将待合并的两个序列并排写出;
- 指针同步比对:
- 每次圈出当前两指针指向的数字,计比较次数 1 次;
- 较小者“出列”(划掉该数字),对应序列指针右移;
- 关键终止线检测:
- 一旦其中任何一个序列中的数字被全部划掉,立即停笔!
- 此时剩余序列的所有剩余数字无需划圈比对,直接全部追加输出,不再产生任何比较次数。
示例:合并序列 (1, 2, 3) 与 (4, 5, 6)
比较 1 与 4 -> 输出 1 (比较 1 次)
比较 2 与 4 -> 输出 2 (比较 2 次)
比较 3 与 4 -> 输出 3 (比较 3 次)
此时序列一已全部耗尽!比较流程彻底终止。
剩余序列 (4, 5, 6) 零比较直接输出。总比较次数恰为 min(3, 3) = 3 次,远小于 3 + 3 - 1 = 5 次。
2. 归并序列选取次序对总比较次数的影响¶
在类似 2024 年真题的多段归并题型中,题目若改变归并顺序,总体比较次数会剧烈波动: * 若采用从左至右贪心归并: 先归并小段可能导致后续合并时长度膨胀; * 若采用类哈夫曼树归并策略(两两挑选当前长度最短的归并段合并): 类似于带权路径长度(WPL)最小化思想,使短序列尽可能处于归并树的较深层,长序列处于较浅层,能有效减少全局数据搬运与比较次数。
3. 归并趟数与二路归并树高度的概念混淆¶
在选择题计算归并趟数时,极易混淆“趟数”、“递归深度”与“树的高度”: * 归并趟数(Passes):有序段长度由 1 翻倍至 \(n\) 所需的合并轮数,严格公式为: $$ \text{趟数} = \lceil \log_2 n \rceil $$ * 二路归并树高度(Height):若叶子节点(初始单元素段)计为第 1 层,则二路归并树的总高度为: $\(h = \lceil \log_2 n \rceil + 1\)$ * 易错点示例:\(n = 7\)$ \text{时,} $\(\lceil \log_2 7 \rceil = 3\) 趟归并。 - 第 1 趟:两两合并产生 3 个长度为 2 的段和 1 个长度为 1 的段; - 第 2 趟:合并产生 1 个长度为 4 的段和 1 个长度为 3 的段; - 第 3 趟:合并产生 1 个长度为 7 的完全有序段。总趟数确为 3 趟。
4. 稳定性判定条件的“等号陷阱”¶
在算法设计题或代码改错题中,归并排序的稳定性完全维系在 Merge 函数的判定表达式上:
* 稳定实现:if (B[i] <= B[j])。当两子表头部元素相等时,左子表元素先输出,保持了原始相对顺序;
* 不稳定实现:if (B[i] < B[j])。当两元素相等时,触发了 else 分支,右子表元素先输出,导致后出现的元素被移动到了前面,稳定性丧失。
五、 考点速记清单¶
- 核心操作定义:二路归并(Merge)的专有功能是将两个相邻的有序表合并为一个新的有序表。
- 比较次数极值界:长度为 \(m\)$ \text{和} $\(n\) 的两个有序表进行二路归并,关键字之间的比较次数严格满足: $\(\min(m, n) \le C \le m + n - 1\)$ 最好情况(数值完全分离)为 \(\min(m, n)\)$ \text{;最坏情况(元素交替穿插)为} $\(m + n - 1\)。
- 提前终止规则:双指针比对扫描过程中,一旦其中一个子表元素全部输出,另一个子表的剩余所有元素直接顺序拷贝,不再产生任何关键字比较。
- 时空复杂度特征:
- 时间复杂度:在最好、最坏与平均情况下恒为 \(O(n \log_2 n)\),渐进阶与输入排列无关;
- 空间复杂度:需要等长辅助数组与递归调用栈,空间开销严格为 \(O(n)\)。
- 算法稳定性:二路归并排序是稳定的排序算法(依托
B[i] <= B[j]保证相同元素左侧优先输出)。 - 归并趟数与树高:含 \(n\)$ \text{个元素的序列进行二路归并排序,归并总趟数为 } $\(\lceil \log_2 n \rceil\)$ \text{,归并树高度为} $\(\lceil \log_2 n \rceil + 1\)。
- 八大排序综合定位:归并排序是基于比较的内部排序算法中,唯一同时具备 \(O(n \log_2 n)\)$ \text{稳定运行效率与稳定性 的算法,但缺点是辅助空间开销较大(} $\(O(n)\))。