外部排序
外部排序
当待排序的数据量大到无法一次性全部装入内存时,就必须采用 外部排序。外部排序的基本思路是:先将整个数据集划分成若干能够装入内存的子块,对每个子块在内存中完成内部排序;随后再把这些已排序的子块逐步合并,最终得到整体有序的结果。这样既克服了内存容量的限制,又能高效地对海量数据完成排序。
外部排序的整体过程通常可以划分为两个关键阶段:
生成初始归并段
先采用 置换选择排序 对原始的无序文件进行扫描。置换选择能够在一次扫描中尽可能长地生成有序子文件,这些子文件即称为 初始归并段。每个归并段都是内部有序的,且长度尽量大,以减少后续合并的轮数。多路归并
将所有 初始归并段 以多路归并的方式逐步合并。每一次归并都会把若干归并段合并成一个更长的有序段,重复此过程直至只剩下一个完整的有序文件,从而得到最终的排序结果。
通过上述两步,外部排序能够在 磁盘与内存之间 高效地完成大规模数据的排序。
置换选择排序
置换选择排序(Replacement Selection Sort)是 外部排序 的一个步骤,用于生成 初始归并段,其核心功能是在 内存缓冲区 有限的情况下,尽可能地生成较长的 初始归并段。
置换选择排序 通过维护一个 工作区 来实现这一目标,工作区是一个 小根堆。
其算法步骤如下:
- 初始化:
- 将待排序文件中的前 M 个记录读入 工作区,建立一个 最小堆(M 为 工作区 的大小)。
- 生成归并段:
- 判断是否有 初始归并段
- 如果不存在任何 初始归并段 的话,创建一个 初始归并段,并添加 工作区 中的最小元素加入其中。
- 否则将 工作区 中的元素与上一个 初始归并段 的最大值 MAXV 进行比较。
- 如果 工作区 中的所有元素都 ≤ 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# | —— | —— |
多路归并
多路归并 的目标是将多个已经排序的 初始归并段(子文件)合并成一个更大的有序文件。
其核心思想是从若干 归并段 中每次选取一个最小的元素加入 工作区(小根堆),然后从 工作区 中选取最小的元素添加到 输出文件 中,通过这种方式可以保证每次添加到 输出文件 中的值是当前的最小值。
多路归并 的具体过程如下:
- 初始化:
- 打开所有参与归并的 初始归并段,并读取每个归并段的第一个元素。
- 将这些元素放入一个数据结构中,以便快速找到最小值(例如,最小堆)。
- 归并:
- 从数据结构中取出最小的元素,将其输出到结果文件中。
- 找到该元素所属的归并段,并从该归并段中读取下一个元素。
- 将新读取的元素放入数据结构中,并调整数据结构,以保持有序。
- 重复上述步骤,直到所有归并段都被处理完毕。
- 结束:
- 当所有归并段都为空时,归并过程结束,结果文件即为完全有序的文件。
多路归并的过程可以通过以下流程图理解:
继续用上文中通过 置换选择算法 生成的三个 初始归并段 {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)$ 时间内完成最小值查找与更新。
胜者树 可以理解为 胜者晋级的淘汰赛模型:类比体育比赛的淘汰制,每一轮两个选手进行比较,胜者晋级上一轮,最终全局胜者抵达根节点。
在 胜者树 中,每个 内部结点 记录的是该轮比较的 胜者(较小的元素),而 叶子节点 表示每个输入归并段的当前值。因此,整棵树的 根节点 就表示 全局最小值。
当某个归并段输出了最小值并更新为下一个元素时,需要 从该叶子节点向上,逐层与兄弟节点重新比较,构建新的胜者路径,最终将新的最小值更新到根节点。
败者树
败者树 可以理解为 败者记录的升降赛模型:类比体育比赛中每场比赛将败者淘汰出局但保留记录,胜者则继续晋级下一轮,最终全局胜者脱颖而出,但 不会被记录在树中,而是单独保留,以便快速访问。
在 败者树 中,每个 内部结点 记录的是该轮比较的 败者(较大的元素),而 叶子节点 同样表示每个输入归并段的当前值。最终的全局胜者(最小值) 不保存在树中,而是单独保存在一个外部变量中。
当某个归并段输出了最小值并更新为下一个元素时,需要 从该叶子节点出发,沿着路径向上与路径上的败者重新比较,并在每一层更新败者信息。
胜者树更加直观,败者树的优势在哪?
在用 胜者树 的时候,每个新元素上升时,首先先和兄弟结点比较,然后再更新父结点(访存 2 次)。
在使用 败者树 的时候,每个新元素上升时,只需要获得父节点并比较即可(访存 1 次)。
所以总的来说,减少了访存的时间,进而 提高了程序运行的效率。