外部排序

真题练习：可在站内题库按“外部排序”知识点筛选。

外部排序的重点是理解初始归并段生成与多路归并两个过程，尤其要能跟踪置换选择排序中记录的输出、冻结与解冻。

外部排序

当待排序的数据量大到无法一次性全部装入内存时，就必须采用 外部排序。外部排序的基本思路是：先将整个数据集划分成若干能够装入内存的子块，对每个子块在内存中完成内部排序；随后再把这些已排序的子块逐步合并，最终得到整体有序的结果。这样既克服了内存容量的限制，又能高效地对海量数据完成排序。

外部排序的整体过程通常可以划分为两个关键阶段：

1. 生成初始归并段 先采用 置换选择排序 对原始的无序文件进行扫描。置换选择能够在一次扫描中尽可能长地生成有序子文件，这些子文件即称为 初始归并段。每个归并段都是内部有序的，且长度尽量大，以减少后续合并的轮数。

2. 多路归并 将所有 初始归并段 以多路归并的方式逐步合并。每一次归并都会把若干归并段合并成一个更长的有序段，重复此过程直至只剩下一个完整的有序文件，从而得到最终的排序结果。

通过上述两步，外部排序能够在 磁盘与内存之间 高效地完成大规模数据的排序。

置换选择排序

置换选择排序（Replacement Selection Sort）是 外部排序 的一个步骤，用于生成 初始归并段，其核心功能是在 内存缓冲区 有限的情况下，尽可能地生成较长的 初始归并段。

置换选择排序 通过维护一个 工作区 来实现这一目标，工作区是一个 小根堆。

其算法步骤如下：

1. 初始化：
   • 将待排序文件中的前 M 个记录读入 工作区，建立一个 最小堆（M 为 工作区 的大小）。
2. 生成归并段：
   • 判断是否有 初始归并段
     • 如果不存在任何 初始归并段 的话，创建一个 初始归并段，并添加 工作区 中的最小元素加入其中。
     • 否则将 工作区 中的元素与上一个 初始归并段 的最大值 MAXV 进行比较。
       • 如果工作区中不存在键值 $\ge MAXV$ 的未冻结记录，则结束当前归并段，解冻工作区中的记录并创建新的归并段。
       • 否则，从所有未冻结且键值 $\ge MAXV$ 的记录中选择最小者，追加到当前归并段末尾。
   • 每输出一个记录，就从输入文件读取下一个值补入工作区；若该值小于当前 $MAXV$，将它冻结到下一归并段，否则它仍可参与当前归并段。

置换选择排序的核心思想如下：

• 判断工作区：如果工作区中所有记录的键值都小于当前输出文件（即已生成的有序段）中最后一个记录的键值，则需要新建一个输出文件，并将这些记录写入该文件，开启新的有序段。
• 继续合并：如果工作区中存在键值不小于当前输出文件末尾记录的记录，则 不断将这些记录追加到已有的输出文件中。这样可以确保输出文件始终保持递增有序，从而形成一个完整的有序序列。

通过上述两步的交替执行，置换选择排序能够在外部存储环境下有效地生成有序文件，适用于大型数据集的排序任务。

---

举一个实际的例子，假设一个输入文件 FI 的内容为 51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100。

我们可以通过 置换选择排序 生成 3 个 初始归并段，分别为 {37, 51, 63, 92, 94, 99} ，{14, 15, 23, 31, 48, 56, 60, 90, 166} ，{8, 17, 43, 100} 。

算法执行的过程如下表所示。# 表示一个初始归并段结束：

输出文件 $FO$	工作区 $WA$	输入文件 $FI$
—	—	51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
—	51, 94, 37, 92	14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
37	51, 94, 14, 92	63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
37, 51	63, 94, 14, 92	15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
37, 51, 63	15, 94, 14, 92	99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
37, 51, 63, 92	15, 94, 14, 99	48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
37, 51, 63, 92, 94	15, 48, 14, 99	56, 23, 60, 31, 17, 43, 8, 90, 166, 100
37, 51, 63, 92, 94, 99	15, 48, 14, 56	23, 60, 31, 17, 43, 8, 90, 166, 100
37, 51, 63, 92, 94, 99 #	15, 48, 14, 56	23, 60, 31, 17, 43, 8, 90, 166, 100
14	15, 48, 23, 56	60, 31, 17, 43, 8, 90, 166, 100
14, 15	60, 48, 23, 56	31, 17, 43, 8, 90, 166, 100
14, 15, 23	60, 48, 31, 56	17, 43, 8, 90, 166, 100
14, 15, 23, 31	60, 48, 17, 56	43, 8, 90, 166, 100
14, 15, 23, 31, 48	60, 43, 17, 56	8, 90, 166, 100
14, 15, 23, 31, 48, 56	60, 43, 17, 8	90, 166, 100
14, 15, 23, 31, 48, 56, 60	90, 43, 17, 8	166, 100
14, 15, 23, 31, 48, 56, 60, 90	166, 43, 17, 8	100
14, 15, 23, 31, 48, 56, 60, 90, 166	100, 43, 17, 8	—
14, 15, 23, 31, 48, 56, 60, 90, 166 #	100, 43, 17, 8	—
8	100, 43, 17	—
8, 17	100, 43	—
8, 17, 43	100	—
8, 17, 43, 100	—	—
8, 17, 43, 100 #	—	—

