第14周外排序第2讲-磁盘排序-生成初始归并段.pdf

磁盘排序过程磁盘排序过程 Fin文件文件 内存内存 读读写写 Fout文件文件 F1文件文件 F2文件文件 Fm文件文件 写写 写写 写写 内存内存 读读 读读 读读 生成若干初始归并段生成若干初始归并段 归并成一个有序文件归并成一个有序文件 设有一个文件设有一个文件Fin.dat，内含，内含4500个记录：个记录：A1,A2,A4500，现在要，现在要 对该文件进行排序，结果放在对该文件进行排序，结果放在Fout.dat文件中。可占用的内存空间至文件中。可占用的内存空间至 多只能对多只能对750个记录进行排序。个记录进行排序。 Fin.dat文件放文件放在在磁盘磁盘上。假设每个记录占用一个物理块。上。假设每个记录占用一个物理块。 磁盘排序磁盘排序示例演示示例演示 内存内存 (750) Fin.dat文件文件 Fout.dat文件文件 文件文件Fin.dat （含（含4500个记录）个记录） 容量为容量为750个记录个记录 产生产生6个长度为个长度为750 个记录的有序文件个记录的有序文件 F1F6。 第第1阶段：阶段：产生初始归并段产生初始归并段 某种内排序方法某种内排序方法 第第2阶段：阶段：多路归并多路归并 可用内存空间大小为可用内存空间大小为750个记录个记录 可以采用多种归并方案来完成可以采用多种归并方案来完成 F1F2 F7 F3F4 F8 F5F6 F9 F10 Fout 内存大小为内存大小为750个记录，但任意大小的两个归并段都可以进行归并。个记录，但任意大小的两个归并段都可以进行归并。 每归并一每归并一次次，参与，参与归并归并的每个记录的每个记录都要读都要读一一次和写次和写一次一次。 注意：注意： 归并方案归并方案1：二二路归并路归并1 方案方案1的读写记录数计算的读写记录数计算 总的读记录数（写记录数与之相同）：总的读记录数（写记录数与之相同）： (F1+F2+F3+F4的记录数的记录数) 3+(F5+F6的记录数的记录数) 2 =12000=8/3遍遍 该数越大，效率越差该数越大，效率越差等于哈夫曼等于哈夫曼树的树的WPL F1和和F2中中 每个记录每个记录 读读3次、次、 写写3次次 F1F2 F7 F3F4 F8 F5F6 F9 F10 Fout 方案方案2：总总的读记录数的读记录数WPL=15000。 方案方案1：总的读记录数总的读记录数WPL=12000。 归并方案归并方案2：二二路归并路归并2 F1F2 F7 F3F4F5F6 F8 Fout F9 F10 方案方案1 1更好更好 归并方案归并方案3：三三路归并路归并 F7 Fout F8 总的读记录数（写记录数与之相同）：总的读记录数（写记录数与之相同）： 方案方案3 :WPL(750+750+750) 2 (750+750+750) 29000 不同的归并方案所需要的读写记录数是不同的！不同的归并方案所需要的读写记录数是不同的！ 另一种方法：采用另一种方法：采用一种称为一种称为置换选择置换选择排序方法用于生成初始归排序方法用于生成初始归 并段并段。 11.2.1 生成初始生成初始归并归并段段 内存内存 abc.dat abc1.dat abc2.dat abcn.dat 均有序均有序 某内排序算法某内排序算法 生成生成前面的前面的初始归并段的方法初始归并段的方法 可以减少生成的初始归并段个数可以减少生成的初始归并段个数 （1）从待排文件从待排文件Fin中按内存工作区中按内存工作区WA的容量的容量w读入读入w个记录个记录。设归并段编设归并段编 号号i=1。 （2）使用败者树从使用败者树从WA中选出关键字最小的记录中选出关键字最小的记录Rmin。 （3）将将Rmin记录输出到记录输出到Fout中中，作为当前归并段的一个成员作为当前归并段的一个成员。 （4）若若Fin不空不空，则从则从Fin中读入下一个记录中读入下一个记录x放在放在Rmin所在的工作区位置代所在的工作区位置代 替替Rmin。 （5）在工作区在工作区中中所有所有Rmin的记录中选择出最小记录作为新的记录中选择出最小记录作为新的的Rmin，转转 （3），直到选不出这样的直到选不出这样的Rmin。 （6）设设i=i+1，开始一个新的归并段开始一个新的归并段。 （7）若工作区已空若工作区已空，则初始归并段已全部产生；否则转则初始归并段已全部产生；否则转（2）。 置换选择排序方法置换选择排序方法 【例例11- -1】 设磁盘文件中共有设磁盘文件中共有18个记录个记录，记录的关键字分别为：记录的关键字分别为： 15,4,97,64,17,32,108,44,76,9,39,82,56,31,80,73,255,68 若内存工作区可容纳若内存工作区可容纳5个记录，个记录，用用置换选择置换选择排序可产生几个排序可产生几个 初始归并段，每个初始归并段包含哪些记录初始归并段，每个初始归并段包含哪些记录? 置换置换- -选择排序选择排序示例演示示例演示 17 32944 7610839 82 56 31 80 7315497 64255 68 18个个记录（记录（w=5）：）： 内存内存工作区工作区w=5 归并段归并段1： 归并段归并段2： Rmin=415 1732 446476 82971089 依次类推，产生归并段依次类推，产生归并段2：9，31，39，56，68，73，80，255 置换置换- -选择选择排序中关键字比较次数分析排序中关键字比较次数分析 共有共有n个记录，个记录，内存工作区内存工作区WA的容量为的容量为w： 若在若在w个记录中选取最小关键字的采用简单比较方法，每个记录中选取最小关键字的采用简单比较方法，每 次需要次需要w- -1次比较。次比较。 总的时间复杂度为总的时间复杂度为O(nw)。 本讲完本讲完