清华大学出版社 《数据结构与算法》赵玉兰 等编著第8章.ppt

1、1,数据结构与算法DATA STRUCTURE AND ARITHMETIC,计算机专业本科主干基础课,2,第8章 外部排序 8.1 外部排序的方法 8.1.1 外部排序的方法 8.1.2 多路平衡归并 8.1.3 置换-选择排序 8.2 最佳归并树,3,8.1.1 外部排序的基本过程 待排序的记录数量巨大，无法一次将待排序的记录全部调入内存，一部分数据只能驻留在外存上（磁带、磁盘、CD-ROM）上。不能使用内部排序的方法进行排序。否则将引起频繁访问外存。,8.1 外部排序的方法,4,当记录以文件的形式存于磁盘上时，通常是按物理块来存放的，物理块也叫做页块。每个页块可存放若干个记录。操作系统是

2、按页块对磁盘信息进行读写。 磁盘通常是指由若干片磁盘组成的磁盘组, 各个盘片安装在同一主轴上高速旋转。各个盘面上半径相同的磁道构成了柱面。各盘面设置一个读写磁头，它们装在同一活动臂上，活动臂可以直接从一个柱面移到另一个柱面上。,5,6,为了访问某一页块, 先寻找柱面: 活动臂使读写磁头移到指定柱面上: 寻查(seek)。再根据盘面号选择相应读写磁头, 等待指定页块转到读写磁头下: 等待(latency)。传输一个字符的时间为 trw，则在磁盘组上读写一个页块的时间：,tiotseektlatencytrw,外排序主要的时间开销用在信息的内、外存交换上，内存排序所需时间可以忽略不计，因此在外排序

3、的过程中主要考虑访问外存的次数。,7,当记录以文件的形式存于磁盘上时，其排序过程主要分为两个阶段：,(2)、把 (1) 生成的初始归并段加以归并, 逐步扩大归并段和减少归并段个数, 直到最后归并成一个归并段(有序文件)为止。,基于磁盘进行的排序多使用归并排序方法。,(1)、建立用于外排序的内存缓冲区。根据它们的大小将输入文件划分为若干段, 用某种内排序方法对各段进行排序。经过排序的段叫做初始归并段。当它们生成后就被写到外存中去。,8,例：设有一个包含4500个记录的输入文件。现用一台其内存至多可容纳750个记录的计算机对该文件进行排序。输入文件放在磁盘上，磁盘每个页块可容纳250个记录, 这样

4、全部记录可存储在 4500 / 25018 个页块中。输出文件也放在磁盘上, 用以存放归并结果。,9,由于内存中可用于排序的存储区域能容纳750 个记录, 因此内存中恰好能存3个页块的记录. 在外排序一开始, 把18块记录, 每3块一组, 读入内存。利用某种内排序方法进行内排序, 形成初始归并段, 再写回外存。总共可得到6个初始归并段。然后一趟一趟进行归并排序。,10,两路归并排序的归并树,R1 750 R2 750 R3 750 R4 750 R5 750 R6 750,初始 归并段,R12 1500 R34 1500 R56 1500,R1234 3000,R123456 4500,第一趟

5、 归并结果,第二趟 归并结果,第三趟 归并结果,11,若把内存区域等份地分为 3 个缓冲区。其中的两个为输入缓冲区, 一个为输出缓冲区, 可以在内存中利用简单 2 路归并函数 merge( ) 实现 2 路归并。 首先, 从参加归并排序的两个输入归并段 R1 和 R2 中分别读入一块, 放在输入缓冲区1 和输入缓冲区2 中。然后在内存中进行 2 路归并，归并结果顺序存放到输出缓冲区中。,输入缓冲区 2,输入缓冲区 1,输出缓冲区,12,一般地，若总元素个数为n，磁盘上每个页块可容纳b个元素，内存缓冲区可容纳i个页块，则每个初始归并段长度为len = i * b，可生成m = n / len 个

