外部排序课件

《外部排序课件》由会员分享，可在线阅读，更多相关《外部排序课件（61页珍藏版）》请在金锄头文库上搜索。

1、1 1 1 1、外存信息的存取、外存信息的存取、外存信息的存取、外存信息的存取2 2 2 2、外部排序的方法、外部排序的方法、外部排序的方法、外部排序的方法3 3 3 3、多路平衡归并的实现、多路平衡归并的实现、多路平衡归并的实现、多路平衡归并的实现4 4 4 4、置换、置换、置换、置换- - - -选择排序选择排序选择排序选择排序5 5 5 5、最佳归并树、最佳归并树、最佳归并树、最佳归并树第第1111章章 外部排序外部排序 1、外存信息的存取、外存信息的存取1、外部排序：、外部排序：内部排序：信息一次可全部调入内存，信息在内存中的处理时间是主要的时间耗费。内部排序：信息一次可全部调入内存，

2、信息在内存中的处理时间是主要的时间耗费。外部排序：信息量巨大，无法一次调入内存。只能驻留在带、盘、外部排序：信息量巨大，无法一次调入内存。只能驻留在带、盘、CD-ROM 上。特点上。特点 为内存运行时间短，内、外存进行交换需要时间长。减少为内存运行时间短，内、外存进行交换需要时间长。减少 I/O 时间成为主时间成为主 要矛盾。要矛盾。 记录（记录（Record）：）：数据项的集合存于内存，称之为结点。如果存之于外存，则叫做记数据项的集合存于内存，称之为结点。如果存之于外存，则叫做记 录。原因起源于是在历史上研究管理应用和计算机科学的两部分人录。原因起源于是在历史上研究管理应用和计算机科学的两部

3、分人员的习惯。员的习惯。 域（场）：记录中的每个数据项，称之为域（域（场）：记录中的每个数据项，称之为域（Field） 。 文件：记录的集合。文件：记录的集合。 关键字：唯一标识记录的域，称之为关键字。关键字：唯一标识记录的域，称之为关键字。 有序文件：文件根据关键字的大小。排成递增或递减的序列。有序文件：文件根据关键字的大小。排成递增或递减的序列。2、基本术语：、基本术语：3、常用外存：、常用外存： 磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。便宜、可反复使用、是一种顺序存取设备。

4、 查找费时、速度幔。查找费时、速度幔。1、外存信息的存取、外存信息的存取3、常用外存：、常用外存： 磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。便宜、可反复使用、是一种顺序存取设备。 查找费时、速度慢。查找费时、速度慢。 带信息的表示：带信息的表示：一种磁化方向、代表一种磁化方向、代表1另一种磁化方向，代表另一种磁化方向，代表01、外存信息的存取、外存信息的存取3、常用外存：、常用外存： 磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。磁带：由磁带介质、读、写磁头、驱动器、

5、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。便宜、可反复使用、是一种顺序存取设备。 查找费时、速度慢（尤其是查找末端记录时）。查找费时、速度慢（尤其是查找末端记录时）。.磁带机走向磁带机走向读读出出头头写写入入头头原原始始盘盘接接收收盘盘 带文件的组织：带文件的组织：记录记录 1记录记录 3记录记录 2IRG（Inter Record Gap）记录间隙）记录间隙1、外存信息的存取、外存信息的存取3、常用外存：、常用外存： 带文件的组织：带文件的组织：记录记录 1记录记录 3记录记录 2IRG（Inter Record Gap）记录间隙）记录间隙vt可靠读写区可靠读写区 IRG：

6、.5.75 inch，带来的问题是什么？带来的问题是什么？ 带的利用率下降，如：带的利用率下降，如： 密度密度 800 byte per inch 的带。设每个记录有的带。设每个记录有 80 byte ，共，共 1000 个记录。如果，个记录。如果， IRG .6 inch ; 带的利用率？带的利用率？ 1000 (80/800) 100 inch ( file) 1000 0.6 600 inch ( total IRG) 利用率利用率 1/7= 14 % 必须改进带的利用率必须改进带的利用率 ! 带文件的读写时间：带文件的读写时间：T i/o = ta + ntw ta 延迟时间：读写头到

7、达相应的记录起始位置的时间。延迟时间：读写头到达相应的记录起始位置的时间。 tw 读读/写一个字符的时间；写一个字符的时间； n 字符字符数。数。读写头读写头1、外存信息的存取、外存信息的存取3、常用外存：、常用外存： 带文件的组织的改进：带文件的组织的改进：块块 1块块 3块块 2IBG（Inter Block Gap）块间间隙块间间隙 IBG：.5.75 inch，带来的好处是什么？带来的好处是什么？ 每一块是一个物理记录，包含若干个逻辑记录。每一块是一个物理记录，包含若干个逻辑记录。 B.F（块因子）（块因子） 一个物理记录包含逻辑记录的个数一个物理记录包含逻辑记录的个数 带的利用率上升

