《数据结构(C++版)(第二版)》第10章

2020年1月30日1第10章外排序本章学习内容10.1外排序的基本概念10.2多路平衡归并的实现2020年1月30日210.1外排序的基本概念内排序是直接在计算机内存中进行的。若要排序的数据一次可以装入计算机内存，则对这批数据的排序可以直接在内存中完成，因而，利用前面的内排序就可以了。若要排序的数据量很大，内存中一次装不下，要将数据放入外存（磁带、磁盘），这时，用内排序达不到我们的要求，必须用到本章介绍的外排序。而外排序是利用内存、外存来共同完成的。外排序可以看成由两个独立的阶段组成。首先，按可用内存的大小，将外存上含n个记录的文件分成若干长度为m的子文件或段，依次读入内存并用上一章的内排序方法（一般用堆排序实现）完成每段的排序，再保存到外存；然后，对这些段进行归并，使归并段逐渐由小到大，直到得到整个文件有序为止。第一阶段就是上一章介绍的内排序方法，因此，本章主要讨论第二阶段的归并实现。第二阶段的归并有二路平衡归并和多路平衡归并。下面先给出例子来说明，具体实现方法见下一节。2020年1月30日3假设有一个含10000个记录的文件，内存一次只能装入1000个记录，则可以将文件分成10段，每段含1000个记录。首先通过10次内部排序得到10个初始归并段R1~R10，其中每一段都含有1000个记录（已经有序），再保存到外存中，然后可以利用二路平衡归并使整个文件有序。二路平衡归并见图10-1。R1R2R3R4R5R6R7R8R9R10R1’R2’R3’R4’R5’R1’’R2’’R3’’R1’’’R2’’’有序文件图10-1二路平衡归并过程2020年1月30日4若对刚才的文件，首先通过10次内部排序得到10个初始归并段R1~R10，其中每一段都含有1000个记录，再保存到外存中，然后也可以利用五路平衡归并使整个文件有序，五路平衡归并见图10-2。R1R2R3R4R5R6R7R8R9R10R1’R2’有序文件图10-2五路平衡归并过程2020年1月30日5一般情况下，外排序所需总的时间=内排序所需时间（生成初始归并段）m*tIS+外存信息读写的时间d*tIO+平衡归并所需的时间s*utmg。m为初始归并段的个数，tIS是得到一个初始归并段进行内排序所需的时间均值；d为总的读写次数，tIO是进行一次外存读写时间的均值；s为归并的趟数，utmg是对u个记录进行内部归并所需时间。对同一文件而言，假设有m个初始归并段，进行k路平衡归并，归并的趟数可以表示为s=logkm。若增加k或减少m则可以减少s，外排序所需总的时间就可以减少。2020年1月30日610.2多路平衡归并的实现10.2.1初始归并段的生成假设初始待排文件为输入文件FI，初始归并段文件为输出文件FO，内存工作区为WA，FO和WA的初始状态为空，并假设内存工作区WA的容量为W个记录，则生成初始归并段的操作过程为：(1)从FI输入W个记录到工作区WA。(2)从WA中选关键字最小的记录，记为MINKEY。(3)将MINKEY记录输出到FO中。(4)若FI不空，则从FI输入下一个记录到WA中。(5)从WA中选比MINKEY大的所有关键字中选最小的关键字，作为新的MINKEY。(6)重复（3）~（5），直到WA中选不出新的MINKEY为止，由此得到一个初始归并段。(7)重复（2）~（6）直到WA为空。则得到全部初始归并段。例如，给定初始文件含有24个记录，对应的关键字分别为：51，49，39，46，38，29，14，61，15，30，1，48，52，3，63，27，4，13，89，24，46，58，33，76。利用上面的方法生成初始归并段过程如下表（假设内存工作区WA的容量为6个记录）。2020年1月30日7FOWAFI51,49,39,46,38,29,14,61,15,30,1,48,52,3,63,27,4,13,89,24,46,58,33,76第一归并段51,49,39,46,38,2914,61,15,30,1,48,52,3,63,27,4,13,89,24,46,58,33,762951,49,39,46,38,1461,15,30,1,48,52,3,63,27,4,13,89,24,46,58,33,7629,3851,49,39,46,61,1415,30,1,48,52,3,63,27,4,13,89,24,46,58,33,7629,38,3951,49,15,46,61,1430,1,48,52,3,63,27,4,13,89,24,46,58,33,7629,38,39,4651,49,15,30,61,141,48,52,3,63,27,4,13,89,24,46,58,33,7629,38,39,46,4951,1,15,30,61,1448,52,3,63,27,4,13,89,24,46,58,33,7629,38,39,46,49,5148,1,15,30,61,1452,3,63,27,4,13,89,24,46,58,33,7629,38,39,46,49,51,6148,1,15,30,52,143,63,27,4,13,89,24,46,58,33,76表10-1生成初始归并段2020年1月30日8第二归并段148,3,15,30,52,1463,27,4,13,89,24,46,58,33,761,348,63,15,30,52,1427,4,13,89,24,46,58,33,761,3,1448,63,15,30,52,274,13,89,24,46,58,33,761,3,14,1548,63,4,30,52,2713,89,24,46,58,33,761,3,14,15,2748,63,4,30,52,1389,24,46,58,33,761,3,14,15,27,3048,63,4,89,52,1324,46,58,33,761,3,14,15,27,30,4824,63,4,89,52,1346,58,33,761,3,14,15,27,30,48,5224,63,4,89,46,1358,33,761,3,14,15,27,30,48,52,6324,58,4,89,46,1333,761,3,14,15,27,30,48,52,63,8924,58,4,33,46,1376表10-1生成初始归并段(续)2020年1月30日9第三归并段424,58,76,33,46,134,1324,58,76,33,464,13,2458,76,33,464,13,24,3358,76,464,13,24,33,4658,764,13,24,33,46,58764,13,24,33,46,58,76表10-1生成初始归并段(续)2020年1月30日10从表10-1可知，上面的24个记录可以生成三个初始归并段分别为：第一归并段R0：29,38,39,46,49,51,61第二归并段R1：1,3,14,15,27,30,48,52,63,89第三归并段R2：4,13,24,33,46,58,76上面的三个初始归并段都是有序序列，故可以用二路平衡归并进行排序或用三路平衡归并进行排序。若用二路平衡归并，可以得到如下结果：[29,38,39,46,49,51,61][1,3,14,15,27,30,48,52,63,89][4,13,24,33,46,58,76][1,3,14,15,27,29,30,38,39,46,48,49,51,52,61,63,89][4,13,24,33,46,58,76][1,3,4,13,14,15,24,27,29,30,33,38,39,46,46,48,49,51,52,58,61,63,76,89]若用三路平衡归并，可以得到如下结果：[29,38,39,46,49,51,61][1,3,14,15,27,30,48,52,63,89][4,13,24,33,46,58,76][1,3,4,13,14,15,24,27,29,30,33,38,39,46,46,48,49,51,52,58,61,63,76,89]2020年1月30日1110.2.2多路平衡归并的实现1.多路平衡归并的败者树将9.4.2节中树形选择排序得到的树称为胜者树（每次选最小的关键字），因为每个非终端结点均表示其左、右孩子结点中的“胜者”。反之，若在双亲结点中记下刚进行比赛的“败者”，而让胜者去参加更高一层的比赛，则可以得到一棵“败者树”。现以五路平衡归并为例来建立“败者树”，假设已经用前面的方法得到五个初始归并段为（其中表示该段的结束）：第一归并段B0：[17，21，]第二归并段B1：[05，44，]第三归并段B2：[10，12，]第四归并段B3：[29，32，]第五归并段B4：[15，56，]2020年1月30日12在建立“败者树”中，按完全二叉树形式，从每个初始归并段取一个关键字（第一个），作为“败者树”的叶子结点，用B[0]~B[4]表示，而非叶子结点用Ls[1]~Ls[4]表示，表示两者比较的败者，Ls[0]表示整个比较的胜者。B[3]和B[4]比较，B[3]为败者，将它的段号存入Ls[4]中，B[3]和B[4]的胜者再与B[0]比较，败者为B[0]，将它的段号存入Ls[2]中，B[1]与B[2]比较，败者的段号存入Ls[3]中，B[0]、B[1]、B[2]、B[3]、B[4]比较的败者段号存入Ls[1]中，胜者的段号存入Ls[0]中，得到的败者树见图10-3。403211705101529Ls[0]Ls[1]Ls[2]B[0]Ls[3]B[1]B[2]Ls[4]B[4]B[3]图10-3五路归并建立的初始败者树2020年1月30日132.多路平衡归并的实现多路平衡归并的实现，是反复调整败者树，并输出Ls[0]的值，直到树中叶结点都表示为。现以五路平衡归并举例说明。【例10-1】假设有五个初始归并段为（其中表示该段的结束）：第一归并段B0：[17，21，]第二归并段B1：[05，44，]第三归并段B2：[10，12，]第五归并段B4：[15，56，]第四归并段B3：[29，32，]试用“败者树”实现五路平衡归并，并给出归并的结果。2020年1月30日14解：先建立初始败者树，然后不断的调整败者树，并输出Ls[0]所对应段的值，直到树中叶结点都表示为。具体实现过程见图10-4各步骤。403211705101529Ls[0]Ls[1]Ls[2]B[0]Ls[3]B[1]B[2]Ls[4]B[4]B[3]403121744101529Ls[0]Ls[1]Ls[2]B[0]Ls[3]B[1]B[2]Ls[4]B[4]B[3]（a）生成的初始败者树(b)输出05后的败者树2020年1月30日15403121744121529Ls[0]Ls[1]Ls[2]B[0]Ls[3]B[1]B[2]Ls[4]B[4]B[3]1032417441529Ls[0]Ls[1]Ls[2]B[0]Ls[3]B[1]B[2]Ls[4]B[4]B[3]（c）输出05,10后的败者树(d)输出05,10,12后的败者树1342017445629Ls[0]Ls[1]Ls[2]B[0]Ls[3]B[1]B[2]Ls[4]B[4]B[3]1342021445629Ls[0]Ls[1]Ls[2]B[0]Ls[3]B[1]B[2]Ls[4]B[4]B[3]（e）输出05,10,12,15后的败者树(f)输出05,10,12,15,17后的败者树2020年1月30日1610423445629Ls[0]Ls[1]Ls[2]B[0]Ls[3]B[1]B[2]Ls[4]B[4]B[3]10423445632Ls[0]Ls[1]Ls[2]B[0]Ls[3]B[1]B[2]Ls[4]B[4]B[3]（g）输出05,10,12,15,17,21后的败者树(h)输出05,10,12,15,17,21,29后的败者树40321