外存信息的存取外部排序的方法多路平衡归并的实ppt课件

《外存信息的存取外部排序的方法多路平衡归并的实ppt课件》由会员分享，可在线阅读，更多相关《外存信息的存取外部排序的方法多路平衡归并的实ppt课件（74页珍藏版）》请在金锄头文库上搜索。

1、11、外存信息的存取、外存信息的存取2、外部排序的方法、外部排序的方法 3、多路平衡、多路平衡归并的并的实现4、置、置换-选择排序排序 5、最正确、最正确归并并树第第 11 章章 外部排序外部排序21、外存信息的存取、外存信息的存取1、外部排序：、外部排序：待排序的记录数量宏大，无法一次调入内存，只待排序的记录数量宏大，无法一次调入内存，只能驻留在外存上磁带、磁盘、能驻留在外存上磁带、磁盘、CD-ROM上。不上。不能运用内部排序的方法进展排序。否那么将引起频能运用内部排序的方法进展排序。否那么将引起频繁访问外存。繁访问外存。 外部排序主要的时间开销用在信息的内、外存交外部排序主要的时间开销用在

2、信息的内、外存交换上，所以减少换上，所以减少 I/O 时间成为要处理的主要问题。时间成为要处理的主要问题。32 2、常用外存：、常用外存：1)1)磁带：由磁带介质、读、写磁头、驱动器、接纳盘和原始盘磁带：由磁带介质、读、写磁头、驱动器、接纳盘和原始盘组成。廉价、可反复运用、是一种顺序存取设备。查找费时、组成。廉价、可反复运用、是一种顺序存取设备。查找费时、速度慢尤其是查找末端记录时速度慢尤其是查找末端记录时.磁带机走向磁带机走向读读出出头头写写入入头头原原始始盘盘接接纳纳盘盘记录记录 1记录记录 3记录记录 2IRGInter Record Gap记录间隙记录间隙vt可靠读写区可靠读写区41、

3、外存信息的存取、外存信息的存取磁带信息的表示：磁带信息的表示：一种磁化方向、代表一种磁化方向、代表1另一种磁化方向，代表另一种磁化方向，代表0010010011010111151、外存信息的存取、外存信息的存取磁带文件的组织：磁带文件的组织：记录记录 1记录记录 3记录记录 2IRGInter Record Gap记录间隙记录间隙 IRG：0.50.75 inch，带来的来的问题是什么？是什么？ 磁磁带的利用率下降。的利用率下降。例如：例如： 密度密度 1600 byte per inch 的的带。设每个每个记录有有 80 byte ，假，假设 IRG 0.75 inch ; 带的利用率？的利

4、用率？读写头读写头记录所用：所用：(80/1600) 0.005 inch IRG所用：所用： 0.75 inch 利用率利用率 0.005/(1+0.75)= 1/16 必需改良磁必需改良磁带的利用率的利用率 !61、外存信息的存取、外存信息的存取磁带文件的组织的改良：磁带文件的组织的改良：块块 1块块 3块块 2IBGInter Block Gap块间间隙块间间隙 IBG：.5.75 inch，带来的益处是磁带的利用率上升，带来的益处是磁带的利用率上升如上例：如上例：设 每一每一块包含包含20个个记录每一每一块所占所占 20 80/1600 1 inch 利用率利用率 1/1+0.75 =

5、 57%7磁磁带文件的文件的读写写时间：T i/o = ta + ntw ta 延延迟时间：读写写头到达相到达相应的物理的物理块的起的起始位置的始位置的时间。 tw 读/写一个字符的写一个字符的时间； n 字符数。字符数。由于磁由于磁带是是顺序存取序存取设备，在，在读一个一个记录时，必需，必需先先顺序序检索，直到所需信息索，直到所需信息经过读写写头时才干得到。才干得到。因此因此检索速度很慢。索速度很慢。磁磁带主要用于存主要用于存储顺序存取的大量数据。序存取的大量数据。1、外存信息的存取、外存信息的存取81、外存信息的存取、外存信息的存取2磁盘：磁盘： 构造：由磁盘驱动器、读、写磁头、活动臂、盘