8、，如上例：带的利用率上升，如上例： 设设 B.F = 100 1000 /100 0.6 6 inch ( total IBG ) 1000 80/800 100 inch ( file) 利用率利用率 100/106 = 94.3 %1、外存信息的存取、外存信息的存取3、常用外存：、常用外存： 磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。 速度快、容量大、直接存取设备。速度快、容量大、直接存取设备。 种类：固定头磁盘、活动头磁盘种类：固定头磁盘、活动头磁盘 固定头磁盘：每个磁道都有一个磁头（速

9、度快）固定头磁盘：每个磁道都有一个磁头（速度快） 活动头磁盘：每个盘面共用一个磁头，活动头磁盘：每个盘面共用一个磁头， 增加了找道的时间，应用广泛。增加了找道的时间，应用广泛。 柱面：各盘面的直径相同的磁道的总和。柱面：各盘面的直径相同的磁道的总和。 物理位置：盘组号、若干个磁盘构成一组，系统可能有许物理位置：盘组号、若干个磁盘构成一组，系统可能有许 多组。多组。 柱面号、柱面号、 磁道号、磁道号、 块（扇区号）块（扇区号） 盘文件的读写时间：盘文件的读写时间：T i/o = tseck + tla + ntwm tseck ：找道时间找道时间tla ：等待时间等待时间twm ：传输时间传输时

10、间/ 字符，字符，n 字符数。字符数。2、外部排序的方法、外部排序的方法1、步骤：、步骤： 生成合并段（生成合并段（run）：）：读入文件的部分记录到内存读入文件的部分记录到内存 在内存中进行内部排序在内存中进行内部排序 将排好序的这些记录写入外存，形成合并段将排好序的这些记录写入外存，形成合并段 再读入该文件再读入该文件 的下面的记录，往复进行，直至文件中的记录全部形成合并段的下面的记录，往复进行，直至文件中的记录全部形成合并段 为止。为止。 外部合并：将上一阶段生成的合并段调入内存，进行合并，直至最后形成一个有序的文外部合并：将上一阶段生成的合并段调入内存，进行合并，直至最后形成一个有序的

11、文 件。件。 平衡合并分类法：被合并的初始合并段均匀分布在平衡合并分类法：被合并的初始合并段均匀分布在 K 条磁带上，即分布在条磁带上，即分布在 T1、T2、 Tk 上。对这上。对这 K 条带进行合并，将生成的中间归并段分布在条带进行合并，将生成的中间归并段分布在 TK+1、 TK+2 、 T2K 上。然后，循环往复，直至最后形成一个上。然后，循环往复，直至最后形成一个 单一的合并段为止。单一的合并段为止。e.g: 平衡平衡 2 路归并，路归并， K 2。 2K = 4, 需需 4条磁带。六个初始合并段均匀分布在条磁带。六个初始合并段均匀分布在 T1、T2 上上。每个合并段有每个合并段有 10

12、00 个记录。个记录。T3、T4 初始为空。合并过程如下：初始为空。合并过程如下：初始分布：初始分布：R（1 1000）R（20012000）R（4001. 5001）R（1001 2000） R（30014000）R（5001. 6000）T1T2T4：空空T3 ：空空7、15、19 8、11、13 16、23、31 5、122、外部排序的方法、外部排序的方法 初始分布：初始分布：R（1 1000）R（20013000）R（4001. 5001）R（1001 2000） R（30014000）R（5001. 6000）T1T2T4：空空T3 ：空空 第一趟归并第一趟归并：T1 ：空空T2 ：

13、空空T3 ：T4：R（1 2000）R（40016000）R（2001 4000）2、外部排序的方法、外部排序的方法 第二趟归并第二趟归并：T3 ：空空T4 ：空空T1 ：T2：R（1 4000）R（4001 6000） 第三趟归并第三趟归并：T3 ：T4 ：空空T1 ：空空T2：空空R（1 6000）2、外部排序的方法、外部排序的方法e.g: 平衡平衡 3 路归并，路归并， K 3。 2K = 6, 需需 6条磁带。六个初始合并段均匀分布在条磁带。六个初始合并段均匀分布在 T1、T2 、T3上。每个合并段有上。每个合并段有 1000 个记录。个记录。T4、T5 、T6 初始为空。合并过程如下

