8-13外部排序-置换选择排序

效果：
构造更长的初始归并段
初始归并段的数量尽可能的少

以前的办法：
若文件共有n个记录，每个初始归并段只能包含l个记录（用于内部排序的内存工作区WA可容纳l个记录），则初始归并段数量r=n/l

现在的办法：
尝试构建一个比内存工作区更大的初始归并段

设一个缓冲区能存放3个元素，用于内部排序的内存工作区也只能容纳3个记录

将4、6、9放入输入缓冲区，依次处理

构造递增的归并段
用变量MINIMAX记录当前最小元素，此时MINIMAX=4，将4号放入输出缓冲区，凑足3个一起发往输出文件FO（读写磁盘必须以磁盘块为单位）（输出文件FO存放在磁盘中）

以下忽略缓冲区演示

7号填补，最小6，MINIMAX改为6，6输出

直到当前内存工作区WA的最小元素10 此时若把10输出，大于归并段中最大元素13，不满足要求
因此冻结10

选择下一个最小且大于MINIMAX的元素14，将MINIMAX改为14,14输出

最小且大于MINIMAX的元素16，将MINIMAX改为16,16输出


以此类推，直到3个都冻结，归并段1结束

将3个元素解冻，同样的方式构造第二个归并段

19输入，选择最小且大于MINIMAX的元素3，MINIMAX改为3，输出3

以此类推，直到处理完所有元素

通过置换-选择排序，可以超过内存工作区的限制，从而构造记录更长，数量更少的归并段，使得归并趟数减小，读写磁盘次数减少，效率更高。