6、片磁道、扇构造：由磁盘驱动器、读、写磁头、活动臂、盘片磁道、扇区、旋转主轴构成。速度快、容量大、直接存取设备。区、旋转主轴构成。速度快、容量大、直接存取设备。9 柱面：各柱面：各盘面的直径一面的直径一样的磁道的的磁道的总和。和。 物理位置：柱面号、磁道号、物理位置：柱面号、磁道号、块扇区号扇区号 盘文件的文件的读写写时间：T i/o = tseck + tla + ntwmtseck (0.1秒秒) ：找道：找道时间； tla (25豪秒豪秒) ：等待：等待时间twm (105个字符个字符/秒秒)：传输时间/ 字符，字符，n 字符数。字符数。种种类：固定：固定头磁磁盘、活、活动头磁磁盘固定固定

7、头磁磁盘：每个磁道都有一个磁：每个磁道都有一个磁头速度快速度快活活动头磁磁盘：每个：每个盘面共用一个磁面共用一个磁头，添加了找道，添加了找道的的时间，运用广泛。，运用广泛。2磁盘：磁盘：10外部排序的根本外部排序的根本过程程11.2 外部排序的方法外部排序的方法按可用内存大小按可用内存大小, ,利用内部排序方法，构造假利用内部排序方法，构造假设干干个个记录的有序子序列写入外存，通常称的有序子序列写入外存，通常称这些些记录的有序的有序子序列子序列为 “ “归并段并段; ;由相由相对独立的两个步独立的两个步骤组成：成：经过“归并，逐并，逐渐扩展展( (记录的的) )有序子序列的有序子序列的长度，直

8、至外存中整个度，直至外存中整个记录序列按关序列按关键字有序字有序为止。止。11例如：假例如：假设有一个含有一个含10,00010,000个个记录的磁的磁盘文件，而文件，而当前所用的当前所用的计算机一次只能算机一次只能对1,0001,000个个记录进展内展内部排序，那么首先利用内部排序的方法得到部排序，那么首先利用内部排序的方法得到1010个初个初始始归并段，然后并段，然后进展逐趟展逐趟归并。并。假假设进展展2 2路路归并并( (即两两即两两归并并) )，那么第一趟由，那么第一趟由1010个个归并段得到并段得到5 5个个归并段并段; ;最后一趟最后一趟归并得到整个并得到整个记录的有序序列。的有序

9、序列。第三趟由第三趟由 3 3 个个归并段得到并段得到2 2个个归并段并段; ;第二趟由第二趟由 5 5 个个归并段得到并段得到3 3个个归并段并段; ;11.2 外部排序的方法外部排序的方法12假假设“数据数据块的大小的大小为200200，即每一次，即每一次访问外存可以外存可以读/ /写写200200个个记录。那么那么对于于10,00010,000个个记录，处置一遍需置一遍需访问外存外存100100次次( (读和写各和写各5050次次) )。分析上述外排分析上述外排过程中程中访问外存外存( (对外存外存进展展读/ /写写) )的次数：的次数：1)1)求得求得1010个初始个初始归并段需并段需

10、访问外存外存100100次次; ;2)2)每每进展一趟展一趟归并需并需访问外存外存100100次次; ;3)3)总计访问外存外存 100 + 4 100 + 4 100 = 500 100 = 500次次11.2 外部排序的方法外部排序的方法13 外排总的时间还应包括内部排序所需时间和逐外排总的时间还应包括内部排序所需时间和逐趟归并时进展内部归并的时间趟归并时进展内部归并的时间11.2 外部排序的方法外部排序的方法tIO值值取决于外存，取决于外存，远远远远大于大于tIS和和tmg。 外部排序外部排序的的时间时间取决于取决于读读写外存的次数写外存的次数d。外部排序外部排序总时间=产生初始生初始归

