外部排序的基本内容

1.内存空间：若要进行 k 路归并排序，则需要在内存中分配 k 个输入缓冲区和1个输出缓冲区
2.外部排序的实现步骤：①生成 r 个初始归并段（对 L 个记录进行内部排序，组成一个有序的初始归并段）②进行 S 趟 k 路归并， S = logk r向上取整
3.如何进行 k 路归并
把 k 个归并段的块读入 k 个输入缓冲区；用“归并排序”的方法从 k 个归并段中选出几个最小记录暂存到输出缓冲区中；当输出缓冲区满时，写出外存
4.外部排序的时间开销：读写外存的时间＋内部排序所需时间＋内部归并所需时间
5.外部排序的优化：①增加归并路数 k ,进行多路平衡归并：代价1：需要增加相应的输入缓冲区；代价2：每次从 k 个归并段中选一个最小元素需要（ k -1）次关键字对比②减少初始归并段数量r