# 外部排序
# 外存、内存之间的数据交换
操作系统以 "块" 为单位对磁盘存储空间进行管理，如：每块大小 1KB，各个磁盘块内存放着各种各样的数据
磁盘的读写以块为单位，数据读入内存后才能被修改，修改完了还要写回磁盘
# 外部排序原理
外部排序：数据元素太多，无法一次全部读入内存进行排序
使用归并排序的方法，最少只需在内存中分配 3 块大小的缓冲区即可对任意一个大文件进行排序
归并排序要求各个子序列有序，每次读入两个块的内容，进行内部排序后写回磁盘
构造初始归并段，然后归并段逐渐合并
外部排序时间 = 读写外存的时间 + 内部排序所需时间 + 内部归并所需时间
优化：多路归并
重要结论：采用多路归并可以减少归并趟数，从而减少磁盘 I/O 读写次数
对 r 个初始归并段，做 k 路归并，则归并树可用 k 叉树表示，若树高为 h，则归并趟数为 h-1
多路归并带来的负面影响：
- k 路归并时，需要开辟 k 个输入缓冲区，内存开销增加
- 每挑选一个关键字需要对比关键字 (k-1) 次，内部归并所需时间增加
优化：减少初始归并段数量
生成初始归并段的内存工作区越大，初始归并段越长
结论：若能增加初始归并段的长度，则可减少初始归并段数量 r
# 败者树
败者树 —— 可视为一棵完全二叉树。k 个叶节点分别是当前参加比较的元素，非叶子节点用来记忆左右子树中的失败者，而让胜者往上继续比较一直到根节点
基于已经构造好的败者树，选出新的胜者只需要进行很少的比赛
败者树在多路平衡归并中应用：每一路初始归并段对应败者树的一个叶子节点，每次选出最小的后，用归并段下一个值替代原来叶子节点，从而达到快速计算出最小值
败者树解决的问题：使用多路平衡归并可减小归并趟数，但是用老土的从 k 个归并段选出一个最小 / 最大元素需要对比关键字 k-1 次，构造败者树可以使关键字对比次数减少到
# 置换 - 选择排序
用于内部排序的内存工作区 WA 可容纳 l 个记录，则每个初始归并段也只能包含 l 个记录，若文件共有 n 个记录，则初始归并段的数量 r=n/l
使用置换 - 选择排序，可以让每个初始归并段的长度超过内存工作区大小的限制
整体流程
设初始待排文件为 FI，初始归并段输出文件为 FO，内存工作区为 WA，FO 和 WA 的初始状态为空，WA 可容纳 w 个记录。置换选择算法步骤如下：
- 从 FI 输入 w 个记录到工作区 WA
- 从 WA 中选出其中关键字取最小值的记录，记为 MINIMAX 记录
- 将 MINIMAX 记录输出到 FO 中去
- 若 FI 不空，则从 FI 输入下一个记录到 WA 中。
- 从 WA 中所有关键字比 MNIMAX 记录的关键字大的记录中选出最小关键字记录，作为新的 MINIMAX 记录
- 重复 3-5，直至在 WA 中选不出新的 MINIMAX 记录为止，由此得到一个初始归并段，输出一个归并段的结束表示到 FO 中去
- 重复 2-6，直至 WA 为空。由此得到全部初始归并段
# 最佳归并树
每个初始归并段看做一个叶子节点，归并段的长度作为结点权值，则这颗归并树的带权路径长度 = 读磁盘的次数 = 写磁盘的次数
重要结论：归并过程中的磁盘 I/O 次数 = 归并树的 WPL（带权路径长度）*2
因此，最佳归并树用构建哈夫曼树的方式构建，最终得到最佳归并树，可以减少读写磁盘次数
注意：对于 k 叉归并，若初始归并段的数量无法构成严格的 k 叉归并树，则需要补充几个长度为 0 的虚段，再进行 k 叉哈夫曼树的构造
k 叉的最佳归并树一定是一颗严格的 k 叉树，即树中只包含度为 k、度为 0 的节点。设度为 k 的节点由 nk 个，度为 0 的节点由 n0 个，归并树的总结点数为 n，则
初始归并数量 + 虚段数量 = n0
- 若 (初始归并段数量 - 1)%(k-1)=0，说明刚好可以构成严格 k 叉树，此时不需要添加虚段
- 若 (初始归并段数量 - 1)%(k-1)=u 不等于 0，则需要补充 (k-1-u) 个虚段