11、并段的并段的时间 m*tIS +外存信息外存信息读写写时间 d*tIO +内部内部归并所需并所需时间 s*utmg14例如例如: :假设对上述例子采用假设对上述例子采用2 2 路归并路归并, ,那么只需进展那么只需进展4 4趟趟归并，归并， 外排所需总的时间：外排所需总的时间： 10*tIS+500*tIO+4*1000*tmg 10*tIS+500*tIO+4*1000*tmg假假设对上述例子采用上述例子采用5 5路路归并并, ,那么只需那么只需进展展2 2趟趟归并，并，总的的访问外存的次数外存的次数为100+2100+2100=300100=300次次11.2 外部排序的方法外部排序的方法

12、普通情况下，假普通情况下，假设待排待排记录序列含序列含 m m 个初始个初始归并段，外排并段，外排时采用采用 k k路路归并，那么并，那么归并趟数并趟数s=s=logkmlogkm ，显然，随着然，随着k k的的增大或增大或m m的减小，的减小，归并的趟数将减少，因此并的趟数将减少，因此对外排而言，通常外排而言，通常采用多路采用多路归并。并。k k 的大小可的大小可选，但需，但需综合思索各种要素。合思索各种要素。1511.3 多路平衡归并的实现多路平衡归并的实现分析分析: m 个初始归并段，外排时采用个初始归并段，外排时采用 k路归并，那路归并，那么归并趟数为么归并趟数为 logkm , K

13、大，趟数减少，读写记录大，趟数减少，读写记录的总数将减少。但的总数将减少。但 K 大，会使内部归并时间大，会使内部归并时间tmg增大增大?。一、多路平衡归并的性质：一、多路平衡归并的性质：16 设从从 k 个元素中挑个元素中挑选一个最小的元素需一个最小的元素需 ( k-1) 次比次比较。 每次比每次比较耗耗费的的时间代价代价为 tmg，在，在进展展 k 路平衡路平衡归并并时,要得到要得到m个初始个初始归并段并段,那么内部那么内部归并并过程中程中进展的比展的比较的的总的次数的次数为: logkm ( k - 1 ) ( n - 1 ) tmg = log2m ( k - 1 ) / log2k

14、( n - 1 ) tmg 改良：采用改良：采用胜者者树或者或者败者者树，从，从 K 个元素中挑个元素中挑选一个最小的元素一个最小的元素仅需需 log2k 次比次比较，这时总的的时间耗耗费将下降将下降为： log2m ( n - 1 ) tmg 11.3 多路平衡归并的实现多路平衡归并的实现1711.3 多路平衡归并的实现多路平衡归并的实现二、胜者树及其运用二、胜者树及其运用195729595765432输输入入缓缓冲冲区区7654321559572995164952787122584912938576671922474859输输出出 缓缓冲冲区区54路平衡归并路平衡归并189711.3 多路

15、平衡归并的实现多路平衡归并的实现729169751649527871225849129385766719224748597654321输输入入缓缓冲冲区区输输出出 缓缓冲冲区区779167299765432157二、胜者树及其运用二、胜者树及其运用4路平衡归并路平衡归并1991211.3 多路平衡归并的实现多路平衡归并的实现1229169951649527871225849129385766719224748597654321输输入入缓缓冲冲区区输输出出 缓缓冲冲区区9129161229976543215794路平衡归并路平衡归并二、胜者树及其运用二、胜者树及其运用2011.3 多路平衡归并的

16、实现多路平衡归并的实现 改良：采用胜者树，从改良：采用胜者树，从K个元素中选取最小元素之后，个元素中选取最小元素之后，从根结点到它的相应的叶子结点途径上的结点都需求进展从根结点到它的相应的叶子结点途径上的结点都需求进展修正，为了加快程序运转的速度产生了败者树。修正，为了加快程序运转的速度产生了败者树。采用采用胜者者树，从，从 K 个元素中挑个元素中挑选一个最小的元素一个最小的元素仅需需 log2m ( n - 1 ) tmg即内部即内部归并并时间与与k无关无关, K 增大，增大，归并趟数并趟数logkm 减少，减少，读写外存次数减少，外排写外存次数减少，外排总时间减少。减少。212111.3