6、等长的初始归并段。在做2路归并排序时，第一趟从m个初始归并段得到 m/2 个归并段，以后各趟将从p (p 1) 个归并段得到 p / 2 个归并段，总归并趟数等于归并树的高度 logm。,13,tES = m*tis + d*tio + s*u*tmg,其中：m是初始归并段的个数；tIS 是对一个初始归并段进行内排序的时间的均值； d 是读/写外存页块的总次数；tIO 是对每一个页块进行读/写的时间；S是归并趟数；tmg是对一个记录进行一次内部归并所需时间。，u*tmg是对u个记录进行内部归并所需的时间。,根据2路归并树, 估计2路归并排序时间tES的上界为：,14,若总记录个数为 n，磁盘上

7、每个页块可容纳 b 个记录，内存缓冲区可容纳 i 个页块，则每个初始归并段长度 为 len = i * b，可生成 m = n/len 个初始归并段。 在做 2 路归并排序时, 第一趟从 m 个初始归并段得到 m/2 个归并段，以后各趟将从 l (l 1) 个归并段得到 l /2 个归并段。总归并趟数为 log2m,15,对 4500 个记录进行排序的例子, 各种操作的计算时间如下： 产生初始归并段： 读 18 个输入块, 内部排序6次, 写18个输出块6 tIS36 tIO,16,归并初始归并段 R1R6： 第一趟：36 tIO4500 tmg 第二趟：归并两个具有 1500 个记录的归并段

8、 R12和 R34 时间为：24 tIO3000 tmg 第三趟：将 R1234 和 R56 归并成一个归并段 36 tIO4500 tmg 合计 tES6 tIS132 tIO12000 tmg,17,归并趟数 S logkm 增大归并路数k, 可减少归并趟数S, 从而减少总读写磁盘次数d。,18,8.1.2 多路平衡归并 (k-way Balanced merging),从8.1式可以看出增大归并路数k可以减少归并趟数S。图8.2给出对有6个初始归并段的文件做3路平衡归并时的归并树，可以看出只需要归并两趟。,19,从上例看到好像k越大越好，但是从下面的讨论中又看到单纯增加k将导致增加内部归

9、并的时间。例如对n个元素的文件，做内部k路归并时，在k个元素中选择最小者，需要顺序比较k-1次。每趟归并产生含有u个元素的归并段时，需要做(u-1)*(k-1)次比较，S 趟归并总共需要的比较次数为： S*(u-1)*(k-1) = logkm * (u-1) * (k-1)= logm * (u-1) * (k-1) / logk,20,在初始归并段个数m与元素个数u一定时， logm*(u-1)是一个常数，而(k-1) / logk在k增大时趋于无穷大。因此，增大归并路数k，会使得内部归并的时间增大。当k增加到一定程度时，可能就抵消了由于减少读写磁盘次数而赢得的时间。 当然我们还可以使用下

10、面将要讲到的“败者树”的方法从k个归并段中选最小者，当k较大时（k 6），用败者树选出排序码最小的元素只需比较logk次（小于k-1次）。此时，S趟归并总共需要的比较次数为： S*(u-1)*logk = logkm* (u-1) * logk = logm * (u-1) * logk / logk = logm * (u-1),21,从得到的式子可以看出总的排序码比较次数与k无关，也就是说总的归并时间不会随k的增大而增大。因此，只要内存空间允许，增大归并路数k，将有效地减少归并树深度，从而减少读写磁盘次数d，提高外部排序的速度。 失败者树:所谓败者树是一棵正则的完全二叉树，其中每个叶结点存

11、放当前参加比较的元素；每个非叶结点存放其子女结点中排序码大的结点（即败者），让二者中的小排序码去参加更上一层的比较，当到达根结点时，根中仍存放其左、右子中较大排序码，得到的小排序码就是目前序列的最小排序码。,22,设有5个初始归并段，m0=6，16，、m1=8，12，、m2=30，38，、m3=9，22，、m4=20，40，90，其中为段结束标志MaxNum，开始进行5路归并，每个归并段有一个排序码参加归并，每个非叶结点中的段号为其左、右子女中的排序码大的元素所在的段号（败者），数组Ls存放比较过程的结果，如图8.3中，Ls2=0（即段m0中的排序码为当前的败者），每个非叶结点向上分支上的段号