14、：初始为空。合并过程如下：初始分布：初始分布：R（1 1000）R（30014000）R（1001 2000） R（40015000）T1：T2：T4：空空T3 ：R（2001 3000） R（50016000）T5：空空T6：空空 第一趟归并第一趟归并：R（1 3000）R（30016000）T4：T5：T1：空空T2：空空T3：空空T6：空空2、外部排序的方法、外部排序的方法e.g: 平衡平衡 3 路归并，路归并， K 3。 2K = 6, 需需 6条磁带。六个初始合并段均匀分布在条磁带。六个初始合并段均匀分布在 T1、T2 、T3上。每个合并段有上。每个合并段有 1000 个记录。个记录

15、。T4、T5 、T6 初始为空。合并过程如下：初始为空。合并过程如下： 第一趟归并第一趟归并：R（1 3000）R（30016000）T4：T5：T1：空空T2：空空T3：空空T6：空空 第二趟归并第二趟归并：R（1 6000）T1：T2：空空T3：空空T4：空空T5：空空T6：空空2、外部排序的方法、外部排序的方法 时间分析时间分析: 归并趟数归并趟数: logkm where k 是路数；是路数；m 是初始合并段数。是初始合并段数。 在上例中：在上例中： log26 = 3 而而 log36 = 2 此外，还有一次生成所有合并段的时间。对此外，还有一次生成所有合并段的时间。对 文件中的所有

16、的记录全部读写一次。文件中的所有的记录全部读写一次。 每一趟归并时，对文件中的所有的记录都要全部读写一次。每一趟归并时，对文件中的所有的记录都要全部读写一次。K 大，趟数减大，趟数减 少，读写记录的总数将减少。但少，读写记录的总数将减少。但 K 大，需要的内存将越多。大，需要的内存将越多。 减少初始合并段数减少初始合并段数 m, 将使趟数减少，读写记录的总数将减少。这就要求在将使趟数减少，读写记录的总数将减少。这就要求在 内存一定且进行内部排序时，内存一定且进行内部排序时， 生成尽可能长的归并段，从而减少归并段的生成尽可能长的归并段，从而减少归并段的 总数。总数。 输入、输出缓冲区的安排输入、

17、输出缓冲区的安排: 设进行平衡设进行平衡 2 路归并，路归并， K 2。 2K = 4, 需需 4条磁带。六个初条磁带。六个初 始合并段均匀分布在始合并段均匀分布在 T1、T2 。每个合并段有每个合并段有 1000 个记录。个记录。T3、T4 初始为空。初始为空。R（1 1000）R（20012000）R（4001. 5001）R（1001 2000） R（30014000）R（5001. 6000）T1T2T4：空空T3 ：空空2、外部排序的方法、外部排序的方法 输入、输出缓冲区的安排输入、输出缓冲区的安排: 设进行平衡设进行平衡 2 路归并，路归并， K 2。 2K = 4, 需需 4条磁

18、带。六个初条磁带。六个初 始合并段均匀分布在始合并段均匀分布在 T1、T2 。每个合并段有每个合并段有 1000 个记录。个记录。T3、T4 初始为空。设每初始为空。设每 个物理块包含个物理块包含 250 个记录，则每个初始合并段包含个记录，则每个初始合并段包含 4 个物理块。个物理块。K 路合并，路合并，K 个输入个输入 输入缓冲区和一个输出缓冲区。输入缓冲区和一个输出缓冲区。R（1 1000）R（20012000）R（4001. 5001）R（1001 2000） R（30014000）R（5001. 6000）T1T2T4： 空空T3 ：空空 250 个记录个记录T1T2 250 个记录

19、个记录 250 个记录个记录 250 个记录个记录 250 个记录个记录 250 个记录个记录 250 个记录个记录 250 个记录个记录IBG（Inter Block Gap）初始合并段初始合并段 ( R（1 1000）) 250 个记录个记录T3 250 个记录大个记录大 250 个记录大个记录大 K(2)个输入缓冲区个输入缓冲区 250 个记录大个记录大 1个输出缓冲区个输出缓冲区读入内存读入内存读入内存读入内存写入磁带写入磁带注意：对于缓冲区的安排，有一定的原则。注意：对于缓冲区的安排，有一定的原则。2、外部排序的方法、外部排序的方法 10 100 T1T2 150 200 220 3

20、00 350 400 1 12 13 14 15 16 17 18初始合并段初始合并段 ( R（1 8）)T3 K(2)个输入缓冲区个输入缓冲区 1 10 1个输出缓冲区个输出缓冲区读入内存读入内存读入内存读入内存写入磁带写入磁带缓冲区的安排举例：缓冲区的安排举例： 10 100 1 121 10 另一个初始合并段另一个初始合并段 ( R（1 8）)ij2、外部排序的方法、外部排序的方法 10 100 T1T2 150 200 220 300 350 400 1 12 13 14 15 16 17 18初始合并段初始合并段 ( R（1 8）)T3 K(2)个输入缓冲区个输入缓冲区 12 1个输