17、多路平衡归并的实现多路平衡归并的实现三、败者树及其运用三、败者树及其运用7295935164952787122584912938576671922474859b0ls1输输入入缓缓冲冲区区输输出出 缓缓冲冲区区97295729976543215留意：挑出冠军留意：挑出冠军需求进展需求进展 k-1 次次比较，此处需求比较，此处需求比较比较 3 次。次。0ls 005ls2ls3b1b2b34路平衡归并路平衡归并222011.3 多路平衡归并的实现多路平衡归并的实现三、败者树及其运用三、败者树及其运用72916935164952787122584912938576671922474859b0ls1

18、输输入入缓缓冲冲区区输输出出 缓缓冲冲区区 9 7 29 57 299765432157留意：挑出冠军留意：挑出冠军需求进展需求进展 k-1 次次比较，此处需求比较，此处需求比较比较 3 次。次。1ls 00 5ls2ls3b1b2b34路平衡归并路平衡归并232011.3 多路平衡归并的实现多路平衡归并的实现三、败者树及其运用三、败者树及其运用122916915164952787122584912938576671922474859b0ls1输输入入缓缓冲冲区区输输出出 缓缓冲冲区区9729572997654321579留意：挑出冠军留意：挑出冠军需求进展需求进展 k-1 次次比较，此处需求

19、比较，此处需求比较比较 3 次。次。3ls 005ls2ls3b1b2b34路平衡归并路平衡归并24typedef int LoserTreek;typedef struct KeyType key; Exnode, Externalk+1;Void K_Merge ( LoserTree &ls，External &b) for ( i = 0; i 0 ) if (bs.key blst.key) s lst; t = t / 2; ls0 = s; / Adjust四、调整败者树的算法描画如下四、调整败者树的算法描画如下:26void CreateLoserTree ( LoserTre

20、e &ls ) / 知知b0到到bk-1为为完全二叉完全二叉树树ls的叶子的叶子结结点存有点存有k个关个关键键字字, 沿从叶沿从叶结结点到根的点到根的k条途径将条途径将ls调调整整为败为败者者树树. bk.key = MINKEY; /设设MINKEY为为关关键键字最小字最小值值. for ( i=0; i = 0; - -i ) Adjust(ls,i); /依次从依次从bk-1,bk-2,b0出出发调发调整整败败者者. / CreateLoserTree四、建立败者树的算法描画如下四、建立败者树的算法描画如下:2711.4 置换置换-选择排序选择排序一、问题的提出一、问题的提出 m个初始归

21、并段做个初始归并段做k路平衡归并排序时归并的趟数路平衡归并排序时归并的趟数为为logkm.为了减少归并趟数，也可以减小为了减少归并趟数，也可以减小m的值。如的值。如何减小初始归并段的个数也就是添加归并段的长度何减小初始归并段的个数也就是添加归并段的长度?处理：在内存理：在内存长度一定度一定时，假，假设包容包容M条条记录，按照，按照通常的通常的 排序方法，初始排序方法，初始归并段的并段的长度可以是度可以是M一种更好的方法是运用置一种更好的方法是运用置换选择(replace selection)算法，平均情况下可以算法，平均情况下可以产生可以生成两倍内存生可以生成两倍内存长度的度的初始初始归并段。

22、并段。284、置换、置换-选择排序选择排序2.置换选择排序置换选择排序置换选择排序是堆排序的变体。置换选择排序是堆排序的变体。输入文件输入文件FI内存任务区内存任务区WA输出文件输出文件Fo内存任务区可包容内存任务区可包容w个记录个记录输出缓冲输出缓冲输入缓冲输入缓冲29(1) 从从FI输入输入W个记录到个记录到WA；(2) 从从WA中选择关键字最小的记录，记为中选择关键字最小的记录，记为MINIMAX(3) 将将MINIMAX输出到输出到FO中；中；(4)假设假设FI不空，从不空，从FI输入下一个记录到输入下一个记录到WA；(5)从从WA中一切关键字比中一切关键字比MINIMAX的关键字大的