多路归并

多路归并 的目标是将多个已经排序的 初始归并段（子文件）合并成一个更大的有序文件。

其核心思想是把每个归并段的当前段首元素放入工作区，并用 小根堆、胜者树或败者树维护这些候选元素。每次选出全局最小值写入输出文件，再从该值所属的归并段读入下一个元素补位，从而保证输出序列始终有序。

多路归并 的具体过程如下：

1. 初始化：
   • 打开所有参与归并的 初始归并段，并读取每个归并段的第一个元素。
   • 将这些元素放入一个数据结构中，以便快速找到最小值（例如，最小堆）。
2. 归并：
   • 从数据结构中取出最小的元素，将其输出到结果文件中。
   • 找到该元素所属的归并段，并从该归并段中读取下一个元素。
   • 将新读取的元素放入数据结构中，并调整数据结构，以保持有序。
   • 重复上述步骤，直到所有归并段都被处理完毕。
3. 结束：
   • 当所有归并段都为空时，归并过程结束，结果文件即为完全有序的文件。

多路归并的过程可以通过以下流程图理解：

---

继续用上文中通过 置换选择算法 生成的三个 初始归并段 {37, 51, 63, 92, 94, 99} ，{14, 15, 23, 31, 48, 56, 60, 90, 166} ，{8, 17, 43, 100} 作为例子。对于这三个 初始归并段，多路归并 的过程如下（假设采用三路归并的话）：

归并段 1 剩余记录	归并段 2 剩余记录	归并段 3 剩余记录	工作区	输出文件
37, 51, 63, 92, 94, 99	14, 15, 23, 31, 48, 56, 60, 90, 166	8, 17, 43, 100	—	—
51, 63, 92, 94, 99	15, 23, 31, 48, 56, 60, 90, 166	17, 43, 100	8, 14, 37	—
51, 63, 92, 94, 99	15, 23, 31, 48, 56, 60, 90, 166	43, 100	14, 17, 37	8
51, 63, 92, 94, 99	23, 31, 48, 56, 60, 90, 166	43, 100	15, 17, 37	8, 14
51, 63, 92, 94, 99	31, 48, 56, 60, 90, 166	43, 100	17, 23, 37	8, 14, 15
51, 63, 92, 94, 99	31, 48, 56, 60, 90, 166	100	23, 37, 43	8, 14, 15, 17
51, 63, 92, 94, 99	48, 56, 60, 90, 166	100	31, 37, 43	8, 14, 15, 17, 23
51, 63, 92, 94, 99	56, 60, 90, 166	100	37, 43, 48	8, 14, 15, 17, 23, 31
63, 92, 94, 99	56, 60, 90, 166	100	43, 48, 51	8, 14, 15, 17, 23, 31, 37
63, 92, 94, 99	56, 60, 90, 166	—	48, 51, 100	8, 14, 15, 17, 23, 31, 37, 43
63, 92, 94, 99	60, 90, 166	—	51, 56, 100	8, 14, 15, 17, 23, 31, 37, 43, 48
92, 94, 99	60, 90, 166	—	56, 63, 100	8, 14, 15, 17, 23, 31, 37, 43, 48, 51
92, 94, 99	90, 166	—	60, 63, 100	8, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56
92, 94, 99	166	—	63, 90, 100	8, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60
94, 99	166	—	90, 92, 100	8, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63
94, 99	—	—	92, 100, 166	8, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63, 90
99	—	—	94, 100, 166	8, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63, 90, 92
—	—	—	99, 100, 166	8, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63, 90, 92, 94
—	—	—	—	8, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63, 90, 92, 94, 99, 100, 166

胜者树

在进行 k 路归并（如外排序）时，我们需要从多个有序子序列中 快速找出当前最小元素，然后将其输出并替换为该序列的下一个元素。

最简单的做法就是每次遍历序列头部元素，找到最小值。该方法每次选择的时间复杂度为 $O(k)$，效率比较低，尤其是当 $k$ 较大时。

树形结构优化（胜者树/败者树）优化的目的就是优化这个过程：

用一棵完全二叉树维护每一轮比较的结果，使得我们可以在 $O(\log k)$ 时间内完成最小值查找与更新。

---

胜者树 可以理解为 胜者晋级的淘汰赛模型：类比体育比赛的淘汰制，每一轮两个选手进行比较，胜者晋级上一轮，最终全局胜者抵达根节点。

