外部排序的基本概念和方法

外部排序：对大文件进行排序时，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序。
因此需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换。

1. 外部排序的步骤

① 根据内存缓冲区大小，将外存上的文件分成 r 个子文件，依次读入内存并利用内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写回外存【目的：形成一个归并段,共r个归并段】。

 
② 对这r个有序归并段进行 S 趟 k 路归并，使归并段（有序子文件)逐渐由小到大，直至得到整个有序文件为止，其中S=⌈log_k​r⌉。（需要在内存中分配k个输入缓冲区和1个输出缓冲区）

注：如何进行 k 路归并？
① 把【k个归并段的块】读入【k个输入缓冲区】。
② 用“归并排序”的方法，从k个归并段中，选出几个最小记录暂存到输出缓冲区中。
③ 当输出缓冲区满时，写出外存。

就是归并排序的过程，只不过有空间的限制

2. 外部排序时间开销 =读写外存的时间 + 内部排序所需时间＋内部归并所需时间

3. 优化

①增加归并路数k【就是k合一】，但是需要增加相应的输入缓冲区，且每次从k个归并段中，选出一个最小元素需要对比 (k-1) 次。
②减少初始归并段数量r。

4. 纠正：什么是多路平衡归并？

例子：

败者树【减少关键字对比次数】

败者树解决的问题：
从 k 个归并段选出一个最小元素需要对比关键字 (k-1) 次，而构造败者树可以使关键字对比次数减少到⌈ log₂ k ⌉

过程：
初始8个有序归并段

找出第一个最小的：


故第一次找出最小的是段3，值为1
随后把值为1的结点去掉，用段3的下一个代替，更新败者树，等到下一个最小为段5,值为2【总共对比了3次——log₂ 8】

随后把值为2的结点去掉，用段5的下一个代替，以此重复进行

败者树的实现思路：

例子：

置换-选择 排序【减少初始归并段数量】

产生更长的初始归并段，从而减少初始归并段数量

初始

过程：

当集满3个红色，开始归并段2

如果是原始的话，需24/3=8个归并段

最佳归并树【解决：归并段谁和谁合并更快？】

构造2路归并的最佳归并树：

多路归并的最佳归并树：

如果减少⼀个归并段：

添加虚段的数量：