数据结构：外部排序原理与优化方法

2.2 第一趟归并

接下来就需要我们把归并段们继续归并排序：

• 将两个归并段中小的数据块读入内存
• 在内存中进行归并排序
• 将排序好的数据写回外存

注意：写回的位置是另外一片，不是原来的存放未排序数据的位置。

出现一整个缓冲区空白的情况，就继续读入一个数据块，然后继续进行归并排序：

第一趟归并结束后，就成功得到了四个大的归并段：

2.3 第二趟归并

和之前一样，挑出两个归并段中最小的一组，继续进行合并：

第二趟合并后，就得到了两个更大的归并段：

2.4 第三趟归并

最后，把这两个更大的归并段进行合并：

最终就得到了有序的数据：

3. 时间开销分析

• 读写外存的时间：就是构造初始归并段的时间
• 内部排序所需时间：就是排序花费的时间。
• 内部归并所需时间：就是几次归并花费的时间。

4. 优化

我们先对读写外存的这部分时间进行优化。

4.1 多路归并

我们可以在内存多申请几个输入缓冲区，实现多路归并，一次读入两个数据段和一次读入四个数据段，当然是后者 I/O 次数更小，还可以减少归并的趟数。

假设：第一趟归并用 4 路归并

第一次归并后就得到两个归并段，只需要再一趟就可以完全有序：

4.2 减少初始归并段数量

比如之前的我们的初始归并段是 8 个，现在减少为 4 个：

4–>2–>1，得到初始归并段后再归并两次就可以完全有序了

外存的总数据块数不变，初始归并段越长，初始归并段越少。

5. 小结

重点在平衡这两个字上：

败者树

1. 多路平衡归并带来的问题

多路平衡归并：一个数要和很多个数都要比一次，才能找到最小的那个数字，就很浪费时间。

2. 败者树的构造

就是两个人战斗，失败的留下，胜利的上去，继续和另一组胜利的人继续比，最终选出一个冠军。

这个时候冠军跑路了：

由派大星顶替它原来的位置

那么难道我们还要重新比 7 次么？！

答案是不需要，右侧的根本没被派大星影响，右侧胜利的依旧是孙悟空； 而派大星需要代替天津饭，先和阿乐比，赢了再和程龙比，赢了再和孙悟空比； 只需要比对三次就可以了

3. 败者树的使用

同样的规则，我们就可以搬到归并段上使用。

画出败者树：

每个归并段都排除自己最小的一个数字参赛：

• 27>12，27 留，12 上；1<17，17 留，1 上；2<9，9 留，2 上；11>4，11 留，4 上；
• 12>1，12 留，1 上；2<4，4 留，2 上
• 1<2，2 留，1 上；
• 上一次的冠军是 1，来自归并段 3，他就可以先走了
• 继续用归并段 3 内的数字接力，6 出来沿着 1 的比赛路径进行比拼
• 6<17，17 留，6 上，所以结点是 6 所在的归并段 3；
• 12>6，12 留，6 上，所以结点是 6 所在的归并段 3；

最终回合：6>2，6 留，2 上，所以结点是 2 所在的归并段 5；

这样就找出了最小的一个数

注意：结点中记录的是来自的归并段，而不是真实数字

所以再需要接着比赛选出最小的冠军，就只需要踩着前人的脚印，继续向上比拼。比如：

4. 败者树的实现思路

5. 小结

置换 - 选择排序

1. 土办法构造初始归并段

纯一块一块构造。

2. 置换 - 选择排序

• 工作区：只能放三个记录
• MINIMAX：刚刚写出的数据的值
• 规定：同一归并段，只能写出比 MINIMAX 大的数字

注意：这里的输出缓冲区省略了，但不代表没有

选择工作区内最小的但比 4 大的数字写出：

按照这个规律一直写出： 这里我们发现最小的一个数字是 10<13，而我们只能写出比 13 大的，所以就放着先不要动

当工作区内的数字都比 MINIMAX 小，不可以写出的时候：

我们就需要开一个新的归并段，经过写出最后是这样：

最后就得到了三个不定长的归并段：

注意：是有输出缓冲区存在的，只不过我们省略了而已

3. 小结

最佳归并树

1. 归并树的神秘性质

归并过程中的磁盘读写次数=归并树的 WPL*2 也就是最佳归并树是哈夫曼的形式

2. 构造最佳归并树

2.1 2 路

2.2 多路归并

如果减少一个归并段，那么单纯地按照哈夫曼树的逻辑处理得到的就不是最佳归并树了：

我们需要添加一个结点 0，然后再按照正常的步骤继续进行：

3. 添加虚段的数量

情景：类似于上面缺少一个归并段的时候，我们需要添加几个结点 0？ 结论：图片最后两行（代入例子更好理解）

4. 小结