21、出缓冲区个输出缓冲区缓冲区的安排举例：缓冲区的安排举例： 10 100 1 121 10 另一个初始合并段另一个初始合并段 ( R（1 8）)ij2、外部排序的方法、外部排序的方法 10 100 T1T2 150 200 220 300 350 400 1 12 13 14 15 16 17 18初始合并段初始合并段 ( R（1 8）)T3 K(2)个输入缓冲区个输入缓冲区 12 1个输出缓冲区个输出缓冲区读入内存读入内存读入内存读入内存缓冲区的安排举例：缓冲区的安排举例： 10 100 13 141 10 另一个初始合并段另一个初始合并段 ( R（1 8）)ij2、外部排序的方法、外部排序的

22、方法 10 100 T1T2 150 200 220 300 350 400 1 12 13 14 15 16 17 18初始合并段初始合并段 ( R（1 8）)T3 K(2)个输入缓冲区个输入缓冲区 1个输出缓冲区个输出缓冲区读入内存读入内存缓冲区的安排举例：缓冲区的安排举例： 10 100 13 141 10 另一个初始合并段另一个初始合并段 ( R（1 8）)ij2、外部排序的方法、外部排序的方法 10 100 T1T2 150 200 220 300 350 400 1 12 13 14 15 16 17 18初始合并段初始合并段 ( R（1 8）)T3 K(2)个输入缓冲区个输入缓冲

23、区 1个输出缓冲区个输出缓冲区读入内存读入内存写入磁带写入磁带缓冲区的安排举例：缓冲区的安排举例： 10 100 13 141 10 另一个初始合并段另一个初始合并段 ( R（1 8）)ij 13 1413 14 3、多路平衡归并的实现、多路平衡归并的实现 时间分析时间分析: logkm 趟趟 K 大，趟数减少，读写记录的总数将减少。但大，趟数减少，读写记录的总数将减少。但 K 大，会带来什么问题呢？大，会带来什么问题呢？1、带、盘的平衡多路归并的性质：、带、盘的平衡多路归并的性质： e.g: K = 2 时时, m 个归并串。总共个归并串。总共 n 个记录。个记录。合并段合并段 1合并段合并

24、段 2合并段合并段 m-1合并段合并段 m中间合并段中间合并段 中间合并段中间合并段 中间合并段中间合并段中间合并段中间合并段有序文件有序文件层数：层数： log2m +1归并趟数：归并趟数： log2m3、多路平衡归并的实现、多路平衡归并的实现1、带、盘的平衡多路归并的性质：、带、盘的平衡多路归并的性质： e.g: K 2 时时, 趟数将会减少。趟数将会减少。m 个归并串。总共个归并串。总共 n 个记录。个记录。合并段合并段 1合并段合并段 k合并段合并段 m-1合并段合并段 m中间合并段中间合并段 中间合并段中间合并段有序文件有序文件层数：层数： logkm +1归并趟数：归并趟数： lo

25、gkm 设从设从 k 个元素中挑选一个最小的元素需个元素中挑选一个最小的元素需 ( k-1) 次比较。次比较。 每次比较耗费的时间代价为每次比较耗费的时间代价为: tmg，那么在进行那么在进行 k 路平衡归并时，总的比较时间耗费不会超过：路平衡归并时，总的比较时间耗费不会超过： logkm ( k - 1 ) ( n - 1 ) tmg = log2m / log2k ( k - 1 ) ( n - 1 ) tmgk log2m / log2k ( k - 1 )大大大大3、多路平衡归并的实现、多路平衡归并的实现1、带、盘的平衡多路归并的性质：、带、盘的平衡多路归并的性质： 设从设从 k 个元

26、素中挑选一个最小的元素需个元素中挑选一个最小的元素需 ( k-1) 次比较。次比较。 每次比较耗费的时间代价为每次比较耗费的时间代价为: tmg，那么在进行那么在进行 k 平衡归并时，总的时间耗费不会超过：平衡归并时，总的时间耗费不会超过： logkm ( k - 1 ) ( n - 1 ) tmg = log2m / log2k ( k - 1 ) ( n - 1 ) tmgk log2m / log2k ( k - 1 )大大大大 改进：采用胜者树或者败者树，从改进：采用胜者树或者败者树，从 K 个元素中挑选一个最小的元素仅需个元素中挑选一个最小的元素仅需 log2k 次比次比 较，这时总

