【数据结构】排序 外部排序

外部排序不会考算法设计，考相关的概念和排序方法过程等。

1.外部排序的基本概念

外部排序是指对于记录很多的大文件进行排序时，无法将其完全复制进内存中进行排序，因此需要将外存中的待排记录一部分一部分地调入内存中进行排序，在排序过程中需要进行多次内存外存之间的交换，这种排序方法就称为外部排序。

2.外部排序的方法

文件在磁盘中通常是按块存储的，而磁盘读写所需时间远远超过内存运算的时间，所以外部排序中的时间代价主要由访问磁盘的次数(I/O次数) 决定。

外部排序的两个阶段：
1.根据内存缓冲区能容纳的大小，将外存上的待处理大文件分成若干个子文件
依次将子文件读入内存并在内存中进行内部排序，再将排序结果重新写回外存。这里称这些已经有序的子文件为归并段或顺串。
2.对这些已经有序的归并段进行逐趟归并，直至整个文件有序为止。
对归并段进行归并排序时，仍然需要在内存中进行，这时该如何处理？
对于两个归并段R1和R2，将内存分为三个缓冲区：两个输入缓冲区和一个输出缓冲区，每次将R1和R2的一部分放入两个输入缓冲区，进行归并排序，每当输出缓冲区满则从输出缓冲区读入外存中，当输入缓冲区中的一个空了时，则从外存中对应归并段中再读入，直到最终将两个归并段都排序完。


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

可以通过增大归并路数k，或减少初始归并段的个数r，来减少归并的趟数，从而减少读写磁盘的次数。

3.多路平衡归并与败者树

当增大归并路数和减少初始归并段个数时，又会使内部归并所需的时间增加，使得减少I/O次数带来的效益打折扣，所以这里想到使用其他的内部归并排序算法。