7.7.1外部排序

①外部排序指待排序文件较大，内存一次放不下，需存放在外部介质的文件的排序。

②为减少平衡归并中外存读写次数所采用的方法：增大归并路数和减少归并段个数。

③利用败者树增大归并路数。

④利用置换-选择排序增大归并段长度来减少归并段个数。

⑤由长度不等的归并段，进行多路平衡归并，需要构造最佳归并树。

7.7.1外部排序的基本概念

内部排序都是在内存中进行的，而在实际应用中，经常需要对大文件进行排序，因为文件中的记录很多、信号量庞大，无法将整个文件拷贝进内存中进行排序。因此，需要将待排序的记录存储在外存上，排序时再将数据一部分一部分的调入内存进行排序。在排序过程中需要多次进行内存和外存之间的交换，对外存文件中的记录进行排序后的结果仍然被存放到原有文件中。这种排序方法就称为外部排序。