23、记录的关键字大的记录中选出最小关键字记录，作为新的中选出最小关键字记录，作为新的MINIMAX记录。记录。(6)反复反复3-5直至直至WA中选不出新的中选不出新的MINIMAX。到此得到一个初始归并段。到此得到一个初始归并段7反复反复2-6，直至，直至WA为空。为空。置换选择排序的操作过程：置换选择排序的操作过程：30实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 6 个记录，利用个记录，利用置换置

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 FI51 49 39 46 38 29WAFO31实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 6 个记录，利用个记录，利用置换置换-选择分类法产生初始合并段。选择分类法产生初始合并段。51 49 39 4

25、6 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI51 49 39 46 38 14WA29FO32实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 6 个记录，利用个记录，利用置换置换-选择分类法产生初始合并段。选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27

26、4 13 89 24 46 58 33 76 FI51 49 46 39 14 61WA29 38FO33实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 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 FI51 49 46

27、 14 61 15WA29 38 39FO34实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 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 FI51 49 14 61 15 30WA29 38 39 46FO35实例：输

28、入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 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 FI51 14 61 15 30 1WA29 38 39 46 49FO36实例：输入文件实例：输入文件FI中记录关键字为：中记录关键

29、字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 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 FI14 61 15 30 1 48WA29 38 39 46 49 51 #FO37实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29

30、、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 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 FI14 15 30 1 48 52WA29 38 39 46 49 51 61FO38实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、5

31、2、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 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 FI14 15 30 1 48 52WA29 38 39 46 49 51 61#FO39实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、

32、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 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 FI14 15 30 48 52 3WA29 38 39 46 49 51 61 # 1 FO40实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76

33、，假定运用的内存可包容，假定运用的内存可包容 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 FI14 15 30 48 52 63WA29 38 39 46 49 51 61 # 1 3FO41实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，

34、假定运用的内存可包容 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 FI15 30 48 52 63 27WA29 38 39 46 49 51 61 # 1 3 14FO42实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包

35、容 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 FI15 30 48 52 63 27WA29 38 39 46 49 51 61 # 1 3 14FO43实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 6 个记录，利

36、用个记录，利用置换置换-选择分类法产生初始合并段。选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI30 48 52 63 27 4WA29 38 39 46 49 51 61 # 1 3 14 15 FO44实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 6 个记录，利用个记录，利

37、用置换置换-选择分类法产生初始合并段。选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI30 48 52 63 4 13WA29 38 39 46 49 51 61 # 1 3 14 15 27FO45实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 6 个记录，利用个记录，利用置换置

38、换-选择分类法产生初始合并段。选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI48 52 63 4 13 89WA29 38 39 46 49 51 61 # 1 3 14 15 27 30FO46实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 6 个记录，利用个记录，利用置换置换

39、-选择分类法产生初始合并段。选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI52 63 4 13 89 24WA29 38 39 46 49 51 61 # 1 3 14 15 27 30 48FO47实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 6 个记录，利用个记录，利用置换

40、置换-选择分类法产生初始合并段。选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI63 4 13 89 24 46WA29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52FO48实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 6 个记录，利用个记录

41、，利用置换置换-选择分类法产生初始合并段。选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI4 13 89 24 46 58WA29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63FO49实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 6 个

42、记录，利用个记录，利用置换置换-选择分类法产生初始合并段。选择分类法产生初始合并段。51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76 FI4 13 24 46 58 33WA29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89#FO50实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定

43、运用的内存可包容 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 FI13 24 46 58 33 76WA29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 FO51实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、

44、76，假定运用的内存可包容，假定运用的内存可包容 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 FI24 46 58 33 76WA29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13FO52实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、

45、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 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 FI46 58 33 76WA29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24FO53实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、5

46、2、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 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 FI46 58 76WA29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24 33FO54实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、39、46、38、29、14、

