外部排序

了解外部排序的思想即可,可能在选择题中考察一题。

外部排序

当待排序的数据量非常大,以至于无法一次性全部加载到内存中时,就需要使用 外部排序

外部排序 通常分为两个主要阶段:

  • 初始归并段生成:使用 置换选择排序,根据原始无序文件生成若干个尽量长的的有序文件,这些有序文件叫做 初始归并段
  • 多路归并:将这些 初始归并段 逐步合并,最终得到完全有序的文件。
置换归并排序:
生成初始归并段
多路归并排序

置换选择排序

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

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

其算法步骤如下:

  1. 初始化
    • 将待排序文件中的前 M 个记录读入 工作区,建立一个 最小堆M工作区 的大小)。
  2. 生成归并段
    • 判断是否有 初始归并段
      • 如果不存在任何 初始归并段 的话,创建一个 初始归并段,并添加 工作区 中的最小元素加入其中。
      • 否则将 工作区 中的元素与上一个 初始归并段 的最大值 MAXV 进行比较。
        • 如果 工作区 中的所有元素都 ≤ MAXV 的话,创建一个新的 初始归并段,并添加 工作区 中的最小元素加入其中。
        • 否则找到第一个 > MAXV 的元素,将其添加到上一个 初始归并段 的末尾。
    • 从输入文件中读取下一个值加入 工作区
输入文件 IF
工作区(小根堆)
输出文件 OF1
输出文件 OF2
如果工作区中存在值
> OF1 最大值
否则创建一个
新文件

举一个实际的例子,假设一个输入文件 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, 9214, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
3751, 94, 14, 9263, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
37, 5163, 94, 14, 9215, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
37, 51, 6315, 94, 14, 9299, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
37, 51, 63, 9215, 94, 14, 9948, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
37, 51, 63, 92, 9415, 48, 14, 9956, 23, 60, 31, 17, 43, 8, 90, 166, 100
37, 51, 63, 92, 94, 9915, 48, 14, 5623, 60, 31, 17, 43, 8, 90, 166, 100
37, 51, 63, 92, 94, 99#15, 48, 14, 5623, 60, 31, 17, 43, 8, 90, 166, 100
1415, 48, 23, 5660, 31, 17, 43, 8, 90, 166, 100
14, 1560, 48, 23, 5631, 17, 43, 8, 90, 166, 100
14, 15, 2360, 48, 31, 5617, 43, 8, 90, 166, 100
14, 15, 23, 3160, 48, 17, 5643, 8, 90, 166, 100
14, 15, 23, 31, 4860, 43, 17, 568, 90, 166, 100
14, 15, 23, 31, 48, 5660, 43, 17, 890, 166, 100
14, 15, 23, 31, 48, 56, 6090, 43, 17, 8166, 100
14, 15, 23, 31, 48, 56, 60, 90166, 43, 17, 8100
14, 15, 23, 31, 48, 56, 60, 90, 166100, 43, 17, 8——
14, 15, 23, 31, 48, 56, 60, 90, 166#100, 43, 17, 8——
8100, 43, 17——
8, 17100, 43——
8, 17, 43100——
8, 17, 43, 100————
8, 17, 43, 100#————

多路归并

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

其核心思想是从若干 归并段 中每次选取一个最小的元素加入 工作区小根堆),然后从 工作区 中选取最小的元素添加到 输出文件 中,通过这种方式可以保证每次添加到 输出文件 中的值是当前的最小值。

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

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

继续用上文中通过 置换选择算法 生成的三个 初始归并段 {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, 9914, 15, 23, 31, 48, 56, 60, 90, 1668, 17, 43, 100
51, 63, 92, 94, 9915, 23, 31, 48, 56, 60, 90, 16617, 43, 1008, 14, 37
51, 63, 92, 94, 9915, 23, 31, 48, 56, 60, 90, 16643, 10014, 17, 378
51, 63, 92, 94, 9923, 31, 48, 56, 60, 90, 16643, 10015, 17, 378, 14
51, 63, 92, 94, 9931, 48, 56, 60, 90, 16643, 10017, 23, 378, 14, 15
51, 63, 92, 94, 9931, 48, 56, 60, 90, 16610023, 37, 438, 14, 15, 17
51, 63, 92, 94, 9948, 56, 60, 90, 16610031, 37, 438, 14, 15, 17, 23
51, 63, 92, 94, 9956, 60, 90, 16610037, 43, 488, 14, 15, 17, 23, 31
63, 92, 94, 9956, 60, 90, 16610043, 48, 518, 14, 15, 17, 23, 31, 37
63, 92, 94, 9956, 60, 90, 16648, 51, 1008, 14, 15, 17, 23, 31, 37, 43
63, 92, 94, 9960, 90, 16651, 56, 1008, 14, 15, 17, 23, 31, 37, 43, 48
92, 94, 9960, 90, 16656, 63, 1008, 14, 15, 17, 23, 31, 37, 43, 48, 51
92, 94, 9990, 16660, 63, 1008, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56
92, 94, 9916663, 90, 1008, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60
94, 9916690, 92, 1008, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63
94, 9992, 100, 1668, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63, 90
9994, 100, 1668, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63, 90, 92
99, 100, 1668, 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)$ 时间内完成最小值查找与更新。


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

8
9
8
9
15
8
17
10
9
20
15
8
9
90
17
15
16
20
38
20
30
25
28
15
50
11
16
95
99
18
20

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

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

败者树

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

9
15
17
10
20
9
90
10
9
20
15
8
9
90
17
15
16
20
38
20
30
25
28
15
50
11
16
95
99
18
20
8
9
15
9
8
17
8
8
胜者需要进行下一轮比较

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

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

补充

胜者树更加直观,败者树的优势在哪?

在用 胜者树 的时候,每个新元素上升时,首先先和兄弟结点比较,然后再更新父结点(访存 2 次)。

在使用 败者树 的时候,每个新元素上升时,只需要获得父节点并比较即可(访存 1 次)。

所以总的来说,减少了访存的时间,进而 提高了程序运行的效率