【数据结构】排序——外部排序（1）
外部排序是指大文件的排序，即排序的记录存储在外存储器上，在排序过程中需进行多次的内、外存之间的交换。
外部排序方法
通常采用归并排序
有外部排序基本上由两个相对独立的阶段组成。
按可用内存大小，将外存上含有n个记录的文件分成若干长度为l的字文件或段。
依次读入内存并利用有效的内部排序方法排序，将排序后得到的有序子文件（称为归并段或顺串），进行逐趟归并，直至得到整个有序文件为止。
在外部排序中实现两两归并，由于不可能将两个有序段及归并结果段同时存放在内存中的缘故，所以不仅要调用归并过程，还需要进行外存的读_写（对外存上信息的读_写是以“物理块”为单位的）。
耗费时间
总时间=内部排序时间(产生初始归并段)+外存读写时间+内部归并时间
内部排序时间=经过内部排序后得到的初始归并段的个数r * 得到一个初始归并段进行内部排序多需时间的均值
外存读写时间=总的读写次数 * 进行一次外存读写时间的均值
内部归并时间=归并的趟数s * n个记录进行内部归并排序的时间
优化方法
- 增大归并路数k
- 减少初始归并段个数r
以上两个方法都可以减少归并的趟数，进而减少读写磁盘的次数，提高外部排序速度
多路平衡归并与败者树
已知增加k可以减少s，从而减少总的读写次数。如果只单纯的增加k又会导致内部归并时间增加。为了使内部归并不受k的增大而影响，提出了败者树。
败者树的基本思想
败者树是树形选择排序的一种变型，可视为一棵完全二叉树。
k个叶子节点分别存放k个归并段在归并过程中当前参加比较的记录，内部节点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点。
若比较两个数，大的为败者、小的为胜利者，则根结点指向的数为最小数。
eg、设初始归并段为(10,15,31),(9,20),(6,15,42),(12,37),(84,95),利用败者树进行m路归并，手工执行选择最小的5个关键字的过程。
性能分析
k-路归并的败者树的深度为[log2k]+1
注意
归并路数并不是越大越好。归并路数k增大时，相应第需要怎家属如缓冲区的个数。k值过大时，虽然归并趟数会减少，但读写外层的次数仍然会增加。
优化
- 增加归并路数k，进行多路平衡归并
代价1.需要增加相应的输入缓冲区。
代价2.每次从k个归并段中选最小元素需要（k-1）关键字对比。 - 减少初始归并段数量r。