《数据结构（C++版）（第二版）》课件第10章.ppt

1、2023年11月28日1第第10章章 外排序外排序本章学习内容 10.1 外排序的基本概念10.2 多路平衡归并的实现2023年11月28日210.1 外排序的基本概念外排序的基本概念内排序是直接在计算机内存中进行的。若要排序的数据一次可以装入计算机内存，则对这批数据的排序可以直接在内存中完成，因而，利用前面的内排序就可以了。若要排序的数据量很大，内存中一次装不下，要将数据放入外存（磁带、磁盘），这时，用内排序达不到我们的要求，必须用到本章介绍的外排序。而外排序是利用内存、外存来共同完成的。外排序可以看成由两个独立的阶段组成。首先，按可用内存的大小，将外存上含n个记录的文件分成若干长度为m的子

2、文件或段，依次读入内存并用上一章的内排序方法（一般用堆排序实现）完成每段的排序，再保存到外存；然后，对这些段进行归并，使归并段逐渐由小到大，直到得到整个文件有序为止。第一阶段就是上一章介绍的内排序方法，因此，本章主要讨论第二阶段的归并实现。第二阶段的归并有二路平衡归并和多路平衡归并。下面先给出例子来说明，具体实现方法见下一节。2023年11月28日3假设有一个含10000个记录的文件，内存一次只能装入1000个记录，则可以将文件分成10段，每段含1000个记录。首先通过10次内部排序得到10个初始归并段R1R10，其中每一段都含有1000个记录（已经有序），再保存到外存中，然后可以利用二路平衡

3、归并使整个文件有序。二路平衡归并见图10-1。图10-1 二路平衡归并过程 2023年11月28日4若对刚才的文件，首先通过10次内部排序得到10个初始归并段R1R10，其中每一段都含有1000个记录，再保存到外存中，然后也可以利用五路平衡归并使整个文件有序，五路平衡归并见图10-2。图10-2 五路平衡归并过程2023年11月28日5一般情况下，外排序所需总的时间=内排序所需时间（生成初始归并段）m*tIS+外存信息读写的时间d*tIO+平衡归并所需的时间s*utmg。m为初始归并段的个数，tIS是得到一个初始归并段进行内排序所需的时间均值；d为总的读写次数，tIO是进行一次外存读写时间的均

4、值；s为归并的趟数，utmg是对u个记录进行内部归并所需时间。对同一文件而言，假设有m个初始归并段，进行k路平衡归并，归并的趟数可以表示为s=logkm。若增加k或减少m则可以减少s，外排序所需总的时间就可以减少。2023年11月28日610.2 多路平衡归并的实现多路平衡归并的实现10.2.1 初始归并段的生成假设初始待排文件为输入文件FI，初始归并段文件为输出文件FO，内存工作区为WA，FO和WA的初始状态为空，并假设内存工作区WA的容量为W个记录，则生成初始归并段的操作过程为：(1)从FI输入W个记录到工作区WA。(2)从WA中选关键字最小的记录，记为MINKEY。(3)将MINKEY记

5、录输出到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个记录）。2023年11月28日7FOWAFI

6、51,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,

7、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,

8、76表10-1 生成初始归并段 2023年11月28日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

9、,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 生成初始归并段(续)2023年11月28日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,4

10、658,764,13,24,33,46,58764,13,24,33,46,58,76表10-1 生成初始归并段(续)2023年11月28日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,6

11、3,89 4,13,24,33,46,58,761,3,14,15,27,29,30,38,39,46,48,49,51,52,61,63,89 4,13,24,33,46,58,761,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,761,3,4,13,14,15,24,27,29,30,33,38,39,46,46,48,49,51,52,

12、58,61,63,76,892023年11月28日1110.2.2 多路平衡归并的实现1.多路平衡归并的败者树将9.4.2节中树形选择排序得到的树称为胜者树（每次选最小的关键字），因为每个非终端结点均表示其左、右孩子结点中的“胜者”。反之，若在双亲结点中记下刚进行比赛的“败者”，而让胜者去参加更高一层的比赛，则可以得到一棵“败者树”。现以五路平衡归并为例来建立“败者树”，假设已经用前面的方法得到五个初始归并段为（其中 表示该段的结束）：第一归并段B0：17，21，第二归并段B1：05，44，第三归并段B2：10，12，第四归并段B3：29，32，第五归并段B4：15，56，2023年11月28

