外部排序

外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。

外部排序的基本思路

1. 把外存上含有n个记录的文件分成若干个长度为L的子文件，把这些子文件依次读入内存，并利用有效的内部排序方法对它们进行排序，再将排序后得到的有序子文件重新写入外存；
2. 对这些有序子文件逐趟归并，使其逐渐由小到大，直至得到整个有序文件为止。

明确概念： 称排序后的 “有序子文件”为“归并段” ，称每次归并时参与归并的“归并段”的数量为“路数” 。

由第二步“归并”操作可以看出，归并时构成了一棵以各归并段为根节点、以归并路数为度的“归并树” 。

效率优化

效率计算 首先，外部排序的总时间一般为：

式中，n 为每次参加归并的记录的个数，t_{MG} 是每做一次内部归并是查找最值的时间。

当然上式完全是个唬人的玩意，常理来说，做一只外部排序的耗时大头主要是I/O操作。 因此，计算一次外部排序的时间，主要是计算做I/O操作的次数。 假设外部I/O设备是硬盘，硬盘的读写是以块为单位，因此分析读写次数主要是分析总体加载和写入块的次数。 可以看出，读写总次数为分段时读写次数 + 归并时读写次数。其中，分段时要求读写所有数据一次，这是不可避免的；归并时每轮归并要求读写所有数据一次（即归并树中每一层都要读写所有数据一次）。因此，若要减少总读写次数，只能减少归并树的层次。

归并数的层次（高度）为：

式中，k 为归并的路数，m 为归并段数

优化归并路数

归并时，每次要从各段中选择出一个最值进行写出，查找这个“最值”的时间随着数据规模的上升而上升；而每次查找该“最值”的“数据规模”即为“归并路数”（因为要从每一路中加载一个数参与比较），因此归并路数上升会导致内部排序变慢。 S 轮归并总共需要的比较次数为：（注意选择题会考）

到这里，设法使查找操作不随问题规模增加而显著增加。

使用“败者树”（借鉴“堆排序”）

内存中持续维护一棵“败者树”，使每次新数据进入时都能借助上次排序的结果 ，从而减少查找时间，这便是“堆排序”的思路。 堆排序的最坏时间复杂度为log_2k 因此，总比较次数便为：

优化归并段数

既然归并操作时能够摆脱内存大小的限制，将超过内存的数据合并排序，那么在分段时也可尝试超过内存个数的分段。

置换-选择排序

// TODO

解决参差不齐的分段问题：最佳归并树

上文示，归并操作时构成了一棵“归并树”。记录数最多（最长）的段，归并时其I/O操作也即越多，因此应将其较晚归并，这可以用“霍夫曼树”解决。

在构造霍夫曼树时有一个问题，若段的数目不足以构成一棵“严格 k 叉树”（k 为归并路数），则应添加权值为0的“虚段”。由于权值为0，“虚段”永远在离根最远的层。

添加“虚段”的方法 设度为0的节点（叶子节点）有 n_0 个，度为 k 的节点（中间节点）有 n_k 个，则对于“严格 k 叉树”有 n_0 = (k-1)n_k + 1 ，则 n_k = (n_0-1)/ (k-1)，有：

• (n_0-1) % (k-1) ==0 : 恰好构成严格 k 叉树，无需添加虚节点
• (n_0-1) % (k-1) == u != 0 : 有 u 个节点多余，则添加 m-u-1 个“虚结点”。（解释：可添加一个中间节点来“收留”此 u 个节点，由于此中间节点的添加也占用了一个原有的“叶子节点位“，因此应该补加 m-(u+1) = m-u-1 个“虚结点”）

https://www.sohu.com/a/258751244_81869251244_8186929251244_81869286924_8186928692_8186928692