27、的时间耗费将下降：较，这时总的时间耗费将下降： logkm log2k ( n - 1 ) tmg log2m ( n - 1 ) tmg 2、胜者树及其使用、胜者树及其使用胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结果，使得更快地挑出亚军、第三名果，使得更快地挑出亚军、第三名 。953、多路平衡归并的实现、多路平衡归并的实现2、胜者树及其使用、胜者树及其使用胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，

28、充分利用上一次比赛的结果，使得更快地挑出亚军、第三名果，使得更快地挑出亚军、第三名 。72959551649527871225849129385766719224748597654321输输入入缓缓冲冲区区输输出出 缓缓冲冲区区5595729976543215注意：挑出冠军注意：挑出冠军需要进行需要进行 k-1 次次比较，此处需要比较，此处需要比较比较 3 次。次。973、多路平衡归并的实现、多路平衡归并的实现2、胜者树及其使用、胜者树及其使用胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结

29、果，使得更快地挑出亚军、第三名果，使得更快地挑出亚军、第三名 。729169751649527871225849129385766719224748597654321输输入入缓缓冲冲区区输输出出 缓缓冲冲区区779167299765432157注意：挑出亚军注意：挑出亚军需要进行需要进行 log2k 次比较，此处需次比较，此处需要比较要比较 2 次。次。9123、多路平衡归并的实现、多路平衡归并的实现2、胜者树及其使用、胜者树及其使用胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结果，使得更

30、快地挑出亚军、第三名果，使得更快地挑出亚军、第三名 。1229169951649527871225849129385766719224748597654321输输入入缓缓冲冲区区输输出出 缓缓冲冲区区912916122997654321579注意：在输出缓注意：在输出缓冲区被写满之后冲区被写满之后，全部内容输出，全部内容输出至带或盘。至带或盘。3、多路平衡归并的实现、多路平衡归并的实现2、胜者树及其使用、胜者树及其使用 胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的 结果，使得更快地挑出亚军、

31、第三名结果，使得更快地挑出亚军、第三名 。 决出第一名需比较：决出第一名需比较： k - 1 次次 决出第二名需比较：决出第二名需比较： log2k 次次 决出第三名需比较：决出第三名需比较： log2k 次次 结果：采用胜者树后，从结果：采用胜者树后，从 K 个元素中挑选一个最小的元素仅需个元素中挑选一个最小的元素仅需 log2k 次比次比 较，这时总的时间耗费下降为：较，这时总的时间耗费下降为：logkm log2k ( n - 1 ) tmg log2m ( n - 1 ) tmg 有意思的是该结果和有意思的是该结果和 k 无关，这是通过多用空间换来的。无关，这是通过多用空间换来的。 改

32、进：采用胜者树，改进：采用胜者树，K 个元素中最小的元素输出之后，从根结点到它的相应的叶子结个元素中最小的元素输出之后，从根结点到它的相应的叶子结 点路径上的结点都需要进行修改，为了加快程序运行的速度产生了败者树。点路径上的结点都需要进行修改，为了加快程序运行的速度产生了败者树。2973、多路平衡归并的实现、多路平衡归并的实现3、败者树及其使用、败者树及其使用72959951649527871225849129385766719224748597654321输输入入缓缓冲冲区区输输出出 缓缓冲冲区区97295729976543215注意：挑出冠军注意：挑出冠军需要进行需要进行 k-1 次次比较

33、，此处需要比较，此处需要比较比较 3 次。次。500529163、多路平衡归并的实现、多路平衡归并的实现729169951649527871225849129385766719224748597654321输输入入缓缓冲冲区区输输出出 缓缓冲冲区区57注意：挑出亚军注意：挑出亚军需要进行需要进行 log2k 次比较，此处需次比较，此处需要比较要比较 2 次。次。3、败者树及其使用、败者树及其使用1709162916729976543210529163、多路平衡归并的实现、多路平衡归并的实现3、败者树及其使用、败者树及其使用122916912516495278712258491293857667

34、19224748597654321输输入入缓缓冲冲区区输输出出 缓缓冲冲区区579注意：在输出缓注意：在输出缓冲区被写满之后冲区被写满之后，全部内容输出，全部内容输出至带或盘。至带或盘。119016162916122997654321093、多路平衡归并的实现、多路平衡归并的实现3、败者树的程序实现、败者树的程序实现typedef int LoserTree k ; typedef struct KeyType key; Exnode, External k+1 ;Void K_Merge ( LoserTree &ls，External & b) for ( i = 0; i 0 ) if