47、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 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 FI58 76WA29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24 33 46FO55实例：输入文件实例：输入文件FI中记录关键字为：中记录关键字为：51、49、

48、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 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 FI76WA29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24 33 46 58FO56实例：输入文件实例：输入文件FI中记录关键字为

49、：中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定运用的内存可包容，假定运用的内存可包容 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 FIWA29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24 33 46 58 76 #FO574、置换、

50、置换-选择排序选择排序 3、长度分析：度分析：设内存可以存放内存可以存放 m 个个记录，那么首先从文件，那么首先从文件读入入 m 记录到内存。到内存。这 m 个个记录一定可以一定可以归入本初始合并段内。入本初始合并段内。这样，必需从文件中必需从文件中读入入 m 个个记录。这 m 个个记录中平均有一半可中平均有一半可以以归入本合并段，一半入本合并段，一半归入下一合并段。入下一合并段。因此，合并段的平均因此，合并段的平均长度度为：m + m/2 + m/4 + = 2m 所以，在平均情况下，合并段的平均所以，在平均情况下，合并段的平均长度度为 2m 。该结论由：由：EFMoore 在在 1961

51、年从置年从置换选择排序同排序同扫雪雪机的机的类比中得到的。比中得到的。581)存储构造定义存储构造定义 可以用败者树的方法可以用败者树的方法 加以实现。加以实现。typedef structRcdType rec; /记录 KeyType key; /关键字 int rnum; /所属归并段的段号RcdNode,WorkAreaw;4、实现：、实现：592)模块构造图模块构造图Replace_selectionGet_run置换置换-选择算法选择算法得到一个初始得到一个初始归并段归并段Construct_LoserSelect_MiniMax选择每个段中选择每个段中最小值最小值60void R

