外部排序算法

1、内部排序算法，即排序的整个过程只是在内存中完成。而当待排序的文件比内存的可使用容量还大时，文件无法一次性放到内存中进行排序，需要借助于外部存储器（例如硬盘、U盘、光盘）

2、外部排序算法：借助外部存储器对数据进行排序的算法，包括置换平衡归并排序算法、置换选择排序算法等

3、外部排序算法的实现，其实就是将体积大的数据分割为内存容得下的多份数据，然后分别使用内部排序算法进行排序，最后进行整合

4、和内部排序算法不同，外部排序算法的主要影响因素在于读写内存的次数

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

1、按照内存大小，将大文件分成若干长度为 l 的子文件（l 应小于内存的可使用容量），然后将各个子文件依次读入内存，使用适当的内部排序算法对其进行排序（排好序的子文件统称为“归并段”或者“顺段”），将排好序的归并段重新写入外存，为下一个子文件排序腾出内存空间

2、对得到的顺段进行合并，直至得到整个有序的文件为止

为了提高整个外部排序的效率，分别从以上两个方面对外部排序进行了优化

1、在实现将初始文件分为 m 个初始归并段时，为了尽量减小 m 的值，采用置换 - 选择排序算法，可实现将整个初始文件分为数量较少的长度不等的初始归并段

2、同时在将初始归并段归并为有序完整文件的过程中，为了尽量减少读写外存的次数，采用构建最佳归并树的方式，对初始归并段进行归并，而归并的具体实现方法是采用败者树的方式

外部排序效率

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

2、计算机中处理数据的为中央处理器（CPU），如若需要访问外存中的数据，只能通过将数据从外存导入内存，然后从内存中获取。同时由于内存读写速度快，外存读写速度慢的差异，更加影响了外部排序的效率

3、对于同一个文件来说，对其进行外部排序时访问外存的次数同归并的次数成正比，即归并操作的次数越多，访问外存的次数就越多

4、对于 k-路平衡归并中 k 值得选择，增加 k 可以减少归并的次数，从而减少外存读写的次数，最终达到提高算法效率的目的

5、一般情况下对于具有 m 个初始归并段进行 k-路平衡归并时，归并的次数为：s = ⌊logk⁡m⌋（其中 s 表示归并次数）

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

（1）增加 k-路平衡归并中的 k 值，对应：多路平衡归并算法

（2）尽量减少初始归并段的数量 m，即增加每个归并段的容量，对应：置换-选择排序算法