35、(bs.key blst.key) s lst; t = t / 2; / s 指示新的胜者的地址。指示新的胜者的地址。 bs.key=blst.key, 则则 bs仍是胜者。仍是胜者。 ls0 = s; / AdjustVoid CreateLoserTree ( LoserTree &ls ) bk.key = MINKEY; for ( i=0; i = 0; - - i ) Adjust(ls,i); / CreateLoserTreekk3、多路平衡归并的实现、多路平衡归并的实现 败者树程序实现：败者树程序实现：72959k516495278712258491293857667192

36、2474859321021输输入入缓缓冲冲区区输输出出 缓缓冲冲区区注意：在输出缓注意：在输出缓冲区被写满之后冲区被写满之后，全部内容输出，全部内容输出至带或盘。至带或盘。11k0存于存于 b0 bk-1之中之中注意：注意： bk = - 存于存于 ls0 lsk-1 之中之中33k3、多路平衡归并的实现、多路平衡归并的实现 败者树程序实现：败者树程序实现：72959k5164952787122584912938576671922474859321021输输入入缓缓冲冲区区输输出出 缓缓冲冲区区注意：在输出缓注意：在输出缓冲区被写满之后冲区被写满之后，全部内容输出，全部内容输出至带或盘。至带或

37、盘。11k0存于存于 b0 bk-1之中之中注意：注意： bk = - 存于存于 ls0 lsk-1 之中之中32k3、多路平衡归并的实现、多路平衡归并的实现 败者树程序实现：败者树程序实现：7295935164952787122584912938576671922474859321021输输入入缓缓冲冲区区输输出出 缓缓冲冲区区注意：在输出缓注意：在输出缓冲区被写满之后冲区被写满之后，全部内容输出，全部内容输出至带或盘。至带或盘。11k0存于存于 b0 bk-1之中之中注意：注意： bk = - 存于存于 ls0 lsk-1 之中之中3213、多路平衡归并的实现、多路平衡归并的实现 败者树程

38、序实现：败者树程序实现：7295935164952787122584912938576671922474859321021输输入入缓缓冲冲区区输输出出 缓缓冲冲区区注意：在输出缓注意：在输出缓冲区被写满之后冲区被写满之后，全部内容输出，全部内容输出至带或盘。至带或盘。11k0存于存于 b0 bk-1之中之中注意：注意： bk = - 存于存于 ls0 lsk-1 之中之中3213、多路平衡归并的实现、多路平衡归并的实现 败者树程序实现：败者树程序实现：7295935164952787122584912938576671922474859321021输输入入缓缓冲冲区区输输出出 缓缓冲冲区区注意

39、：在输出缓注意：在输出缓冲区被写满之后冲区被写满之后，全部内容输出，全部内容输出至带或盘。至带或盘。1100存于存于 b0 bk-1之中之中注意：注意： bk = - 存于存于 ls0 lsk-1 之中之中35213、多路平衡归并的实现、多路平衡归并的实现 败者树程序实现：败者树程序实现：7295935164952787122584912938576671922474859321021输输入入缓缓冲冲区区输输出出 缓缓冲冲区区注意：在输出缓注意：在输出缓冲区被写满之后冲区被写满之后，全部内容输出，全部内容输出至带或盘。至带或盘。1100存于存于 b0 bk-1之中之中 注意：注意：bk = -

40、 存于存于 ls0 lsk-1 之中之中35213、多路平衡归并的实现、多路平衡归并的实现 败者树程序实现：记录输出结束后，可能出现如下情况。此时败者树程序实现：记录输出结束后，可能出现如下情况。此时 bls0 = +，程序结束。程序结束。3321021输输入入缓缓冲冲区区输输出出 缓缓冲冲区区注意：每一个归注意：每一个归并段的最后加一并段的最后加一个字段为个字段为 + ，即书上所说的即书上所说的 MAXKEY，作为作为结束条件。结束条件。1100存于存于 b0 bk-1之中之中 注意：注意：bk = - 存于存于 ls0 lsk-1 之中之中3+4、置换、置换-选择排序选择排序1、作用：产生

41、尽可能长的初始归并段。在内存长度一定时，按照通常的排序方法，产生的、作用：产生尽可能长的初始归并段。在内存长度一定时，按照通常的排序方法，产生的 初始归并段的长度只能和内存长度相同，但采用本方法之后可以产生却可以生成初始归并段的长度只能和内存长度相同，但采用本方法之后可以产生却可以生成 两倍内存长度的初始归并段（平均情况下）。两倍内存长度的初始归并段（平均情况下）。2、实例：、实例：F1：31、21、19、12、26、41、11、37、15、23、29 在带在带 1 上上 F2： 输出磁带输出磁带 2 假定使用的内存只有假定使用的内存只有 3 个记录长，利用置换个记录长，利用置换-选择分类法产

