(70)王道数据结构-外部排序

基本概念

外排序（External sorting）是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器（通常是硬盘）上。外排序通常采用的是一种“排序-归并”的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。而后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。

若要进行k路归并排序，则需要再内存中分配k个输入缓冲区和1个输出缓冲区

实现步骤

1.生成r个初始归并段(对L个记录进行内部排序，组成一个有序的初始归并段)
2.进行S趟k路归并，S=log(kr)

进行k路归并

1.把k个归并段的块读入k个输入缓冲区
2.用“归并排序”的方法从k个归并段中选出几个最小记录
3.当输出缓冲区满时，写出外存

效率分析

时间开销

时间 = 读写外存的时间 + 内部排序所需时间 + 内部归并所需时间

优化

1.增加归并路数k，进行多路平衡归并

• 代价1:需要增加相应的输入缓冲区
• 代价2:每次从k个归并段中选一个最小元素需要(k-1)次关键字对比

2.减少初始化归并段数量r