8.【外部排序】基本概念和方法 + 优化：【败者树】{减少关键字对比次数}、【置换-选择 排序】{减少初始归并段数量}、【最佳归并树】{谁先合并更快}
文章目录
- 外部排序的基本概念和方法
- 1. 外部排序的步骤
- 2. `外部排序时间开销` = **读写外存的时间 + 内部排序所需时间＋内部归并所需时间**
- 3. 优化
- 4. 纠正：什么是多路平衡归并？
- 败者树【减少关键字对比次数】
- 置换-选择 排序【减少初始归并段数量】
- 最佳归并树【解决：归并段谁和谁合并更快？】
外部排序的基本概念和方法
外部排序：对大文件进行排序时，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序。
因此需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换。
1. 外部排序的步骤
① 根据内存缓冲区大小，将外存上的文件分成 r 个子文件，依次读入内存并利用内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写回外存【目的：形成一个归并段,共r个归并段】。
② 对这r个有序归并段进行 S 趟 k 路归并，使归并段（有序子文件)逐渐由小到大，直至得到整个有序文件为止，其中 S=⌈logkr⌉。（需要在内存中分配k个输入缓冲区和1个输出缓冲区）注：如何进行 k 路归并？
① 把【k个归并段的块】读入【k个输入缓冲区】。
② 用“归并排序”的方法，从k个归并段中，选出几个最小记录暂存到输出缓冲区中。
③ 当输出缓冲区满时，写出外存。就是归并排序的过程，只不过有空间的限制
2. 外部排序时间开销 = 读写外存的时间 + 内部排序所需时间＋内部归并所需时间
3. 优化
①增加归并路数k【就是k合一】，但是需要增加相应的输入缓冲区，且每次从k个归并段中，选出一个最小元素需要对比 (k-1) 次。
②减少初始归并段数量r。
4. 纠正：什么是多路平衡归并？
例子：
败者树【减少关键字对比次数】
败者树解决的问题：
从 k 个归并段选出一个最小元素需要对比关键字 (k-1) 次，而构造败者树可以使关键字对比次数减少到⌈ log2 k ⌉
过程：
初始8个有序归并段
找出第一个最小的：
故第一次找出最小的是段3，值为1
随后把值为1的结点去掉，用段3的下一个代替，更新败者树，等到下一个最小为段5,值为2【总共对比了3次——log2 8】
随后把值为2的结点去掉，用段5的下一个代替，以此重复进行
败者树的实现思路：
例子：
置换-选择 排序【减少初始归并段数量】
产生更长的初始归并段，从而减少初始归并段数量
初始
过程：
当集满3个红色，开始归并段2
如果是原始的话，需24/3=8个归并段
最佳归并树【解决：归并段谁和谁合并更快？】
构造2路归并的最佳归并树：
多路归并的最佳归并树：
如果减少⼀个归并段：
添加虚段的数量：