42、生初始合并段。选择分类法产生初始合并段。4、置换、置换-选择排序选择排序 实例的实现过程：实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带在带 1 上上 步数步数内存缓冲区内容（由内存缓冲区内容（由 F1 输入）输入）输出结果（至带输出结果（至带 F2 ）131、 21、 19194、置换、置换-选择排序选择排序 实例的实现过程：实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带在带 1 上上 步数步数内存缓冲区内容（由内存缓冲区内容（由 F1 输入）输入）输出结果（至带输出结果（至带 F2 ）131、

43、21、 1919231、 21、 (12)214、置换、置换-选择排序选择排序 实例的实现过程：实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带在带 1 上上 步数步数内存缓冲区内容（由内存缓冲区内容（由 F1 输入）输入）输出结果（至带输出结果（至带 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)264、置换、置换-选择排序选择排序 实例的实现过程：实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带在带 1 上上 步数步数内存缓冲区内容（由内存缓冲区内容（由

44、F1 输入）输入）输出结果（至带输出结果（至带 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)314、置换、置换-选择排序选择排序 实例的实现过程：实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带在带 1 上上 步数步数内存缓冲区内容（由内存缓冲区内容（由 F1 输入）输入）输出结果（至带输出结果（至带 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)315(11)、41、 (12)414、置换、置换-选

45、择排序选择排序 实例的实现过程：实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带在带 1 上上 步数步数内存缓冲区内容（由内存缓冲区内容（由 F1 输入）输入）输出结果（至带输出结果（至带 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)315(11)、41、 (12)416(11)、(37)、(12) #第一个初始合并段第一个初始合并段4、置换、置换-选择排序选择排序 实例的实现过程：实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在

46、带在带 1 上上 步数步数内存缓冲区内容（由内存缓冲区内容（由 F1 输入）输入）输出结果（至带输出结果（至带 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)315(11)、41、 (12)416(11)、(37)、(12) #711、37、12114、置换、置换-选择排序选择排序 实例的实现过程：实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带在带 1 上上 步数步数内存缓冲区内容（由内存缓冲区内容（由 F1 输入）输入）输出结果（至带输出结果（至带 F2 ）131、 21

47、、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)315(11)、41、 (12)416(11)、(37)、(12) #711、37、1211815、37、12124、置换、置换-选择排序选择排序 实例的实现过程：实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带在带 1 上上 步数步数内存缓冲区内容（由内存缓冲区内容（由 F1 输入）输入）输出结果（至带输出结果（至带 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)315(11)

48、、41、 (12)416(11)、(37)、(12) #711、37、1211815、37、1212915、37、23154、置换、置换-选择排序选择排序 实例的实现过程：实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带在带 1 上上 步数步数内存缓冲区内容（由内存缓冲区内容（由 F1 输入）输入）输出结果（至带输出结果（至带 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)315(11)、41、 (12)416(11)、(37)、(12) #711、37、1211815、37

49、、1212915、37、23151029、37、23 234、置换、置换-选择排序选择排序 实例的实现过程：实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带在带 1 上上 步数步数内存缓冲区内容（由内存缓冲区内容（由 F1 输入）输入）输出结果（至带输出结果（至带 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)315(11)、41、 (12)416(11)、(37)、(12) #711、37、1211815、37、1212915、37、23151029、37、23 2311

50、29、37294、置换、置换-选择排序选择排序 实例的实现过程：实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带在带 1 上上 步数步数内存缓冲区内容（由内存缓冲区内容（由 F1 输入）输入）输出结果（至带输出结果（至带 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)315(11)、41、 (12)416(11)、(37)、(12) #711、37、1211815、37、1212915、37、23151029、37、23 2311 29、372912 37374、置换、置换-

51、选择排序选择排序 实例的实现过程：实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带在带 1 上上 步数步数内存缓冲区内容（由内存缓冲区内容（由 F1 输入）输入）输出结果（至带输出结果（至带 F2 ）131、 21、 1919231、 21、 (12)21331、 26、 (12)26431、 41、 (12)315(11)、41、 (12)416(11)、(37)、(12) #711、37、1211815、37、1212915、37、23151029、37、23 2311 29、372912 373713#第二个初始合并段第二个初始合并段第一个初

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