12、表示比较过程的胜者，它将参加更高一层结点的比较。,23,Ls0存放最后的胜者。以后每选出一个当前排序码最小的元素，将它送入输出缓冲区，然后从它所在的归并段输入缓冲区中取出下一个参加归并的元素，替换已经取走的最小元素，如图8.4最左侧叶结点（排序码为16），再从叶结点到根结点，沿某一特定路径进行调整，将下一个排序码最小元素的归并段号调整到Ls0中。最后，段结束标志MaxNum（如图中的）升入Ls0，排序完成，输出一个段结束标志。,24,25,m1,m0,m2,30,m3,9,20,16,8,16 ,8 12 ,30 38 ,9 22 ,20 40 90 ,m0,m1,m2,m3,m4,m3,Ls

13、0,Ls1,Ls2,Ls3,Ls4,m4,m4,m1,败者树,m3,胜者,图8.3 选出当前最小的关键字8,26,void k_waymerge () r = new Elementk;/创建元素数组 *key = new intk+1; /创建外结点数组 *Ls = new intk; /创建败者树数组 for ( i = 0; i k; i+ ) /传送参选排序码 InputRecord ( ri ); keyi = ri.key; ,27,for ( i = 0; i k; i+) Lsi = k; keyk = -MaxNum; /初始化 for ( i = k-1; i; i- )

14、/调整形成败者树 adjust ( key, Ls, k, i ); while ( keyLs0 != MaxNum ) /选归并段 q = Ls0; /最小元素的段号,28,OutputRecord ( rq ); /输出 InputRecord ( rq ); /从该段补入元素 keyq = rq.key; adjust ( key, Ls, k, q ); /调整 Output end of run marker; /输出段结束标志 / k_waymerge,29,自某叶结点keyq到败者树根结点的调整算法,void adjust () /q指示败者树的某叶结点keyq, 从该结点起到

15、根结点进行比较, 将最小key元素所在归并段的段号记入Ls0。k是叶结点key0.k-1的个数。 for ( t = (k+q) / 2; t 0; t /= 2 ) / t是q的双亲 if ( keyLst keyq) /败者记入Lst, 胜者记入q temp = q; q = Lst; Lst = temp; Ls0 = q; / adjust,30,输入文件FI,内存工作区WA,输出文件Fo,内存工作区可容纳 w个记录,8.1.3 置换选择排序,31,从输入文件FI中把 k 个元素读入内存工作区WA中，假设内存中存放元素的数组r可容纳的元素个数为 k 。 将无穷小存入Threshold作

16、为阈值。 从所有排序码比Threshold大的元素中选择一个排序码最小的元素rq作为阈值，其排序码存入Threshold。 将rq元素写到输出文件FO中。 若FI未读完，则从FI读入下一个元素。 重复(3)-(5)，直到在WA中选不出排序码比Threshold大的元素为止。此时，在输出文件FO中得到一个初始归并段，在它最后加一个归并段结束标志。 重复(2)-(6)，重新开始选择和置换，产生新的初始归并段，直到输入文件FI中所有元素选完为止。,置换选择排序的操作过程：,32,若按每个初始归并段的长度与内存工作区的长度一致的 方法，采用前面的内部排序的方式，在长度为3的工作 区中进行排序，则9个元

17、素的序列27, 31, 15, 54, 20, 22,66, 42, 39，可分成3个初始归并段： Run0 15, 27, 31 Run1 20, 22, 54 Run2 39, 42, 66 但采用上述置换-选择的方法，如图8.5可生成2个长度不 等的初始归并段： Run0 15, 27, 31, 54, 66 Run1 20, 22, 39, 42 ,33,34,35,在WA中选择的过程可利用“败者树”来实现。 在利用败者树选取最小元素时，把败者树的叶结点和非叶结点分开定义。假设败者树有k个叶结点，用key存放，key0到keyk-1存放各归并段当前参加归并的元素的排序码，keyk是辅助