52、eplace_Selection(LoserTree &ls, WorkArea &wa, FILE *fi,FILE *fo)Construct_Loser(ls, wa); rc=rmax=1; /rc为当前生成段号，为当前生成段号，rmax为最大段的段号为最大段的段号 while(rc=rmax) get_run(ls, wa); fwrite(RUNEND_SYMBLE, sizeof(struct RcdType), 1, fo); rc=wals0 .rnum; /Replace_Selection3)模块实现模块实现61void get_run(LoserTree &ls, Wo

53、rkArea &wa)while(wals0 .rnum=rc) q=ls0; minimax=waq.key; fwrite(&waq.rec, sizeof(struct RcdType), 1, fo); If(feof( f i ) waq.rnum=rmax+1; waq.key=MAXKEY; else fread(&waq.rec,sizeof(struct RcdType),1, fi); waq.key=waq.rec.key; If(waq.key0; t=t/2, p=ls t ) if(wap.rnumwaq.rnum | wap.rnum=waq.rnum & wap

54、.key waq.key) qlst; ls0=q;63void Construct_Loser(LoserTree &ls, WorkArea &wa)for(i=0; i=0; - -i) fread(&wai.rec, sizeof(struct RcdType), 1, fi); wai.key=wai.rec.key; wai.rnum=1; Select_MiniMax(ls, wa, i); /end for/Construct_Loser6432144、置换、置换-选择排序选择排序5、败者树实现置换、败者树实现置换-选择排序选择排序522901051、49、39、46、38、2

55、9、14、61、154613914915112913815436532044、置换、置换-选择排序选择排序5、败者树实现置换、败者树实现置换-选择排序选择排序52293801151、49、39、46、38、29、14、61、154613914915111423815436612044、置换、置换-选择排序选择排序5、败者树实现置换、败者树实现置换-选择排序选择排序5229383901351、49、39、46、38、29、14、61、154613914915111426115436712044、置换、置换-选择排序选择排序5、败者树实现置换、败者树实现置换-选择排序选择排序53293839460

56、1251、49、39、46、38、29、14、61、15461152491511142611543留意：在全部的留意：在全部的 段号标志变成段号标志变成 2 之后，合并段之后，合并段 1 的记录已全部生的记录已全部生成。成。？K 值越大越好吗！685、最正确归并树、最正确归并树1、最正确归并树、最正确归并树 原因：由于初始归并段通常不等长原因：由于初始归并段通常不等长,进展归并时进展归并时,长度不同的初始归并段归并的顺序不同长度不同的初始归并段归并的顺序不同,读写外存读写外存的总次数也不同。的总次数也不同。 目的：减少读写外存的次数。目的：减少读写外存的次数。69e.g:假定由置换选择分类法生

57、成了假定由置换选择分类法生成了 9 个初始归并段，记录个初始归并段，记录数分别为数分别为 9、30、12、18、3、17、2、6、24 。假设进展。假设进展 3-路归并，请讨论在各种情况下的对外存的读写次数。路归并，请讨论在各种情况下的对外存的读写次数。301293171862425138 32121从外存读从外存读 121 个记录个记录写入外存写入外存 121 个记录个记录从外存读从外存读 121 个记录个记录写入外存写入外存 121 个记录个记录 A.总共读写外存总共读写外存 484 个记录个记录705、最正确归并树、最正确归并树1、最正确归并树、最正确归并树 62392417183011

58、32 59121从外存读从外存读 11 个记录个记录写入外存写入外存 11 个记录个记录从外存读从外存读 91个记录个记录写入外存写入外存 121 个记录个记录 B.写入外存写入外存 91 个记录个记录从外存读从外存读 121 个记录个记录12总共读写外存总共读写外存 446 个记录个记录715、最正确归并树、最正确归并树326924171812520 4791 C.总共读写外存总共读写外存 326 个记录个记录 按照按照 HUFFMAN 树的思想，记录少的段最先合并。不够时添树的思想，记录少的段最先合并。不够时添加虚段。如下例所示。加虚段。如下例所示。从外存读从外存读 5个记录个记录写入外存

59、写入外存 11 个记录个记录从外存读从外存读 91个记录个记录写入外存写入外存 67 个记录个记录写入外存写入外存 91 个记录个记录72 虚段的补法虚段的补法: 在在 K 路平衡路平衡归并并时，它的，它的归并并树的模型是一棵度的模型是一棵度为 K 的的树。在在这棵棵树上的上的结点要么是叶子，要么是具有点要么是叶子，要么是具有 K 个子女的内部个子女的内部结点。点。设具有具有 K 个子女的内部个子女的内部结点共有点共有 nk 个。初始个。初始归并段的个并段的个数数为 m 个。个。设 n = nk + m ，故：从，故：从结点出点出发的枝条，合的枝条，合计有有K nk 个。假个。假设从从进入入结

60、点的角度点的角度进展思索，那么共有：展思索，那么共有： nk + m 1 留意：没有枝条留意：没有枝条进入根入根结点。点。 所以，所以， K nk nk + m 1 于是：于是： nk ( m 1 ) / ( K - 1) 这就意味着，假就意味着，假设 ( m 1 ) MOD ( K - 1) 0，无需添加，无需添加虚段。否那么，要添加虚段，其数目虚段。否那么，要添加虚段，其数目为： K1 ( m 1 ) MOD ( K - 1) 73限制：限制： 由于磁带寻觅具有最少记录的初始归并段，必需反复由于磁带寻觅具有最少记录的初始归并段，必需反复倒带。所以，适用性不强。倒带。所以，适用性不强。在磁盘的情况下，需求有段包含的记录数信息、段的在磁盘的情况下，需求有段包含的记录数信息、段的位置信息等。文件如集中放置在几个相邻的柱面上的位置信息等。文件如集中放置在几个相邻的柱面上的情况比较适宜。情况比较适宜。74本章小结本章小结1.了解外存信息的存取方法，磁带和磁盘的特点了解外存信息的存取方法，磁带和磁盘的特点2.掌握外部排序的方法掌握外部排序的方法 3.了解最正确归并树的概念了解最正确归并树的概念多路平衡归并的实现多路平衡归并的实现置换置换-选择排序选择排序