408 高频考点精讲:外部排序(External Sorting)¶
模块归属:数据结构 · 排序
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
- 近十年考查频次:3 次(2016~2025 年:2016#11、2019#11、2023#42)
- 历年总考查频次:3 次
- 出题形式:单项选择题(基础概念定性判断、最佳归并树虚段计算)、综合解答题(置换-选择排序算法动态模拟推演、初始段长度极限分析,分值 10 分)
- 命题特点:
- 考查兼具定性分析、动态模拟及定量代数推导。早期以单项选择题形式考查海量数据排序选型(2016)及严格 \(k\) 叉最佳归并树虚段判定(2019),近年延伸至算法大题,深入考查置换-选择排序工作区的运行机理与极限边界证明(2023)。
- 理论模型与工程性能权衡紧密结合。考查重点集中在外存 I/O 访问代价模型、多路平衡归并的压深机制、败者树(Loser Tree)对内部比较复杂度的优化证明、严格 \(k\) 叉树的代数整除约束,以及置换-选择排序动态吞吐特性的推导。
二、 具体考察内容¶
1. 外部排序两阶段架构与 I/O 次数代价模型¶
(1) 基本概念与设计动机¶
在处理海量数据文件(例如数十吉字节至数十太字节级别)时,数据规模远超计算机主存的物理容量,无法将待排序数据一次性完整加载到内存中进行常规内部排序。外部排序(External Sorting)即指针对外存(如机械硬盘、固态硬盘)中海量数据进行的排序过程。
由于外存属于块设备(Block Device),机械硬盘寻道延迟及固态硬盘块读写延迟比内存访问延迟高出 \(3 \sim 5\) 个数量级,外部排序的总时间开销主要取决于外存 I/O(读/写)次数。因此,外部排序算法设计的核心目标是在有限的内存缓冲区约束下,最大限度减少外存数据块的读写总次数。
(2) 两阶段处理框架¶
外部排序普遍采用“两阶段归并排序(Two-Phase Multiway Merge Sort)”架构:
- 第一阶段:生成初始归并段(Run Generation)
分批将外存中的未排序数据读入内存,利用内部排序算法(如快速排序、置换-选择排序等)将其整理为若干局部有序的数据片段,随后写回外存。这些在外存上生成的有序片段称为初始归并段(Initial Runs)。 - 第二阶段:多路归并(Multiway Merging)
在内存中开辟输入缓冲区与输出缓冲区,逐趟将若干个归并段合并为更长的归并段,反复迭代,直至最终将所有数据合并为单一全局有序文件。
外存海量无序数据
│
▼ [阶段一:读入内存内排,写回外存]
r 个初始归并段(Runs)
│
▼ [阶段二:利用内存缓冲区进行多路平衡归并]
第一趟归并 ──> 第二趟归并 ──> ... ──> 第 S 趟归并
│
▼
外存全局单一有序文件
(3) 外存 I/O 次数定量数学模型¶
设待排序文件共有 \(n\)$ \text{个记录,占用外存} $\(N\)$ \text{个物理块;第一阶段生成了} $\(r\)$ \text{个初始归并段;第二阶段采用} $\(k\)$ \text{路平衡归并,共执行} $\(S\) 趟归并。
-
生成初始归并段的 I/O 次数:
整个文件必须完整读入内存一次,生成的所有初始段必须完整写出到外存一次: $\(\text{I/O}_{\text{phase1}} = N_{\text{read}} + N_{\text{write}} = 2N\)$ -
每趟归并的 I/O 次数:
每一趟归并都需要遍历参与该趟的所有初始归并段块,并将合并后的有序数据完整写入外存。因此,只要所有数据均参与该趟归并,每一趟归并同样涉及 \(N\)$ \text{块的读入与} $\(N\) 块的写出: $\(\text{I/O}_{\text{per\_pass}} = N_{\text{read}} + N_{\text{write}} = 2N\)$ -
归并趟数 \(S\) 的计算:
每经过一趟 \(k\)$ \text{路平衡归并,归并段数量变为原来的} $\(1/k\)$ \text{。设初始段数为} $\(r\),当段数缩减至 1 时排序完成: $\(S = \lceil \log_k r \rceil\)$ -
外部排序总 I/O 读写块数: $\(\text{Total I/O} = 2N + 2N \cdot S = 2N \left(1 + \lceil \log_k r \rceil\right)\)$
由上述代数式可知,降低总 I/O 开销的核心优化途径有二: 1. 增大归并路数 \(k\)$ \text{:提升归并树分支度,从而降低对数高度} $\(\lceil \log_k r \rceil\)$ \text{(减少归并趟数} $\(S\)); 2. 减少初始归并段数 \(r\)$ \text{:增加每个初始段的平均长度,从而在分子端压缩} $\(\log_k r\) 的值。
2. 多路平衡归并与内部比较开销的矛盾¶
在多路平衡归并中,若在内存中开辟 \(k\)$ \text{个输入缓冲区(分别对应} $\(k\)$ \text{个归并段)与 1 个输出缓冲区。归并过程如下:从} $\(k\) 个输入缓冲区的当前关键字中选出全局最小关键字,送入输出缓冲区;若输出缓冲区存满,则写回外存;若某个输入缓冲区读空,则从对应外存归并段中调入后续物理块。
(1) 普通线性比较的性能瓶颈¶
若采用普通的逐一比较选择最小关键字: * 在 \(k\)$ \text{个输入段的段头元素中选出最小值,需要进行} $\(k - 1\) 次两两比较; * 设文件共有 \(n\)$ \text{个记录,每趟归并将} $\(n\)$ \text{个记录全部输出,需执行} $\(n - 1\) 次选小操作,单趟归并的内部比较次数为: $\(C_{\text{pass}} = (n - 1)(k - 1)\)$ * \(S\) 趟归并的内部比较总次数为: $$C_{\text{total}} = S \cdot (n
-
1)(k
-
1) = \lceil \log_k r \rceil \cdot (n
-
1)(k
-
1) \approx (n
-
1)\ln r \cdot \frac{k
-
1}{\ln k}$$
(2) 矛盾分析¶
当增大归并路数 \(k\) 时:
* 归并趟数 \(S = \lceil \log_k r \rceil\) 随之减少,外存 I/O 次数单调下降;
* 函数 \(f(k) = \frac{k - 1}{\ln k}\)$ \text{随着} $\(k\)$ \text{的增大而严格单调递增,内部比较总次数} $\(C_{\text{total}}\) 显著增加。
当 \(k\) 过大时,CPU 进行内部比较的时间开销急剧恶化,抵消外存 I/O 减少所带来的性能收益。为打破该性能瓶颈,必须引入败者树(Loser Tree)。
3. 败者树(Loser Tree)原理与比较次数优化推导¶
(1) 败者树的数据结构定义¶
败者树是树形选择排序(Tournament Tree)的一种变体,属于完全二叉树结构:
* 叶子节点:包含 \(k\)$ \text{个叶子节点,编号为} $\(0 \sim k-1\)$ \text{,分别存放} $\(k\) 个归并段当前的段头待选记录关键字。
* 分支节点(内部节点):包含 \(k-1\)$ \text{个节点,编号为} $\(1 \sim k-1\)。每个分支节点不记录获胜者,而是记录该层比赛中失败者(即关键字较大者)来自哪个归并段的编号。
* 树顶节点:在根节点上方单独设立一个单元 ls[0],用于记录整棵树最终比赛的胜者(即全局最小关键字所在的归并段编号)。
ls[0] = 3 (全局胜者:段 3)
│
ls[1] (记录该处败者)
/ \
ls[2] ls[3]
/ \ / \
b[0] b[1] b[2] b[3] (叶子节点:4 个归并段的段头元素)
(2) 胜者树与败者树的机制对比¶
- 胜者树(Winner Tree):内部节点保存两两比较中的胜者。当某一叶子节点更新后,沿树向上重构路径时,必须获取其父节点以及兄弟节点的当前胜者进行二次比对。由于需要动态定位兄弟节点,在数组存储形态下的指针寻址开销较大。
- 败者树(Loser Tree):内部节点直接存储败者,胜者携带胜出标记继续向上晋级。当更新叶子节点后,新元素只需沿着父节点指针单向向上攀爬,每上一层仅与当前父节点中记录的“原败者”进行 1 次比较:
- 较小者(新胜者)继续向上攀爬;
- 较大者(新败者)驻留在当前分支节点,替代原有的败者编号。 整个调整路径仅涉及单一父节点链,完全无需访问兄弟节点,硬件缓存局部性更优,控制逻辑简洁。
(3) 比较复杂度的渐近推导¶
- 树的高度:包含 \(k\)$ \text{个叶子节点的完全二叉树,其高度为} $\(\lceil \log_2 k \rceil\)。
- 单次选小开销:当输出全局最小值并从相应归并段调入下一个新关键字后,从该叶子节点向根节点调整,整条链路上共有 \(\lceil \log_2 k \rceil\) 个分支节点。在每个分支节点上仅执行 1 次比较。 因此,每选出一个最小记录,内部比较次数仅为: $\(C_{\text{select}} = \lceil \log_2 k \rceil\)$
- 内部比较总次数: $\(C_{\text{total\_loser}} = S \cdot n \lceil \log_2 k \rceil = \lceil \log_k r \rceil \cdot n \lceil \log_2 k \rceil = \left\lceil \frac{\log_2 r}{\log_2 k} \right\rceil \cdot n \lceil \log_2 k \rceil \approx n \log_2 r\)$ 结论:引入败者树后,内部比较总次数 \(C_{\text{total\_loser}}\)$ \text{近似为} $\(n \log_2 r\)$ \text{,该值在渐近意义上与归并路数} $\(k\)$ \text{完全无关。系统可以根据内存缓冲区配额尽可能选取更大的} $\(k\),从而以恒定的内部计算开销最大化压低外存 I/O 趟数。
4. 置换-选择排序(Replacement-Selection Sort)与初始段生成¶
常规内部排序(如快速排序、归并排序)受内存工作区容量限制,若工作区最多容纳 \(m\)$ \text{个记录,则单次只能生成长度为} $\(m\)$ \text{的初始归并段。若待排文件有} $\(N\)$ \text{个记录,初始段数固定为} $\(r = \lceil N/m \rceil\)。
置换-选择排序突破了该限制,能够在容量为 \(m\)$ \text{的内存工作区中生成平均长度达到} $\(2m\)$ \text{ 的初始归并段,使初始段数减少约} $\(50\%\)。
(1) 算法运行机制¶
设内存工作区为 \(WA\)$ \text{,容量为} $\(m\)$ \text{;输入文件为} $\(FI\)$ \text{,输出文件为} $\(FO\):
1. 初始化:从 \(FI\)$ \text{中顺序读入} $\(m\)$ \text{个记录填满工作区} $\(WA\)。
2. 选小操作:利用败者树(或优先队列堆结构)在 \(WA\) 中选出尚未被冻结的记录中关键字最小的记录,记为当前段的 MINIMAX。
3. 输出与读入:将 MINIMAX 输出至当前归并段;随后若 \(FI\)$ \text{未空,从} $\(FI\)$ \text{读入下一个记录} $\(x\) 填补该空位。
4. 冻结(Freeze)状态判断:
- 若 \(x.key \ge \text{MINIMAX}.key\):新读入记录大于等于当前段最后一个输出值,说明它能够保持当前归并段的单调递增性,将其归入当前归并段,保持解冻状态,继续参与当前段后续选小;
- 若 \(x.key < \text{MINIMAX}.key\):新读入记录小于当前段最新输出值,若输出将破坏当前段的递增单调性,因此必须将其**标记为冻结()暂时挂起,不参前归并段的后续选小,留待下一个归并段处理。
5. 归并段终止**:当工作区中的所有 \(m\) 个记录均被冻结(即不存在任何未冻结记录)时,当前归并段输出结束。
6. 解冻与换段:将工作区中全部 \(m\) 个记录的冻结标记清除(全部解冻),开启下一个初始归并段,重复上述步骤,直至文件所有记录处理完毕。
[工作区 WA (容量 m)] ──(选出未冻结最小 MINIMAX)──> 输出到当前归并段 FO
▲ │
│ (新记录 x 填补空位) │
[输入文件 FI] ▼
若 x.key >= MINIMAX.key ──> 正常参与当前段 (未冻结)
若 x.key < MINIMAX.key ──> 标记冻结 (*),挂起归入下一段
(2) 平均段长 2m 的数学证明(雪融模型 / Snowplow Argument)¶
Donald Knuth 在《计算机程序设计艺术》(TAOCP)第 3 卷中提出了经典的“扫雪机模型”,严格论证了置换-选择排序在均匀随机分布输入下的平均段长:
- 模型构建: 将输入数据序列的关键字视作在区间 \([0, 1)\) 上连续均匀落下的雪花。 将容量为 \(m\) 的工作区视作一辆在周长为 1 的环形环道上以恒定速率逆时针行驶的扫雪机。 扫雪机车厢的最大载雪容量为 \(m\)。输入数据源源不断送入,扫雪机扫起前方雪花并即时卸载到外存文件。
- 物理映射:
- 扫雪机当前所在的位置对应当前输出的关键字值
MINIMAX; - 落在扫雪机前进方向前方的雪花,对应新输入记录 \(x \ge \text{MINIMAX}\),可被扫雪机在当前圈次直接铲走(属于当前归并段);
- 落在扫雪机后方的雪花,对应新输入记录 \(x < \text{MINIMAX}\),在当前圈次无法被铲起,只能积压在地面上等待扫雪机在下一圈处理(被冻结归入下一段)。
- 微积分推导: 设整个系统达到动态平衡。在扫雪机运行一整圈(生成一个完整归并段)的过程中:
- 圈次起始时,环道上积攒了上一圈遗留的雪量,积雪总量为工作区满载容量 \(m\);
- 在扫雪机行进一圈的单位时间内,新落入环道上的总雪量记为 \(L_{\text{new}}\);
- 因为雪花在时间与空间上均呈现均匀分布,扫雪机扫过某一特定路段时,平均只能扫到该路段在扫雪机经过前落下的雪。由于扫雪机匀速行进,落入扫雪机前方并被其实时铲走的雪量期望值恰好为新落雪量的一半: $\(L_{\text{current}} = \frac{1}{2} L_{\text{new}}\)$
- 扫雪机一圈铲出的总雪量(即一个归并段的总长度 \(L\))等于初始积雪与行进中实时铲走雪量之和: $\(L = m + \frac{1}{2} L_{\text{new}}\)$
- 稳定状态下,系统流入速率等于流出速率,一圈内新落下的总雪量必然等于该圈被铲出的雪量,即 \(L_{\text{new}} = L\)。
- 代入方程求解: $\(L = m + \frac{1}{2} L \implies \frac{1}{2} L = m \implies L = 2m\)$
- 结论:在输入关键字序列呈随机独立均匀分布的前提下,置换-选择排序生成的初始归并段的数学期望长度为 \(2m\)。
(3) 段长极值边界分析¶
对于总记录数为 \(n\)$ \text{、工作区容量为} $\(m\)(\(n > m > 0\))的任意输入序列:
* 最大值 \(L_{\max} = n\):
当输入文件原本已经单调非递减(正序)时,每次读入的新关键字 \(x\)$ \text{必然满足} $\(x \ge \text{MINIMAX}\)$ \text{。工作区中永远不会出现冻结记录,整篇文件的所有} $\(n\)$ \text{个记录将在同一个初始段中一次性输出完毕,生成单一长度为} $\(n\) 的初始归并段。
* 最小值 \(L_{\min} = m\):
当输入文件在读满初始工作区后,后续读入的记录全部严格小于工作区中当前最小元素(例如后续序列整体呈逆序或者数值骤降),则新读入的每个记录均因 \(x < \text{MINIMAX}\)$ \text{而立即被冻结。原工作区内的} $\(m\)$ \text{个记录输出完毕后,工作区内全部} $\(m\)$ \text{个记录均处于冻结状态,当前归并段被迫终止。因此段长的理论最小值为工作区容量} $\(m\)。
5. 最佳归并树(严格 k 叉哈夫曼树)与虚段补充¶
(1) 最佳归并树的数学本质¶
各初始归并段的长度通常不同(特别是由置换-选择排序生成时)。进行 \(k\)$ \text{路平衡归并时,归并过程可以用一棵} $\(k\) 叉树进行建模: * 树的叶子节点表示各个初始归并段,叶子的权值 \(w_i\) 代表该归并段包含的物理块数; * 树的分支节点表示归并产生的新段,其权值等于各子节点权值之和; * 根节点代表最终生成的全局有序文件; * 叶子节点所在的深度 \(l_i\) 代表该归并段参与归并的趟数。
归并过程中外存 I/O 读写块数正比于树的带权路径长度(WPL): $\(\text{WPL} = \sum_{i=1}^{r} w_i \times l_i\)$ 为使总 I/O 读写代价达到最小,归并树必须是一棵带权路径长度最小的 \(k\)$ \text{叉树,即 } $\(k\)$ \text{叉最佳归并树(} $\(k\)-way Huffman Tree)。
(2) 严格 k 叉树的代数整除约束¶
在理想的最佳归并树中,每个分支节点都必须拥有 \(k\)$ \text{个子节点(即每次合并均能凑满} $\(k\)$ \text{路),这类归并树称为严格} $\(k\) 叉树。
设叶子节点数(初始归并段数)为 \(n_0\)$ \text{,度为} $\(k\)$ \text{的分支节点数为} $\(n_k\)$ \text{,不存在度数在} $\(1 \sim k-1\)$ \text{之间的分支节点(即} $\(n_1 = n_2 = \dots = n_{k-1} = 0\)): * 树的总结点数为: $\(N = n_0 + n_k\)$ * 树的总边数(分支总数)为: $\(E = N - 1 = n_0 + n_k - 1\)$ * 从分支引出角度,每个度为 \(k\)$ \text{的节点引出} $\(k\) 条边,叶节点不引出边: $\(E = k \cdot n_k\)$ * 联立上述两式: $$k \cdot n_k = n_0 + n_k
-
1 \implies (k
-
1) n_k = n_0
-
1 \implies n_k = \frac{n_0
-
1}{k
-
1}$$
因为分支节点数 \(n_k\)$ \text{必须为正整数,故严格} $\(k\) 叉树存在的充分必要条件为: $\((n_0 - 1) \bmod (k - 1) = 0\)$
(3) 虚段补充公式推导¶
若实际初始归并段数 \(n_0\)$ \text{无法被} $\(k-1\) 整除,即: $$(n_0
-
1) \bmod (k
-
1) = R \ne 0 \quad (1 \le R < k
-
1)$$ 这表明归并节点无法全部满载,必然存在某个分支节点的度数不足 \(k\)。如果任由度数不足的分支节点出现在归并的最后阶段(靠近根部),会导致较长的大归并段多参与一次归并,严重增加 I/O 代价。
为确保满足最优贪心性质,必须人为补充若干长度为 0 的“虚段(Dummy Runs)”(即权值为 0 的叶子节点)。 设需补充的虚段数量为 \(u\)(\(0 \le u < k - 1\)): 补充后新的叶节点数变为 \(n_0 + u\),必须严格满足整除关系: $\((n_0 + u - 1) \bmod (k - 1) = 0\)$ 即: $\((R + u) \bmod (k - 1) = 0\)$
由此得出计算虚段数 \(u\) 的标准数学公式: $$ \text{u = \begin{cases} 0, & \text{若 } (n_0
-
1) \bmod (k
-
1) = 0 \ (k
-
1)
-
[(n_0
-
1) \bmod (k
-
1)], & \text{若 } (n_0
-
1) \bmod (k
-
1) \ne 0 \end{cases}} $$
统一写为模运算形式: $$u = \left( (k
-
1)
-
\left((n_0
-
1) \bmod (k
-
1)\right) \right) \bmod (k
-
1)$$
(4) 虚段的合并原则¶
由于虚段的权值为 0,在按照哈夫曼树贪心选择最小权值合并时,虚段必须与权值最小的若干实际初始归并段一起,在第一轮归并中优先被合并。 这样可以保证虚段处于树的最深层(叶节点深度最大),从而使长度较大的实际归并段处于较浅层,实现全局 WPL 最小化。
三、 近十年真题精讲(2016~2025)¶
【真题 1】2023 年 408 第 42 题 · 置换-选择排序算法运行与极限分析¶
题目
对含有 \(n\)(\(n > 0\)$ \text{)个记录的文件进行外部排序,采用置换-选择排序生成初始归并段时需要使用一个工作区,工作区中能保存} $\(m\) 个记录。请回答下列问题:
(1) 如果文件中包含 19 个记录,其关键字是 51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100;当 \(m=4\) 时,可以生成几个初始归并段,各是什么?
(2) 对任意的 \(m\)$ \text{和} $\(n\)(\(n > m > 0\)),生成的第一个初始归并段的长度最大值和最小值分别是多少?
【解析】¶
(1) 算法执行追踪(工作区容量 \(m = 4\))
初始状态:从输入序列读入前 4 个元素填满工作区:
\(\text{WA} = \{51, 94, 37, 92\}\)$ \text{,待读入序列为} $\([14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100]\)。
- 生成归并段 1:
- 当前未冻结最小值为 37,输出 37;读入 14。因 \(14 < 37\)$ \text{,14 被冻结(记为} $\(14^*\)$ \text{)。工作区为} $\(\{51, 94, 14^*, 92\}\)。
- 当前未冻结最小值为 51,输出 51;读入 63。因 \(63 \ge 51\)$ \text{,63 未冻结。工作区为} $\(\{63, 94, 14^*, 92\}\)。
- 当前未冻结最小值为 63,输出 63;读入 15。因 \(15 < 63\)$ \text{,15 被冻结(记为} $\(15^*\)$ \text{)。工作区为} $\(\{15^*, 94, 14^*, 92\}\)。
- 当前未冻结最小值为 92,输出 92;读入 99。因 \(99 \ge 92\)$ \text{,99 未冻结。工作区为} $\(\{15^*, 94, 14^*, 99\}\)。
- 当前未冻结最小值为 94,输出 94;读入 48。因 \(48 < 94\)$ \text{,48 被冻结(记为} $\(48^*\)$ \text{)。工作区为} $\(\{15^*, 48^*, 14^*, 99\}\)。
-
当前未冻结最小值为 99,输出 99;读入 56。因 \(56 < 99\)$ \text{,56 被冻结(记为} $\(56^*\)$ \text{)。工作区为} $\(\{15^*, 48^*, 14^*, 56^*\}\)。 此时工作区内 4 个元素全部被冻结,归并段 1 生成完毕。
归并段 1 内容:37, 51, 63, 92, 94, 99(长度为 6)。 -
生成归并段 2:
全部解除冻结,工作区为 \(\{15, 48, 14, 56\}\)$ \text{,待读入序列为} $\([23, 60, 31, 17, 43, 8, 90, 166, 100]\)。 - 当前未冻结最小值为 14,输出 14;读入 23。因 \(23 \ge 14\)$ \text{,23 未冻结。工作区为} $\(\{15, 48, 23, 56\}\)。
- 当前未冻结最小值为 15,输出 15;读入 60。因 \(60 \ge 15\)$ \text{,60 未冻结。工作区为} $\(\{60, 48, 23, 56\}\)。
- 当前未冻结最小值为 23,输出 23;读入 31。因 \(31 \ge 23\)$ \text{,31 未冻结。工作区为} $\(\{60, 48, 31, 56\}\)。
- 当前未冻结最小值为 31,输出 31;读入 17。因 \(17 < 31\)$ \text{,17 被冻结(记为} $\(17^*\)$ \text{)。工作区为} $\(\{60, 48, 17^*, 56\}\)。
- 当前未冻结最小值为 48,输出 48;读入 43。因 \(43 < 48\)$ \text{,43 被冻结(记为} $\(43^*\)$ \text{)。工作区为} $\(\{60, 43^*, 17^*, 56\}\)。
- 当前未冻结最小值为 56,输出 56;读入 8。因 \(8 < 56\)$ \text{,8 被冻结(记为} $\(8^*\)$ \text{)。工作区为} $\(\{60, 43^*, 17^*, 8^*\}\)。
- 当前未冻结最小值为 60,输出 60;读入 90。因 \(90 \ge 60\)$ \text{,90 未冻结。工作区为} $\(\{90, 43^*, 17^*, 8^*\}\)。
- 当前未冻结最小值为 90,输出 90;读入 166。因 \(166 \ge 90\)$ \text{,166 未冻结。工作区为} $\(\{166, 43^*, 17^*, 8^*\}\)。
-
当前未冻结最小值为 166,输出 166;读入 100。因 \(100 < 166\)$ \text{,100 被冻结(记为} $\(100^*\)$ \text{)。工作区为} $\(\{100^*, 43^*, 17^*, 8^*\}\)。 此时工作区内 4 个元素全部被冻结,归并段 2 生成完毕。
归并段 2 内容:14, 15, 23, 31, 48, 56, 60, 90, 166(长度为 9)。 -
生成归并段 3:
全部解除冻结,工作区为 \(\{100, 43, 17, 8\}\),输入文件已经全部读完,无后续元素。 按从小到大依次选出输出:8, 17, 43, 100。
归并段 3 内容:8, 17, 43, 100(长度为 4)。
总共生成 3 个初始归并段。
(2) 第一个初始归并段长度的极值推导
* 最大值:\(n\)
若输入文件的 \(n\)$ \text{个记录原本已经按升序排列(或单调非递减),则在生成第一个段的过程中,每次新读入的关键字均大于等于刚刚输出的关键字,记录永远不会被冻结。整个文件所有} $\(n\)$ \text{个记录将在第一个归并段中全部输出,因此最大长度为} $\(n\)。
* 最小值:\(m\)
若输入文件在读入前 \(m\)$ \text{个记录填满工作区后,后续读入的记录全部严格小于工作区中当前输出的最小值(例如前} $\(m\)$ \text{个记录非常大,后续元素极小),则后续进入工作区的记录将立刻被全数冻结。工作区内原有的} $\(m\)$ \text{个记录输出完毕后,所有元素均处于冻结状态,段即刻终止。因此最小长度为工作区容量} $\(m\)。
【正确答案】¶
(1) 共生成 3 个初始归并段,各段内容为:
第一段:37, 51, 63, 92, 94, 99
第二段:14, 15, 23, 31, 48, 56, 60, 90, 166
第三段:8, 17, 43, 100
(2) 生成的第一个初始归并段长度的最大值是 \(n\)$ \text{,最小值是} $\(m\)。
【真题 2】2019 年 408 第 11 题 · 最佳归并树虚段计算¶
题目
设外存上有 120 个初始归并段,进行 12 路归并时,为实现最佳归并,需要补充的虚段个数是( )。
A. 1 B. 2 C. 3 D. 4
【解析】¶
- 题型识别与代数条件:
本题考查 12 路最佳归并树(即严格 12 叉哈夫曼树)的构造条件。
已知初始归并段数(叶子节点数)\(n_0 = 120\)$ \text{,归并路数} $\(k = 12\)。 - 严格 \(k\) 叉树整除条件验证:
在严格 \(k\)$ \text{叉树中,仅存在度为 0 的叶节点与度为} $\(k\) 的分支节点,必须满足: $\((n_0 - 1) \bmod (k - 1) = 0\)$ 代入本题数值:\(k - 1 = 12 - 1 = 11\)。
计算余数: $\((120 - 1) \bmod 11 = 119 \bmod 11\)$ 由于 \(119 = 11 \times 10 + 9\)$ \text{,余数} $\(R = 9 \ne 0\)。
这表明 120 个初始归并段无法直接构成严格 12 叉树,必须补充虚段。 - 计算虚段个数 \(u\):
设补充的虚段数为 \(u\)(\(0 \le u < 11\)),使新的叶节点数满足整除约束: $\((119 + u) \bmod 11 = 0 \implies (9 + u) \bmod 11 = 0\)$ 由于 \(0 \le u < 11\),解得: $\(u = 11 - 9 = 2\)$ 故需要补充 2 个权值为 0 的虚段。
【选项逐项辨析】¶
- A 选项(1 个):若补 1 个虚段,\((119 + 1) \bmod 11 = 120 \bmod 11 = 10 \ne 0\),不满足严格 12 叉树条件,错误。
- B 选项(2 个):若补 2 个虚段,\((119 + 2) \bmod 11 = 121 \bmod 11 = 0\),恰好构成度均为 12 的分支节点,正确。
- C 选项(3 个):若补 3 个虚段,\((119 + 3) \bmod 11 = 1 \ne 0\),错误。
- D 选项(4 个):若补 4 个虚段,\((119 + 4) \bmod 11 = 2 \ne 0\),错误。
正确答案:B
【真题 3】2016 年 408 第 11 题 · 海量数据外部排序选型¶
题目
对 10TB 的数据文件进行排序,应使用的方法是( )。
A. 希尔排序 B. 堆排序 C. 快速排序 D. 归并排序
【解析】¶
- 题干核心约束分析:
待排数据规模为 10TB。当前主流计算机的主存(RAM)物理容量通常在数十 GB 至数百 GB 之间,即便对于大型服务器,10TB 数据量也远远超出主存物理容量,数据必须常驻在外存(磁盘阵列或高容量 SSD)中。 - 算法属性辨析:
- 希尔排序(Shell Sort):基于跨步插入的内部排序算法,需要高频随机访问内存数组,在外存中由于磁盘寻道延迟巨大,不可行。
- 堆排序(Heap Sort):基于完全二叉树父子索引(\(2i\)$ \text{与} $\(2i+1\))的跳跃访问,访问局部性极差,在外存中会导致剧烈的随机 I/O 抖动。
- 快速排序(Quick Sort):虽然具有较好的局部性,但其双向指针扫描与递归划分要求全量数据常驻寻址空间,无法直接在有限内存下对 10TB 外存文件完成全量排序。
- 归并排序(Merge Sort):归并操作具有优异的顺序流式读写(Sequential Streaming I/O)特性。在第一阶段生成初始段后,第二阶段仅需维持固定大小的顺序读写缓冲区即可完成多路合并,是处理外存海量数据文件排序的唯一标准体系(即外部多路平衡归并排序)。
【选项逐项辨析】¶
- A、B、C 均为典型内部排序算法,无法突破内存物理容量上限,直接在外存上运行时性能崩溃甚至无法执行。
- D 是外部排序的核心骨干框架,故必须选用归并排序。
正确答案:D
四、 核心解题套路与易错陷阱¶
1. 核心解题套路¶
(1) 最佳归并树虚段计算“三步法”¶
- 第一步:提取参数:明确叶节点数 \(n_0\)$ \text{(初始归并段数)及归并路数} $\(k\)。
- 第二步:求模运算:计算 \((n_0 - 1) \bmod (k - 1) = R\)。
- 第三步:分类判定:
- 若 \(R = 0\)$ \text{:无需补充虚段,} $\(u = 0\);
- 若 \(R \ne 0\)$ \text{:需补充虚段数} $\(u = (k - 1) - R\)。
(2) 置换-选择排序手工模拟“四栏表格法”¶
在草稿纸上模拟置换-选择排序算法时,建议建立如下跟踪表格以杜绝推导失误:
| 步骤 | 当前段输出 (MINIMAX) | 新读入元素 \(x\)$ \text{ | 冻结判定 (} $\(x < \text{MINIMAX}\)$ \text{?) | 工作区剩余状态 (标记} $\(*\)) |
|---|---|---|---|---|
| 1 | 选出未冻结最小 | 填补空位 | 比较大小打标 | 更新工作区 |
- 当工作区中标记 \(*\)$ \text{的元素数量达到} $\(m\)$ \text{时,立即划定当前段结束,进入下一行全部解除} $\(*\),开启新段。
(3) 外部排序 I/O 读写量综合计算标准范式¶
若题目给出文件总块数 \(N\)$ \text{、初始段数} $\(r\)$ \text{、归并路数} $\(k\): 1. 算归并趟数:\(S = \lceil \log_k r \rceil\); 2. 算总 I/O 读写块数:\(\text{Total I/O} = 2N \times (1 + S)\); 3. 注意审题:若题目问“归并阶段的 I/O 次数”,则不包含初始段生成的 \(2N\)$ \text{,即仅为} $\(2NS\)$ \text{;若问“外部排序全过程总 I/O 次数”,必须计入初始段生成的} $\(2N\)。
2. 易错陷阱排查¶
-
陷阱 1:虚段计算错将 \((n_0 - 1)\)$ \text{写成} $\(n_0\)
错误公式:$u = (k -
1)
-
(n_0 \bmod (k
-
1))\(。 *病因剖析*:树的度数定理建立在边数等于顶点数减 1 的代数基础上,\)E = N
-
1 = n_0 + n_k
-
1 = k \cdot n_k$$ \text{。公式必须是} $$n_0
-
1$$ \text{。若直接使用} $\(n_0 \bmod (k-1)\) 计算,将导致算出的虚段数完全错误。
-
陷阱 2:整除情形下强行补充虚段
病因剖析:当 $(n_0 -
1) \bmod (k
-
1) = 0$$ \text{时,初始段数已能够完美凑满所有分支节点,所需虚段数为 0。若机械使用} $$(k-1)
-
0 = k-1$,会平白多出一整层无意义的纯虚段合并。
-
陷阱 3:混淆败者树的分支节点存储内容
病因剖析:败者树的分支节点存放的是失败者来自哪个归并段的段号,而不是败者关键字本身,更不是胜者编号。整棵树的最终胜者存放在树根之上的专用单元ls[0]中。 -
陷阱 4:误判置换-选择排序当前段终止时刻
病因剖析:只要工作区中还有一个元素未被冻结,当前归并段就不能终止!绝不能因为新读入的元素被冻结就停止输出,必须一直选小输出,直至工作区内所有 \(m\) 个元素全部处于冻结状态(或输入已耗尽且工作区全部排空)方可结束当前段。
五、 考点速记清单¶
- 归并趟数公式:\(S = \lceil \log_k r \rceil\)(\(r\)$ \text{为初始段数,} $\(k\) 为归并路数)。
- 总外存 I/O 块数:\(\text{Total I/O} = 2N(1 + \lceil \log_k r \rceil)\)$ \text{(第一阶段生成初始段耗费} $\(2N\)$ \text{,第二阶段每趟归并耗费} $\(2N\))。
- 败者树核心价值:将 \(k\)$ \text{路归并选出最小关键字的比较次数从} $\(k - 1\)$ \text{压缩至} $\(\lceil \log_2 k \rceil\)$ \text{。整趟归并的内部比较总开销与归并路数} $\(k\) 无关。
- 置换-选择排序期望段长:平均段长为 \(2m\)(\(m\)$ \text{为工作区容量);段长极值区间为} $\([m, n]\)。
- 冻结判定法则:新读入关键字 \(x < \text{MINIMAX}\) 时立即冻结;工作区全部冻结时段终止。
-
最佳归并树虚段公式: $$u = \left( (k
-
1)
-
\left((n_0
-
1) \bmod (k
-
1)\right) \right) \bmod (k
-
1)$$
- 虚段归并次序:虚段权值为 0,在最佳归并树中必须最优先参与第一轮归并。