在 胜者树 中，每个 内部结点 记录的是该轮比较的 胜者（较小的元素），而 叶子节点 表示每个输入归并段的当前值。因此，整棵树的 根节点 就表示 全局最小值。

当某个归并段输出了最小值并更新为下一个元素时，需要 从该叶子节点向上，逐层与兄弟节点重新比较，构建新的胜者路径，最终将新的最小值更新到根节点。

败者树

败者树 可以理解为 败者记录的升降赛模型：类比体育比赛中每场比赛将败者淘汰出局但保留记录，胜者则继续晋级下一轮，最终全局胜者脱颖而出，但 不会被记录在树中，而是单独保留，以便快速访问。

在 败者树 中，每个 内部结点 记录的是该轮比较的 败者（较大的元素），而 叶子节点 同样表示每个输入归并段的当前值。最终的全局胜者（最小值） 不保存在树中，而是单独保存在一个外部变量中。

当某个归并段输出了最小值并更新为下一个元素时，需要 从该叶子节点出发，沿着路径向上与路径上的败者重新比较，并在每一层更新败者信息。

败者树的优势

在用 胜者树 时，新元素沿路径上升，需要取得兄弟结点记录的胜者后再更新父结点；使用 败者树 时，路径上的内部结点已经保存了需要比较的败者，可直接让当前胜者逐层与其比较。

两者每次更新都需要 $O(\log k)$ 次比较，但败者树通常能减少记录移动和访存，调整过程也更集中，因此常用于多路归并。

归并趟数、缓冲区与稳定性的判断

设初始归并段个数为 $r$，每次进行 $k$ 路归并。忽略最后一趟可能不足 $k$ 段的情形，完成归并所需的趟数为

这说明增大归并路数能够减少整文件被反复读写的次数，但不能无限增大：进行 $k$ 路归并至少要给 $k$ 个输入段各留一个输入缓冲区，并留一个输出缓冲区，另外还要有维护最小记录的堆、胜者树或败者树。内存固定时，路数过大反而会让每个缓冲区过小、I/O 效率下降。答题时应把“减少趟数”与“缓冲区是否装得下”同时说明。

每一趟完整归并通常都要把待处理记录读入一次、再写出一次，因此外部排序的主要代价是磁盘 I/O，而不是比较次数。若题目给出块大小、可用内存块数或初始段数，应先求工作区能容纳多少块、再求初始段数量和归并趟数；不能只套内部排序的 $O(n\log n)$ 比较复杂度。

置换选择为什么能生成更长的段

若工作区可容纳 $M$ 条记录，置换选择并不保证每个初始段都恰好有 $M$ 条。当前段每输出一个最小记录，就读入一条新记录：新记录不小于刚输出值时仍属于当前段；小于刚输出值时被冻结，留给下一段。当前可参与竞争的记录全部冻结后，当前段结束，冻结记录解冻并开始下一段。

在独立、均匀随机的输入假设下，初始段平均长度常接近 $2M$，因此段数往往比简单内存排序分段更少；这只是统计上的期望，不是对有序、逆序或高度重复输入都成立的保证。若输入近似升序，段可能远长于 $2M$；若输入不断出现比已输出值小的记录，冻结得更早，段也会变短。

外部归并要保持稳定性，还须规定相等关键字的取舍。多路归并时，若多个段首关键字相等，应优先输出原来归并段序号更小、或更早读入的记录；置换选择的比较也需用“关键字加原始次序”作为并列时的次关键字。只写“使用败者树”并不能自动保证稳定。

从文件规模估算排序流程

设待排序文件有 $N$ 条记录，内存工作区一次只能容纳 $M$ 条记录。采用“读满 $M$ 条、内部排好后写出”生成初始段时，初始段数为 $\lceil N/M\rceil$；采用置换选择时，随机输入下的平均段长常约为 $2M$，段数才可近似估为 $\lceil N/(2M)\rceil$。后一个估计不能替代实际轨迹，题目给出具体输入时仍应按冻结、解冻过程逐条判断。

有了初始段数 $r$ 后，再按可用缓冲区确定 $k$ 路归并，并计算 $\lceil\log_k r\rceil$ 个归并层次。若某一层的段数不能被 $k$ 整除，最后一组可以少于 $k$ 段，或按题设补入不含记录的虚段；虚段不改变结果，只是使每个归并组形状一致。把“记录数”和“初始段数”混为一谈，会导致趟数相差很大。

若把初始段生成也计为一次读写，且每个归并层都写回外存，完整外排大致要经历一次初始读写和每层一次读写。最终结果若直接交给后续程序而不再落盘，最后一次写出的代价可按题意省去；因此 I/O 次数必须根据“结果是否写回磁盘、缓冲区按块还是按记录计数”的题设明确说明。