《《数据结构(C++版)(第二版)》第10章.ppt》由会员分享，可在线阅读，更多相关《《数据结构(C++版)(第二版)》第10章.ppt（20页珍藏版）》请在三一办公上搜索。
1、2023/5/30,1,第10章 外排序,本章学习内容,10.1 外排序的基本概念,10.2 多路平衡归并的实现,2023/5/30,2,10.1 外排序的基本概念,内排序是直接在计算机内存中进行的。若要排序的数据一次可以装入计算机内存，则对这批数据的排序可以直接在内存中完成，因而，利用前面的内排序就可以了。若要排序的数据量很大，内存中一次装不下，要将数据放入外存（磁带、磁盘），这时，用内排序达不到我们的要求，必须用到本章介绍的外排序。而外排序是利用内存、外存来共同完成的。,外排序可以看成由两个独立的阶段组成。首先，按可用内存的大小，将外存上含n个记录的文件分成若干长度为m的子文件或段，依次读
2、入内存并用上一章的内排序方法（一般用堆排序实现）完成每段的排序，再保存到外存；然后，对这些段进行归并，使归并段逐渐由小到大，直到得到整个文件有序为止。第一阶段就是上一章介绍的内排序方法，因此，本章主要讨论第二阶段的归并实现。,第二阶段的归并有二路平衡归并和多路平衡归并。下面先给出例子来说明，具体实现方法见下一节。,2023/5/30,3,假设有一个含10000个记录的文件，内存一次只能装入1000个记录，则可以将文件分成10段，每段含1000个记录。首先通过10次内部排序得到10个初始归并段R1R10，其中每一段都含有1000个记录（已经有序），再保存到外存中，然后可以利用二路平衡归并使整个文
3、件有序。二路平衡归并见图10-1。,图10-1 二路平衡归并过程,2023/5/30,4,若对刚才的文件，首先通过10次内部排序得到10个初始归并段R1R10，其中每一段都含有1000个记录，再保存到外存中，然后也可以利用五路平衡归并使整个文件有序，五路平衡归并见图10-2。,图10-2 五路平衡归并过程,2023/5/30,5,一般情况下，外排序所需总的时间=内排序所需时间（生成初始归并段）m*tIS+外存信息读写的时间d*tIO+平衡归并所需的时间s*utmg。,m为初始归并段的个数，tIS是得到一个初始归并段进行内排序所需的时间均值；d为总的读写次数，tIO是进行一次外存读写时间的均值；
4、s为归并的趟数，utmg是对u个记录进行内部归并所需时间。,对同一文件而言，假设有m个初始归并段，进行k路平衡归并，归并的趟数可以表示为s=logkm。若增加k或减少m则可以减少s，外排序所需总的时间就可以减少。,2023/5/30,6,10.2 多路平衡归并的实现,10.2.1 初始归并段的生成,假设初始待排文件为输入文件FI，初始归并段文件为输出文件FO，内存工作区为WA，FO和WA的初始状态为空，并假设内存工作区WA的容量为W个记录，则生成初始归并段的操作过程为：,(1)从FI输入W个记录到工作区WA。(2)从WA中选关键字最小的记录，记为MINKEY。(3)将MINKEY记录输出到FO
5、中。(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/5/30,7,表10-1 生成初始
6、归并段,2023/5/30,8,表10-1 生成初始归并段(续),2023/5/30,9,表10-1 生成初始归并段(续),2023/5/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,
7、48,52,63,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,
8、49,51,52,58,61,63,76,89,2023/5/30,11,10.2.2 多路平衡归并的实现,1.多路平衡归并的败者树,将节中树形选择排序得到的树称为胜者树（每次选最小的关键字），因为每个非终端结点均表示其左、右孩子结点中的“胜者”。反之，若在双亲结点中记下刚进行比赛的“败者”，而让胜者去参加更高一层的比赛，则可以得到一棵“败者树”。,现以五路平衡归并为例来建立“败者树”，假设已经用前面的方法得到五个初始归并段为（其中 表示该段的结束）：,第一归并段B0：17，21，,第二归并段B1：05，44，,第三归并段B2：10，12，,第四归并段B3：29，32，,第五归并段B4：15，
9、56，,2023/5/30,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。,图10-3 五路归并建立的初始败者树,2023/5/30,13,2.多路平衡归并的实现,多路平衡归并的
10、实现，是反复调整败者树，并输出Ls0的值，直到树中叶结点都表示为。,现以五路平衡归并举例说明。,【例10-1】假设有五个初始归并段为（其中 表示该段的结束）：,第一归并段B0：17，21，,第二归并段B1：05，44，,第三归并段B2：10，12，,第五归并段B4：15，56，,第四归并段B3：29，32，,试用“败者树”实现五路平衡归并，并给出归并的结果。,2023/5/30,14,解：先建立初始败者树，然后不断的调整败者树，并输出Ls0所对应段的值，直到树中叶结点都表示为。,具体实现过程见图10-4各步骤。,（a）生成的初始败者树,(b)输出05后的败者树,2023/5/30,15,（c）
11、输出05,10后的败者树,(d)输出05,10,12后的败者树,（e）输出05,10,12,15后的败者树,(f)输出05,10,12,15,17后的败者树,2023/5/30,16,（g）输出05,10,12,15,17,21后的败者树,(h)输出05,10,12,15,17,21,29后的败者树,（i）输出05,10,12,15,17,21,29,32后败者树,(j)输出05,10,12,15,17,21,29,32,44后败者树,2023/5/30,17,(k)输出05,10,12,15,17,21,29,32,44,56后败者树,图10-4 利用败者树实现五路平衡归并,2023/5/3
12、0,18,3.多路平衡归并的算法实现,#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/5/30,19,void createlosttree(int lsk)/建立败者树 for(int i=0;
13、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;coutbq;/输入最小值所属段的下一个值 adjust(ls,q);/重新调整败者树 coutbls0;/输出最小值,void main()k_merge(ls,b);,2023/5/30,20,对例10-1的五个初始归并段，可按如下输入执行：,17 05 10 29 15（回车键）44123276756213276732327673276732767,最后输出的结果为：5 10 12 15 17 21 29 32 44 56,