53、下，合并段的平均长度为合并段的平均长度为 2m 。 书上介绍：该结论由：书上介绍：该结论由：EFMoore 在在 1961 年从置换选择排序同扫雪机的类比中得年从置换选择排序同扫雪机的类比中得 到的。不过我认为这种证明完全是胡扯。到的。不过我认为这种证明完全是胡扯。4、程序实现：、程序实现： 可以用败者树的办法可以用败者树的办法 加以实现。加以实现。32144、置换、置换-选择排序选择排序5、败者树实现置换、败者树实现置换-选择排序选择排序522901051、49、39、46、38、29、14、61、1546139149151129138154332044、置换、置换-选择排序选择排序5、败者

54、树实现置换、败者树实现置换-选择排序选择排序52293801151、49、39、46、38、29、14、61、1546139149151114238154312044、置换、置换-选择排序选择排序5、败者树实现置换、败者树实现置换-选择排序选择排序5229383901351、49、39、46、38、29、14、61、1546139149151114261154312044、置换、置换-选择排序选择排序5、败者树实现置换、败者树实现置换-选择排序选择排序532938394601251、49、39、46、38、29、14、61、15461152491511142611543注意：在全部的注意：在全

55、部的 段号标志变成段号标志变成 2 之后，合并段之后，合并段 1 的记录已全部生的记录已全部生成。成。？K 值越大越好吗！5、最佳归并树、最佳归并树1、最佳归并树、最佳归并树 起因：由于初始归并段通常不等长。起因：由于初始归并段通常不等长。 目的：减少读写外存的次数。目的：减少读写外存的次数。 限制：由于磁带寻找具有最少记录的初始归并段，必须反复倒带。所以，实用性不强。在盘限制：由于磁带寻找具有最少记录的初始归并段，必须反复倒带。所以，实用性不强。在盘 的情况下，需要有段包含的记录数信息、段的位置信息等。文件如集中放置在几个相的情况下，需要有段包含的记录数信息、段的位置信息等。文件如集中放置在

56、几个相 邻的柱面上的情况比较合适。邻的柱面上的情况比较合适。e.g:假定由置换选择分类法生成了假定由置换选择分类法生成了 9 个初始归并段，记录数分别为个初始归并段，记录数分别为 9、30、12、18、3、17、 2、 6、24 。如果进行。如果进行 3-路归并，请讨论在各种情况下的对外存的读写次数。路归并，请讨论在各种情况下的对外存的读写次数。301293171862425138 32121从外存读从外存读 121 个记录个记录写入外存写入外存 121 个记录个记录从外存读从外存读 121 个记录个记录写入外存写入外存 121 个记录个记录 A.总共读写外存总共读写外存 484 个记录个记录

57、5、最佳归并树、最佳归并树1、最佳归并树、最佳归并树 6239241718301132 59121从外存读从外存读 11 个记录个记录写入外存写入外存 11 个记录个记录从外存读从外存读 91个记录个记录写入外存写入外存 121 个记录个记录 B.写入外存写入外存 91 个记录个记录从外存读从外存读 121 个记录个记录12总共读写外存总共读写外存 446 个记录个记录5、最佳归并树、最佳归并树1、最佳归并树、最佳归并树 326924171812520 4791从外存读从外存读 5 个记录个记录写入外存写入外存 5 个记录个记录从外存读从外存读 67 个记录个记录写入外存写入外存 91 个记录

58、个记录 C.写入外存写入外存 67 个记录个记录从外存读从外存读 91 个记录个记录总共读写外存总共读写外存 326 个记录个记录 按照按照 HUFFMAN 树的思想，记录少的段最先合并。不够时增加虚段。如下例所示。树的思想，记录少的段最先合并。不够时增加虚段。如下例所示。 8 个初始归并段个初始归并段，记录数分别为，记录数分别为 9、12、18、3、17、2、6、24。5、最佳归并树、最佳归并树1、最佳归并树、最佳归并树 按照按照 HUFFMAN 树的思想，记录少的段最先合并。不够时增加虚段。树的思想，记录少的段最先合并。不够时增加虚段。 虚段的段数的计算虚段的段数的计算:解：在解：在 K

59、路平衡归并时，它的归并树的模型是一棵度为路平衡归并时，它的归并树的模型是一棵度为 K 的树。在这棵树上的结点要么的树。在这棵树上的结点要么 是叶子，要么是具有是叶子，要么是具有 K 个儿子的内部结点。设具有个儿子的内部结点。设具有 K 个儿子的内部结点共有个儿子的内部结点共有 nk 个个 。初始归并段的个数为。初始归并段的个数为 m 个。个。 设设 n = nk + m ，故：故： 从结点出发的枝条，共计有：从结点出发的枝条，共计有：K nk 根根 若从进入结点结点的角度进行考虑，则共有：若从进入结点结点的角度进行考虑，则共有： 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)。