归并过程对应的归并树abc1.databc2.databc3.databc4.databc5.dat5,63,8,91, 72, 10认真abc12.databc34.dat3,4,5,61,7,8,9abc1.dat中每个abc1234.dat元素读一次写一次（写入1，3，4，5.6,7,8，9abc12.dat)abc.dat1,2,3,4,5,6,7,8,9,1011/44
归并过程对应的归并树 5，6 abc1.dat 3，4 abc2.dat 3，4，5，6 abc12.dat 8，9 abc3.dat 1，7 abc4.dat 1，7，8，9 abc34.dat 1，3，4，5，6，7，8，9 abc1234.dat 1，2，3，4，5，6，7，8，9，10 abc.dat 2，10 abc5.dat abc1.dat中每个 元素读一次写一 次（写入 abc12.dat） 11/44
生成初始归并段的方法10.8.11．常规方法某内排序算法F1F2内存Fin均有序...FmWA为W得到m个有序文件Fi～Fm初始归并段，显然m=[n/w]。通常前m-1个有序文件的长度均为w，最后一个有序文件的长度小于等于w。12/44
1. 常规方法 Fin 内存 F1 F2 . Fm 均有序 某内排序算法 得到m个有序文件F1～Fm初始归并段，显然m=n/w。 通常前m-1个有序文件的长度均为w，最后一个有序文件的长度小 于等于w。 WA为w 12/44
2.置换-选择排序方法（1）从待排文件Fin中按内存工作区WA的容量w读入w个元素。设归并段编号i=1。（2）从WA中选出关键字最小的元素Rmin。（3）将Rmin元素输出到当前归并段Fi。（4）若Fin不空，则从Fin中读入下一个元素x放在Rmin所在的工作区位置代替Rmin。（5）在工作区中所有≥Rmin的元素中选择出最小元素作为新的Rmin，转（3），直到选不出这样的Rmin。（6）设+1，开始一个新的归并段。（7）若工作区已空，则初始归并段已全部产生；否则转（2）。13/44
2. 置换-选择排序方法 （1）从待排文件Fin中按内存工作区WA的容量w读入w个元素。设归并段编号i=1。 （2）从WA中选出关键字最小的元素Rmin。 （3）将Rmin元素输出到当前归并段Fi。 （4）若Fin不空，则从Fin中读入下一个元素x放在Rmin所在的工作区位置代替Rmin。 （5）在工作区中所有≥Rmin的元素中选择出最小元素作为新的Rmin，转（3），直 到选不出这样的Rmin。 （6）设i=i+1，开始一个新的归并段。 （7）若工作区已空，则初始归并段已全部产生；否则转（2）。 13/44
【例10.13】设磁盘文件中共有18个元素，元素的关键字分别为：(15，4,97,64，17,32,108，44,76，9,39,82，56，31，80,73,255,68)若内存工作区可容纳5个元素，用置换一选择排序可产生几个初始归并段，每个初始归并段包含哪些元素？14/44
【例10.13】设磁盘文件中共有18个元素，元素的关键字分别为： （15，4，97，64，17，32，108，44，76，9，39，82，56，31，80，73， 255，68） 若内存工作区可容纳5个元素，用置换－选择排序可产生几个初始归并段，每 个初始归并段包含哪些元素? 14/44
18个元素（W=5）：154.9764. 1732 108 44 76 9 3982 56 31 807325568Rmin=内存工作区W=5归并段1：归并段2：依次类推，产生归并段2：9，31，39，56，68，73，80，25515/44
15 4 97 64 17 32 108 44 76 9 39 82 56 31 80 73 255 68 ∞ 18个元素（w=5）： 内存工作区w=5 归并段1： 归并段2： Rmin= 41753244647682971089 依次类推，产生归并段2：9，31，39，56，68，73，80，255 15/44