算法（三）外部排序算法

当待排序序列比内存可使用容量还大时，文件无法一次性放到内存中进行排序，需要借助外部存储器（例如硬盘、u盘、光盘），这时就需要用到外部排序来解决。

外部排序算法由两个阶段构成

• 1. 按照内存大小，拆分成若干大小的子文件。使用适当的内部排序算法进行排序，将排好序的归并段写入外存，为下一个子文件排序腾出内存空间。
• 2. 对所有的归并段进行合并，直到得到整个有序的文件。

外部排序算法的最优方案：多路归并（败者树-归并时使用的比较算法）+ 置换选择（败者树（或最小堆）-生成初始文件）+ 最佳归并树（哈夫曼树-来决定初始文件的归并顺序）

下面我们解释这几种算法。

对于外部排序算法来说，影响整体排序效率的因素主要取决于读写外存的次数，即访问外存的次数越多，算法花费的时间就越多，效率就越低。

平衡归并的路数越多，需要归并的次数就越少。这样读取外存的次数就越少。
平衡归并的初始拆分的临时文件个数越少，需要归并的次数就越少。
一般情况下对于具有m个初始段，进行k路平衡归并时，归并的次数为 s=log_km

从公式可以判断出，想要达到减少归并次数从而提高算法效率的目的。可以从两个角度实现：

• 增加k路平衡归并中k的值 （引申出：多路平衡归并算法）
• 尽量减少初始归并段的数量m 即增加每个归并段的容量。（引申出：置换-选择排序算法）

多路平衡归并算法

五路平衡归并

具体败者树此处不描述。请自行查阅。

5路归并的比较算法如果采用顺序比较，需要4次比较才得到最小值；如果采用败者树算法，则最多需要3次。并且可以看出，k路归并对应的比较次数是大约是 log₂⁡k 次。

所以多路平衡排序算法，在归并阶段使用败者树，来进行归并时的排序，效率较高。

置换选择算法

上面描述的多路平衡归并算法，我们都是在假设已经有了排好序的初始归并段（文件）的前提下进行讨论的。
为了得到初始归并段，我们把大文件拆分成内存所能承受的若干个文件，然后把文件逐个从外存读进内存，进行某种内部排序算法，再输出为单个文件，由于内存的限制，大文件要拆分成许多个小文件。但是因为m值越大归并次数越多，排序所需时间就越长。置换选择算法就很好地解决这一问题。
置换选择算法仍然使用败者树。
使用败者树分段后，各个文件中的记录已经有序，不需要再经过 外存读进内存 、内存中进行内部排序算法、再输出单个文件的过程。

通过置换选择排序算法得到的归并段，通过证明，平均长度为内存工作区大小的两倍。

最佳归并树

置换选择算法分段后，由于各初始段长度不相等，那么归并段的归并顺序对排序的时间会不会有影响呢？
例如有3个初始归并段 a、b、c，段长分别为1、2、3。

• 先归并b、c 得到归并段e 那么e 的长度为5 ，再归并a、e。 所需时间为 (2+3) 得到e (1+ 5) 得到最终归并段 整体为（2+3）+（1+5）=11
• 先归并a、b 得到归并段e 在归并c、e 那么所需时间为 （1+2）+（3+3）=9

也就是说如果一开始就归并很长的段，由于该段还会在以后归并中出现，那么消耗时间就很长。所以我们应该先归并较短的段。

最终可以通过构造哈夫曼树的方法得到最佳归并顺序。

至此外部排序结束。

位图法和桶排序

位图法和桶排序也可以作为外部排序使用的算法。但是只特定于指定场景。
位图法 bitmap ：使用hash映射，将对应的正整数映射到位图的集合中。每一个bit代表其映射的正整数是否存在。
比如{1，2，3，5，8，13}使用下列集合表示：

0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0

位图法是计数排序思想。
应用：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中。（布隆过滤器）

桶排序：将大文件按照指定范围分桶，例如位数，范围等等，分好桶后，分别排序。这样就不需要最后的归并。因为在分桶的时候已经确定了每个桶的先后顺序。初始需要遍历一次。