当待排序序列比内存可使用容量还大时，文件无法一次性放到内存中进行排序，需要借助外部存储器（例如硬盘、u盘、光盘），这时就需要用到外部排序来解决。
外部排序算法由两个阶段构成
- 按照内存大小，拆分成若干大小的子文件。使用适当的内部排序算法进行排序，将排好序的归并段写入外存，为下一个子文件排序腾出内存空间。
- 对所有的归并段进行合并，直到得到整个有序的文件。
外部排序算法的最优方案：多路归并（败者树-归并时使用的比较算法）+ 置换选择（败者树（或最小堆）-生成初始文件）+ 最佳归并树（哈夫曼树-来决定初始文件的归并顺序）
下面我们解释这几种算法。
对于外部排序算法来说，影响整体排序效率的因素主要取决于读写外存的次数，即访问外存的次数越多，算法花费的时间就越多，效率就越低。
平衡归并的路数越多，需要归并的次数就越少。这样读取外存的次数就越少。
平衡归并的初始拆分的临时文件个数越少，需要归并的次数就越少。
一般情况下对于具有m个初始段，进行k路平衡归并时，归并的次数为 s=logkm
从公式可以判断出，想要达到减少归并次数从而提高算法效率的目的。可以从两个角度实现：
- 增加k路平衡归并中k的值 （引申出：多路平衡归并算法）
- 尽量减少初始归并段的数量m 即增加每个归并段的容量。（引申出：置换-选择排序算法）
多路平衡归并算法
五路平衡归并
提高k值，看似简单却暗藏杀机。我们都知道，归并排序的时候需要对每一路的当前值进行逐个比较，以得出最小值（最大值），也就是说如果一次归并有k路，正常来说就需要比较k-1次，这种顺序比较的成本太高了。那么有没有什么方法降低成本-
败者树
具体败者树此处不描述。请自行查阅。
5路归并的比较算法如果采用顺序比较，需要4次比较才得到最小值；如果采用败者树算法，则最多需要3次。并且可以看出，k路归并对应的比较次数是大约是 log2k 次。
所以多路平衡排序算法，在归并阶段使用败者树，来进行归并时的排序，效率较高。
置换选择算法
上面描述的多路平衡归并算法，我们都是在假设已经有了排好序的初始归并段（文件）的前提下进行讨论的。
为了得到初始归并段，我们把大文件拆分成内存所能承受的若干个文件，然后把文件逐个从外存读进内存，进行某种内部排序算法，再输出为单个文件，由于内存的限制，大文件要拆分成许多个小文件。但是因为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亿个数当中。（布隆过滤器）
桶排序：将大文件按照指定范围分桶，例如位数，范围等等，分好桶后，分别排序。这样就不需要最后的归并。因为在分桶的时候已经确定了每个桶的先后顺序。初始需要遍历一次。
网友评论