13、日12在建立“败者树”中，按完全二叉树形式，从每个初始归并段取一个关键字（第一个），作为“败者树”的叶子结点，用B0B4表示，而非叶子结点用Ls1Ls4表示，表示两者比较的败者，Ls0表示整个比较的胜者。B3和B4比较，B3为败者，将它的段号存入Ls4中，B3和B4的胜者再与B0比较，败者为B0，将它的段号存入Ls2中，B1与B2比较，败者的段号存入Ls3中，B0、B1、B2、B3、B4比较的败者段号存入Ls1中，胜者的段号存入Ls0中，得到的败者树见图10-3。4 0 3 2 1 17 05 10 15 29 Ls0 Ls1 Ls2 B0 Ls3 B1 B2 Ls4 B4 B3 图10-3

14、五路归并建立的初始败者树2023年11月28日132.多路平衡归并的实现多路平衡归并的实现，是反复调整败者树，并输出Ls0的值，直到树中叶结点都表示为 。现以五路平衡归并举例说明。【例10-1】假设有五个初始归并段为（其中 表示该段的结束）：第一归并段B0：17，21，第二归并段B1：05，44，第三归并段B2：10，12，第五归并段B4：15，56，第四归并段B3：29，32，试用“败者树”实现五路平衡归并，并给出归并的结果。2023年11月28日14解：先建立初始败者树，然后不断的调整败者树，并输出Ls0所对应段的值，直到树中叶结点都表示为 。具体实现过程见图10-4各步骤。4 0 3 2

15、 1 17 05 10 15 29 Ls0 Ls1 Ls2 B0 Ls3 B1 B2 Ls4 B4 B3 4 0 3 1 2 17 44 10 15 29 Ls0 Ls1 Ls2 B0 Ls3 B1 B2 Ls4 B4 B3（a）生成的初始败者树(b)输出05后的败者树 2023年11月28日15 4 0 3 1 2 17 44 12 15 29 Ls0 Ls1 Ls2 B0 Ls3 B1 B2 Ls4 B4 B3 1 0 3 2 4 17 44 15 29 Ls0 Ls1 Ls2 B0 Ls3 B1 B2 Ls4 B4 B3（c）输出05,10后的败者树 (d)输出05,10,12后的败者树

16、 1 3 4 2 0 17 44 56 29 Ls0 Ls1 Ls2 B0 Ls3 B1 B2 Ls4 B4 B3 1 3 4 2 0 21 44 56 29 Ls0 Ls1 Ls2 B0 Ls3 B1 B2 Ls4 B4 B3（e）输出05,10,12,15后的败者树 (f)输出05,10,12,15,17后的败者树 2023年11月28日16 1 0 4 2 3 44 56 29 Ls0 Ls1 Ls2 B0 Ls3 B1 B2 Ls4 B4 B3 1 0 4 2 3 44 56 32 Ls0 Ls1 Ls2 B0 Ls3 B1 B2 Ls4 B4 B3（g）输出05,10,12,15,1

17、7,21后的败者树(h)输出05,10,12,15,17,21,29后的败者树 4 0 3 2 1 44 56 Ls0 Ls1 Ls2 B0 Ls3 B1 B2 Ls4 B4 B3 1 0 3 2 4 56 Ls0 Ls1 Ls2 B0 Ls3 B1 B2 Ls4 B4 B3（i）输出05,10,12,15,17,21,29,32后败者树(j)输出05,10,12,15,17,21,29,32,44后败者树 2023年11月28日17 1 0 3 2 4 Ls0 Ls1 Ls2 B0 Ls3 B1 B2 Ls4 B4 B3(k)输出05,10,12,15,17,21,29,32,44,56后败

18、者树图10-4 利用败者树实现五路平衡归并 2023年11月28日183.多路平衡归并的算法实现#include#define MAXKEY 32767 /定义最大值#define min 0 /定义最小值#define k 5 /K路平衡归并int lsk;/败者树中非叶子结点的存储空间int bk+1;/败者树中叶子结点的存储空间void adjust(int lsk,int s)int t=(s+k)/2;int temp;while(t0)if(bsblst)temp=s;s=lst;lst=temp;t=t/2;ls0=s;2023年11月28日19void createlosttr

19、ee(int lsk)/建立败者树 for(int i=0;i=0;-i)adjust(ls,i);void k_merge(int lsk,int bk)/K路平衡归并 for(int i=0;ibi;/输入叶子结点的值 createlosttree(ls);while(bls0!=MAXKEY)int q=ls0;coutbqbq;/输入最小值所属段的下一个值 adjust(ls,q);/重新调整败者树 coutbls0 ;/输出最小值void main()k_merge(ls,b);2023年11月28日20对例10-1的五个初始归并段，可按如下输入执行：17 05 10 29 15（回车键）44123276756213276732327673276732767最后输出的结果为：5 10 12 15 17 21 29 32 44 56