18、工作单元，在初始建立败者树时使用，存放一个最小的在各归并段中不可能出现的排序码：-MaxNum。,36,首先比较两个元素所在归并段的段号，段号小者为胜者，段号大者为败者；在归并段的段号相同时，排序码小者为胜者，排序码大者为败者。比较后把败者元素在元素数组 r 中的序号记入它的双亲结点中，把胜者元素在元素数组 r 中的序号记入工作单元 s 中，向更上一层进行比较，最后的胜者记入 Ls0中。,37,38,39,40,41,2,2,2,2,(10)阈值为22，选出39,42,2,2,2,2,(11)阈值为39，选出42 (12) 阈值为42，结束,43,利用败者树生成初始归并段的算法：,void g

19、enerateRuns () r = new Elementk; int *key = new intk; /参选元素排序码数组 int *rn = new intk; /参选元素段号数组 int *Ls = new intk; /败者树 for (i = 0; i k; i+ ) Lsi = 0; rni = 0; ,44,利用败者树生成初始归并段的算法：,for ( i = k-1; i 0; i- ) /输入首批元素 if ( end of input ) rni = 2; /中途结束 else InputRecord ( ri ); /从缓冲区输入 keyi = ri.key; rni

20、 = 1; SelectMin ( key, rn, Ls, k, i, rq ); /调整 ,45,利用败者树生成初始归并段的算法,q = Ls0; / q是最小元素在 r 中的序号 int rq = 1; / rq的归并段段号 int rc = 1; /当前归并段段号 int rmax = 1; /下次将要产生的归并段段号 int Threshold = MaxNum; /阈值 while (1) /生成一个初始归并段 if ( rq != rc ) /当前最小元素归并段大 Output end of run marker; /加段结束符 if ( rq rmax ) return; /处

21、理结束 else rc = rq; /否则置当前段号等于rq ,46,利用败者树生成初始归并段的算法,OutputRecord ( rq ); / rc=rq，输出 Threshold = Keyq; /置新的阈值 if ( end of input ) rnq = rmax + 1; /虚设元素 else /输入文件未读完 InputRecord ( rq ); /读入到刚才位置 keyi = ri.key; if ( keyq Threshold ) /小于阈值 rnq = rmax = rq + 1; /应为下一段元素,47,利用败者树生成初始归并段的算法,else rnq = rc;

22、/否则在当前段 rq = rnq; SelectMin ( key, rn, Ls, k, q, rq ); q = Ls0; /新的最小元素 / end of while delete r ; /generateRuns,48,在败者树中选择最小元素的算法：,void SelectMin () /q指示败者树的某叶结点keyq, 从该结点向上到根结点Ls0进行比较, 选择出/Threshold元素。k是叶结点key0.k-1的个数。 for ( int t = (k+q)/2; t 0; t /= 2 ) if ( rnLst rq | rnLst = rq q = Lst; Lst = t

23、emp; /败者记入Lst, 胜者记入q rq = rnq; Ls0 = q; /最后的胜者 / SelectMin,50,8.2 最佳归并树,归并树是描述归并过程的 m 叉树。因为每一次做 m 路归并都需要有m个归并段参加，因此，归并树是只有度为0和度为 m 的结点，称为正则 m 叉树。例如：设有11个长度不等的初始归并段，其长度（元素个数）分别为 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22,51,对它们进行 3 路归并时的归并树如图8.7所示。在归并树中，各叶结点代表参加归并的各初始归并段，叶结点上的权值即为该初始归并段中的元素个数，根结点代表最终生成的归并段，叶结点到根结点的路径长度表示在归并过程中的读元素次数，各非叶结点代表归并出来的新归并段，归并树的带权路径长度WPL即为归并过程中读元素的总次数。对于图8.7中的3路归并树而言，其WPL为：,52,WPL=(2+4+6+8+10+12+14+16+18)*3+(20+22)*1=312。,因而，在归并过程中读写元素的总次数为