外部排序

外部排序流程

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

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

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

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

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

置换选择排序

置换选择排序（Replacement Selection Sort）是 外部排序 中的一个步骤，用于生成 初始归并段。它的目标是在 内存工作区有限 的情况下，尽可能生成更长的初始归并段，从而减少后续归并次数，提高外部排序效率。

置换选择排序的基本思想是：工作区中的记录并不会一次性全部输出，而是不断从输入文件读取新记录替换已经输出的记录，并判断新记录应该属于当前归并段还是下一归并段。

其算法过程如下：

1. 初始化
   • 从待排序文件中读入前 M 个记录，放入工作区（M 为工作区容量）。
2. 生成归并段
   • 若当前还没有归并段，则创建第一个归并段，并输出工作区中最小的记录。
   • 此后，每次输出一个记录后，都将其与当前归并段最后一个记录（记为 MAXV）进行比较：
     • 如果工作区中仍存在键值大于 MAXV 的记录，则继续将其中键值最小的记录加入当前归并段，使归并段保持有序。
     • 如果工作区中的所有记录都不大于 MAXV，说明这些记录已经无法继续加入当前归并段，需要结束当前归并段，并创建一个新的归并段继续输出。
   • 每输出一个记录，就从输入文件中读取一个新的记录补充到工作区，直到所有记录都处理完成。

置换选择排序的核心思想可以概括为：

• 能够接入当前归并段的记录，就尽可能继续输出。 只要工作区中仍存在键值大于当前归并段最后一个记录（MAXV）的记录，就将其中键值最小的记录追加到当前归并段，使该归并段不断扩展。
• 无法接入当前归并段的记录，则留到下一归并段。 当工作区中的所有记录都不大于 MAXV 时，说明这些记录都无法保持当前归并段的有序性，因此结束当前归并段，并以这些记录作为起点开始生成新的归并段。

与内部排序不同，置换选择排序并不是一次性对工作区中的记录进行排序，而是在 输出一个记录的同时，从输入文件中读入一个新的记录补充到工作区。因此，后续读入的数据只要满足有序性要求，就有机会继续加入当前归并段，而不是必须等待下一轮排序。

正是由于这种 边输出、边读入、边扩展归并段 的机制，一个归并段不仅包含最初读入工作区的记录，还可能包含后续读入的大量记录。因此，在随机输入的情况下，一个初始归并段的平均长度约为工作区容量的 2M，从而减少初始归并段的数量，降低后续多路归并的次数，提高整个外部排序的效率。

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

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

算法执行的过程如下表所示：

多路归并

多路归并（K-way Merge）是外部排序的第二个阶段，其目标是将多个已经有序的 初始归并段 逐步合并，最终生成一个完整的有序文件。

其 核心思想 是：

每个归并段始终保留一个当前待输出的元素，每次从这些元素中选出最小值写入输出文件，然后从该元素所属的归并段读取下一个元素进行补充。

由于每个归并段本身已经有序，因此只需要维护每个归并段当前的最小候选元素，即可保证输出文件始终保持有序。

实际实现中，通常使用 小根堆 维护各个归并段当前的候选元素，从而能够快速找到全局最小值。

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

1. 初始化
   • 打开所有参与归并的初始归并段。
   • 从每个归并段读取第一个元素，将这些元素加入工作区（通常采用小根堆维护）。
2. 归并
   • 从工作区中取出最小元素，写入输出文件。
   • 找到该元素所属的归并段，从该归并段读取下一个元素。
   • 若该归并段还有剩余元素，则将新读取的元素加入工作区，并调整数据结构。
   • 重复上述过程，直到所有归并段均处理完成。
3. 结束
   • 当所有归并段都已读完、工作区为空时，归并结束，得到一个完全有序的文件。

多路归并的关键在于：每个归并段始终只有一个元素参与比较，因此工作区中最多只需要维护 k 个元素（k 为归并路数），每输出一个元素，仅需从对应的归并段补充一个新的元素即可。借助小根堆，每次取出最小元素和插入新元素的时间复杂度均为 O(log k)，因此整个多路归并能够高效地完成大规模外部排序。

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

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

胜者树

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

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

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

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

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

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

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

败者树

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

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

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