十章节外部排序十章节外部排序本章内容本章内容p外存信息的存取p外部排序的基本方法归并排序法p多路平衡归并p置换-选择排序胜者树胜者树(树形选择排序树形选择排序) 6 8 6 8 9 8 9 6 8 90 9 15 8 90 10 9 20 6 8 12 10 9 20 15 8 12 10 9 20 6 8 12 90 10 9 20 15 8 12 90 14 22 24 15 16 17 92 14 22 24 25 16 17 92 26 38 30 25 50 18 97 26 38 30 50 18 97 7路合并胜者树路合并胜者树 重构后的胜者树重构后的胜者树 重构胜者树时，从根结点至新补入记录的叶结点的重构胜者树时，从根结点至新补入记录的叶结点的路径上的所有结点都必须更新。路径上的所有结点都必须更新。败者树败者树 5 2 2 0 4 0 1 3 6 90 1 3 6 90 10 9 20 6 8 12 10 9 20 15 8 12 10 9 20 6 8 12 90 10 9 20 15 8 12 90 14 22 24 15 16 11 92 14 22 24 25 16 11 92 26 38 30 25 50 18 97 26 38 30 50 18 97 7路合并败者树 重构后的败者树败者树的特点：记录败者，胜者参加下一轮比赛 败者树的优点：重构时修改结点较少01 2 3 4 5 64ls05ls01 2 3 4 5 60 4 5 2 0 1 3 6 90 0 10 9 20 6 8 12 1 2 3 4 5 6调整败者树的方法: 将新补充的结点与其双亲结点比较, 败者留在该双亲结点,胜者继续向上直至树根的双亲以在b4补充15为例154与3比较4与2比较42与5比较25调整败者树的方法调整败者树的方法 7 7 7 7 7 7 7 90 0 10 9 20 6 8 12 1 2 3 4 5 6k-路归并对内存的要求路归并对内存的要求 至少要有k个输入缓冲区和一个输出缓冲区建败者树的过程7 -1初始化败者树调整b66调整b55调整b44调整b334调整b22调整b1124调整b0054建败者树的过程建败者树的过程数据结构数据结构 (依据：败者树为完全二叉树)p主：b0. k b0. k-1k个叶结点 ，存放k个输入归并段中当前 参加归并的记录（缓冲区） bk虚拟记录，该关键字取可能的最小值minkeyp辅：ls0. k-1 不含叶结点的败者树 存放最后胜出的编号（ls0）以及所记录的败者编号处理步骤处理步骤p建败者树ls0. k-1p重复下列操作直至k路归并完毕n将将bls0写至输出归并段写至输出归并段n补充记录补充记录(某归并段变空时某归并段变空时,补补 )，调整败者树，调整败者树多路平衡归并算法多路平衡归并算法算法描述：建立败者树算法描述：建立败者树void CreateLoserTree() bk = MINKEY; for (i = 0; i = 0; i+) Adjust(i);void Adjust(int s) for (t = (s + k) / 2; t 0; t /= 2) if (bs blst) s lst; ls0 = s;算法描述算法描述: K路合并路合并void K_Merge() for (i = 0; i k; i+) input(i); /* 第i路输入一个元素到bi */ CreateLoserTree(ls); while (bls0 != MAXKEY) q = ls0; output(bq); input(q); Adjust(q); 置置 换换 - 选选 择择 排排 序序置换置换-选择排序选择排序目标目标 扩大初始归并段长度，突破内存工作区容量(设w个记录)的限制。置换置换-选择排序原理选择排序原理 内存 外存 原始文件 内存工作区 FI WA 初始归并段文件 (w个记录) FO 为简化问题，设每个物理块存放一个记录为简化问题，设每个物理块存放一个记录1) 从FI输入w个记录到工作区WA；2) 在FO中标记一个归并段开始；3) 从WA中选出最小关键字记录，记为minimax记录；4) 将minimax记录输出到FO中；5) 从FI输入下一个记录到WA中；6) 在WA中的关键字比minimax大的记录中选出关键字最小的记录 6.1) 若不能选到，在FO中标记一个归并段结束； 若由于WA为空而未选出，则结束处理； 否则，标记下一个归并段开始，转 3) 6.2) 否则，将选出的记录作为新的minimax记录，转 4) 示例示例 利用败者树利用败者树( (教材教材303303页图页图11.6)11.6) FO WA(4个记录) FI 空 空 36,21,33,87,23,7,62,16, 54,43,29, 空 36,21,33,87 23,7,62,16,54, 43,29, 21 36,23,33,87 7,62,16,54, 43,29, 21,23 36,7,33,87 62,16,54,43,29, 21,23,33 36,7,62,87 16,54,43,29, 21,23,33,36 16,7,62,87 54,43,29, 21,23,33,36,62 16,7,54,87 43,29, 21,23,33,36,62,87 16,7,54,43 29, 21,23,33,36,62,87|7 16,29,54,43 p处理步骤处理步骤 1)初始化败者树： 1.1)所有外部结点： rnum=0; key=0；所有内部结点置0； 1.2)对外部结点从编号w-1至0 从外存FI读入记录，置段号为1，并调整败者树 2)置当前段号为1； 3)若ls0指示的外部结点属于当前段，输出该记录； 否则,当前段号+1，输出段标后再输出该记录； 4)若FI未空，从FI补充记录， 若补充key此前输出记录的key，则rnum=当前段号+1 否则rnum=当前段号 否则补虚记录：key=; rnum=当前段号+1； 5)调整败者树 转3）直至所有记录被输出调整败者树原则：段号小者为胜者段号相同，关键字小的为胜者置换置换-选择排序的效果选择排序的效果p所得初始排序段的长度不等p当输入文件记录的关键字大小随机分布时，初始归并段的平均长度为内存工作区大小w的两倍最最 佳佳 归归 并并 树树最佳归并树最佳归并树文件经过置换文件经过置换-选择排序之后，得到长度不等的初始归并选择排序之后，得到长度不等的初始归并段，进行段，进行k路归并时，初始归并段的不同搭配，会导致路归并时，初始归并段的不同搭配，会导致归并过程中归并过程中I/O的次数的次数不同。不同。设有9个初始归并段，记录个数(长度)分别为： 9，30，12，18，3，17，2，6，24 121 121 51 38 32 30 32 59 9 30 12 18 3 17 2 6 24 11 9 12 17 18 24 2 3 6(9+30+12+18+3+17+2+6+24)2 (2+3+6) 3+(9+12+17+(51+38+32) 2 +18+24) 2+30 1 2=484 =4463-路归并所有叶结点加权外通路长度的所有叶结点加权外通路长度的2 2倍倍IO方案二方案一最佳归并树的构造最佳归并树的构造最佳归并树即k叉(阶)哈夫曼树。 设初始归并段为m个，进行k-路归并1）若 (m-1) mod (k-1) 0 则需附加(k-1)- (m-1) mod (k-1) 个长度为0的虚段，以使每次归并都可以对应k个段2）按照哈夫曼树的构造原则（权值越小的结点离根结点越远）构造最佳归并树。k k阶哈夫曼树阶哈夫曼树示例示例 长度分别为2，3，6，9，12，17，18，24的8个初始归并段进行3路归并，求最佳归并树。 91 20 24 47 5 6 9 12 17 18 0 2 3I/O次数： (2+3)3 + (6+9+12+17+18)2 + 241 2 = 326作业作业1. 假设一次I/O的物理块可容纳150个记录，每次可对750个记录进行内部排序，那么对含有150000个记录的磁盘文件进行4-路平衡归并排序时，共需进行多少次I/O？2.已知某文件经过置换-选择排序之后，得到长度分别为47，9，31，18，4，12，23和7（单位均为物理块）的8个初始归并段。试为3-路平衡归并设计一个读写外存次数最少的归并方案，并求出读写外存的次数。3.在外排序中怎样减少排序的总时间？