《外部排序》课件.ppt

《《外部排序》课件.ppt》由会员分享，可在线阅读，更多相关《《外部排序》课件.ppt（61页珍藏版）》请在三一办公上搜索。

1、1、外存信息的存取2、外部排序的方法3、多路平衡归并的实现4、置换-选择排序5、最佳归并树,第11章 外部排序,1、外存信息的存取2、外部排序的方法,1、外存信息的存取,1、外部排序：内部排序：信息一次可全部调入内存，信息在内存中的处理时间是主要的时间耗费。外部排序：信息量巨大，无法一次调入内存。只能驻留在带、盘、CD-ROM 上。特点 为内存运行时间短，内、外存进行交换需要时间长。减少 I/O 时间成为主 要矛盾。,记录（Record）：数据项的集合存于内存，称之为结点。如果存之于外存，则叫做记 录。原因起源于是在历史上研究管理应用和计算机科学的两部分人员的习惯。 域（场）：记录中的每个数据

2、项，称之为域（Field） 。 文件：记录的集合。 关键字：唯一标识记录的域，称之为关键字。 有序文件：文件根据关键字的大小。排成递增或递减的序列。,2、基本术语：,3、常用外存：,磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。 查找费时、速度幔。,1、外存信息的存取1、外部排序： 记录（Record）：数,1、外存信息的存取,3、常用外存：,磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。 便宜、可反复使用、是一种顺序存取设备。 查找费时、速度慢。 带信息的表示：,一种磁化方向、代表1,另一种磁化方向，代表0,01001001,1

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

4、v,t,可靠读写区,IRG：.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 延迟时间：读写头到达相应的记录起始位置的时间。 tw 读/写一个字符的时间； n 字符数。,读写头,1、外存信息的存取3、

5、常用外存： 带文件的组织：记录 1,1、外存信息的存取,3、常用外存：,带文件的组织的改进：,块 1,块 3,块 2,IBG（Inter Block Gap）块间间隙,IBG：.5.75 inch，带来的好处是什么？ 每一块是一个物理记录，包含若干个逻辑记录。 B.F（块因子） 一个物理记录包含逻辑记录的个数 带的利用率上升，如上例： 设 B.F = 100 1000 /100 0.6 6 inch ( total IBG ) 1000 80/800 100 inch ( file) 利用率 100/106 = 94.3 %,1、外存信息的存取3、常用外存： 带文件的组织的改进：块,1、外存信

6、息的存取,3、常用外存：,磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。 速度快、容量大、直接存取设备。 种类：固定头磁盘、活动头磁盘 固定头磁盘：每个磁道都有一个磁头（速度快） 活动头磁盘：每个盘面共用一个磁头， 增加了找道的时间，应用广泛。,柱面：各盘面的直径相同的磁道的总和。,物理位置：盘组号、若干个磁盘构成一组，系统可能有许 多组。 柱面号、 磁道号、 块（扇区号）,盘文件的读写时间：T i/o = tseck + tla + ntwm tseck ：找道时间tla ：等待时间twm ：传输时间/ 字符，n 字符数。,1、外存信息的存取3、常用外存： 磁盘：由

7、存取装置、读、写,2、外部排序的方法,1、步骤：,生成合并段（run）：读入文件的部分记录到内存 在内存中进行内部排序 将排好序的这些记录写入外存，形成合并段 再读入该文件 的下面的记录，往复进行，直至文件中的记录全部形成合并段 为止。,外部合并：将上一阶段生成的合并段调入内存，进行合并，直至最后形成一个有序的文 件。,平衡合并分类法：被合并的初始合并段均匀分布在 K 条磁带上，即分布在 T1、T2、 Tk 上。对这 K 条带进行合并，将生成的中间归并段分布在 TK+1、 TK+2 、 T2K 上。然后，循环往复，直至最后形成一个 单一的合并段为止。e.g: 平衡 2 路归并， K 2。 2K

8、 = 4, 需 4条磁带。六个初始合并段均匀分布在 T1、T2 上。每个合并段有 1000 个记录。T3、T4 初始为空。合并过程如下：初始分布：,R（1 1000）,R（20012000）,R（4001. 5001）,R（1001 2000）,R（30014000）,R（5001. 6000）,T1,T2,T4：空,T3 ：空,7、15、19 8、11、13 16、23、31 5、12,2、外部排序的方法1、步骤： 生成合并段（run）：读入文,2、外部排序的方法,初始分布：,R（1 1000）,R（20013000）,R（4001. 5001）,R（1001 2000）,R（3001400

9、0）,R（5001. 6000）,T1,T2,T4：空,T3 ：空,第一趟归并：,T1 ：空,T2 ：空,T3 ：,T4：,R（1 2000）,R（40016000）,R（2001 4000）,2、外部排序的方法 初始分布：R（1 1000）R（2,2、外部排序的方法,第二趟归并：,T3 ：空,T4 ：空,T1 ：,T2：,R（1 4000）,R（4001 6000）,第三趟归并：,T3 ：,T4 ：空,T1 ：空,T2：空,R（1 6000）,2、外部排序的方法 第二趟归并：T3 ：空T4 ：空T1,2、外部排序的方法,e.g: 平衡 3 路归并， K 3。 2K = 6, 需 6条磁带。六

10、个初始合并段均匀分布在 T1、T2 、T3上。每个合并段有 1000 个记录。T4、T5 、T6 初始为空。合并过程如下：初始分布：,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。,2、外部排序的方法,e.g: 平衡 3 路归并， K 3。 2K = 6, 需 6条磁带。六个

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

12、录全部读写一次。 每一趟归并时，对文件中的所有的记录都要全部读写一次。K 大，趟数减 少，读写记录的总数将减少。但 K 大，需要的内存将越多。 减少初始合并段数 m, 将使趟数减少，读写记录的总数将减少。这就要求在 内存一定且进行内部排序时， 生成尽可能长的归并段，从而减少归并段的 总数。,输入、输出缓冲区的安排: 设进行平衡 2 路归并， K 2。 2K = 4, 需 4条磁带。六个初 始合并段均匀分布在 T1、T2 。每个合并段有 1000 个记录。T3、T4 初始为空。,R（1 1000）,R（20012000）,R（4001. 5001）,R（1001 2000）,R（30014000

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

14、0）,T1,T2,T4： 空,T3 ：空,250 个记录,T1,T2,250 个记录,250 个记录,250 个记录,250 个记录,250 个记录,250 个记录,250 个记录,IBG（Inter Block Gap）,初始合并段 ( R（1 1000）),250 个记录,T3,250 个记录大,250 个记录大,K(2)个输入缓冲区,250 个记录大,1个输出缓冲区,读入内存,读入内存,写入磁带,注意：对于缓冲区的安排，有一定的原则。,2、外部排序的方法 输入、输出缓冲区的安排: 设进行平衡,2、外部排序的方法,10 100,T1,T2,150 200,220 300,350 400,1

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

16、并段 ( R（1 8）),i,j,2、外部排序的方法 10 100 T1T2 150,2、外部排序的方法,10 100,T1,T2,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 14,1 10,另一个初始合并段 ( R（1 8）),i,j,2、外部排序的方法 10 100 T1T2 150,2、外部排序的方法,10 100,T1,T2,150 200,220 300,350 400,1 12,13 14,1

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

18、13 14,13 14,2、外部排序的方法 10 100 T1T2 150,3、多路平衡归并的实现,时间分析: logkm 趟 K 大，趟数减少，读写记录的总数将减少。但 K 大，会带来什么问题呢？,1、带、盘的平衡多路归并的性质：,e.g: K = 2 时, m 个归并串。总共 n 个记录。,合并段 1,合并段 2,合并段 m-1,合并段 m,中间合并段,中间合并段,中间合并段,中间合并段,有序文件,层数： log2m +1归并趟数： log2m,3、多路平衡归并的实现 时间分析: logkm,3、多路平衡归并的实现,1、带、盘的平衡多路归并的性质：,e.g: K 2 时, 趟数将会减少。m

19、 个归并串。总共 n 个记录。,合并段 1,合并段 k,合并段 m-1,合并段 m,中间合并段,中间合并段,有序文件,层数： logkm +1归并趟数： logkm,设从 k 个元素中挑选一个最小的元素需 ( k-1) 次比较。 每次比较耗费的时间代价为: tmg，那么在进行 k 路平衡归并时，总的比较时间耗费不会超过： logkm ( k - 1 ) ( n - 1 ) tmg = log2m / log2k ( k - 1 ) ( n - 1 ) tmgk log2m / log2k ( k - 1 ),大,大,3、多路平衡归并的实现1、带、盘的平衡多路归并的性质： e,3、多路平衡归并的

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

21、、胜者树及其使用胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结果，使得更快地挑出亚军、第三名 。,3、多路平衡归并的实现1、带、盘的平衡多路归并的性质： 设,9,5,3、多路平衡归并的实现,2、胜者树及其使用胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结果，使得更快地挑出亚军、第三名 。,7,29,5,9,5,516495278,712258491,2938576671,922474859,7,6,5,4,3,2,1,输入缓冲区,输出 缓冲区,5,5,9,5,7,29,9,7,6,5,4,3,2,1,5,注意：挑出冠军需要进行 k-1

22、 次比较，此处需要比较 3 次。,953、多路平衡归并的实现2、胜者树及其使用72959557,9,7,3、多路平衡归并的实现,2、胜者树及其使用胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结果，使得更快地挑出亚军、第三名 。,7,29,16,9,7,516495278,712258491,2938576671,922474859,7,6,5,4,3,2,1,输入缓冲区,输出 缓冲区,7,7,9,16,7,29,9,7,6,5,4,3,2,1,57,注意：挑出亚军需要进行 log2k 次比较，此处需要比较 2 次。,973、多路平衡归并的实现2、胜者树及其使用72

23、916975,9,12,3、多路平衡归并的实现,2、胜者树及其使用胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结果，使得更快地挑出亚军、第三名 。,12,29,16,9,9,516495278,712258491,2938576671,922474859,7,6,5,4,3,2,1,输入缓冲区,输出 缓冲区,9,12,9,16,12,29,9,7,6,5,4,3,2,1,579,注意：在输出缓冲区被写满之后，全部内容输出至带或盘。,9123、多路平衡归并的实现2、胜者树及其使用1229169,3、多路平衡归并的实现,2、胜者树及其使用 胜者进入下一轮，直至决出本次

24、比赛的冠军。决出冠军之后，充分利用上一次比赛的 结果，使得更快地挑出亚军、第三名 。 决出第一名需比较： k - 1 次 决出第二名需比较： log2k 次 决出第三名需比较： log2k 次,结果：采用胜者树后，从 K 个元素中挑选一个最小的元素仅需 log2k 次比 较，这时总的时间耗费下降为：logkm log2k ( n - 1 ) tmg log2m ( n - 1 ) tmg 有意思的是该结果和 k 无关，这是通过多用空间换来的。,改进：采用胜者树，K 个元素中最小的元素输出之后，从根结点到它的相应的叶子结 点路径上的结点都需要进行修改，为了加快程序运行的速度产生了败者树。,3、多

25、路平衡归并的实现2、胜者树及其使用 结果：采用胜者树,29,7,3、多路平衡归并的实现,3、败者树及其使用,7,29,5,9,9,516495278,712258491,2938576671,922474859,7,6,5,4,3,2,1,输入缓冲区,输出 缓冲区,9,7,29,5,7,29,9,7,6,5,4,3,2,1,5,注意：挑出冠军需要进行 k-1 次比较，此处需要比较 3 次。,5,0,0,5,2973、多路平衡归并的实现3、败者树及其使用7295995,29,16,3、多路平衡归并的实现,7,29,16,9,9,516495278,712258491,2938576671,922

26、474859,7,6,5,4,3,2,1,输入缓冲区,输出 缓冲区,57,注意：挑出亚军需要进行 log2k 次比较，此处需要比较 2 次。,3、败者树及其使用,1,7,0,9,16,29,16,7,29,9,7,6,5,4,3,2,1,0,5,29163、多路平衡归并的实现729169957299765,29,16,3、多路平衡归并的实现,3、败者树及其使用,12,29,16,9,12,516495278,712258491,2938576671,922474859,7,6,5,4,3,2,1,输入缓冲区,输出 缓冲区,579,注意：在输出缓冲区被写满之后，全部内容输出至带或盘。,1,1,9

27、,0,16,16,29,16,12,29,9,7,6,5,4,3,2,1,0,9,29163、多路平衡归并的实现3、败者树及其使用122916,3、多路平衡归并的实现,3、败者树的程序实现typedef int LoserTree k ; typedef struct KeyType key; Exnode, External k+1 ;,Void K_Merge ( LoserTree / 将含最大关键字MAXKEY的记录写至输出归并段 / K_Merge,3、多路平衡归并的实现3、败者树的程序实现Void K_Me,3、多路平衡归并的实现,3、败者树的程序实现,Void Adjust (

28、LoserTree / Adjust,Void CreateLoserTree ( LoserTree / CreateLoserTree,3、多路平衡归并的实现3、败者树的程序实现Void Adj,k,k,3、多路平衡归并的实现,败者树程序实现：,7,29,5,9,k,516495278,712258491,2938576671,922474859,3,2,1,0,2,1,输入缓冲区,输出 缓冲区,注意：在输出缓冲区被写满之后，全部内容输出至带或盘。,1,1,k,0,存于 b0 bk-1之中注意： bk = - ,存于 ls0 lsk-1 之中,3,kk3、多路平衡归并的实现 败者树程序实现

29、：72959k5,3,k,3、多路平衡归并的实现,败者树程序实现：,7,29,5,9,k,516495278,712258491,2938576671,922474859,3,2,1,0,2,1,输入缓冲区,输出 缓冲区,注意：在输出缓冲区被写满之后，全部内容输出至带或盘。,1,1,k,0,存于 b0 bk-1之中注意： bk = - ,存于 ls0 lsk-1 之中,3,3k3、多路平衡归并的实现 败者树程序实现：72959k5,2,k,3、多路平衡归并的实现,败者树程序实现：,7,29,5,9,3,516495278,712258491,2938576671,922474859,3,2,1

30、,0,2,1,输入缓冲区,输出 缓冲区,注意：在输出缓冲区被写满之后，全部内容输出至带或盘。,1,1,k,0,存于 b0 bk-1之中注意： bk = - ,存于 ls0 lsk-1 之中,3,2k3、多路平衡归并的实现 败者树程序实现：7295935,2,1,3、多路平衡归并的实现,败者树程序实现：,7,29,5,9,3,516495278,712258491,2938576671,922474859,3,2,1,0,2,1,输入缓冲区,输出 缓冲区,注意：在输出缓冲区被写满之后，全部内容输出至带或盘。,1,1,k,0,存于 b0 bk-1之中注意： bk = - ,存于 ls0 lsk-1

31、 之中,3,213、多路平衡归并的实现 败者树程序实现：7295935,2,1,3、多路平衡归并的实现,败者树程序实现：,7,29,5,9,3,516495278,712258491,2938576671,922474859,3,2,1,0,2,1,输入缓冲区,输出 缓冲区,注意：在输出缓冲区被写满之后，全部内容输出至带或盘。,1,1,0,0,存于 b0 bk-1之中注意： bk = - ,存于 ls0 lsk-1 之中,3,5,213、多路平衡归并的实现 败者树程序实现：7295935,2,1,3、多路平衡归并的实现,败者树程序实现：,7,29,5,9,3,516495278,7122584

32、91,2938576671,922474859,3,2,1,0,2,1,输入缓冲区,输出 缓冲区,注意：在输出缓冲区被写满之后，全部内容输出至带或盘。,1,1,0,0,存于 b0 bk-1之中 注意：bk = - ,存于 ls0 lsk-1 之中,3,5,213、多路平衡归并的实现 败者树程序实现：7295935,2,1,3、多路平衡归并的实现,败者树程序实现：记录输出结束后，可能出现如下情况。此时 bls0 = +，程序结束。,3,3,2,1,0,2,1,输入缓冲区,输出 缓冲区,注意：每一个归并段的最后加一个字段为 + ，即书上所说的 MAXKEY，作为结束条件。,1,1,0,0,存于 b

33、0 bk-1之中 注意：bk = - ,存于 ls0 lsk-1 之中,3,+,+,+,+,+,+,+,+,213、多路平衡归并的实现 败者树程序实现：记录输出结束后,4、置换-选择排序,1、作用：产生尽可能长的初始归并段。在内存长度一定时，按照通常的排序方法，产生的 初始归并段的长度只能和内存长度相同，但采用本方法之后可以产生却可以生成 两倍内存长度的初始归并段（平均情况下）。,2、实例：F1：31、21、19、12、26、41、11、37、15、23、29 在带 1 上 F2： 输出磁带 2 假定使用的内存只有 3 个记录长，利用置换-选择分类法产生初始合并段。,4、置换-选择排序1、作用

34、：产生尽可能长的初始归并段。在内存,4、置换-选择排序,实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带 1 上,步数内存缓冲区内容（由 F1 输入）输出结果（至带 F2 ）131、 21、 1919,4、置换-选择排序 实例的实现过程： F1：31、21、19,4、置换-选择排序,实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带 1 上,步数内存缓冲区内容（由 F1 输入）输出结果（至带 F2 ）131、 21、 1919231、 21、 (12)21,4、置换-选择排序 实例的实现过程： F1：31

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

36、6、 (12)26431、 41、 (12)31,4、置换-选择排序 实例的实现过程： F1：31、21、19,4、置换-选择排序,实例的实现过程： 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)41,4、置换-选择排序 实例的实现过程： F1：31、21、19,4、置换-选择排序,实例的实现过程： F1：31、21、19、12、26、41、11、37、

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,4、置换-选择排序,实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带 1 上,步数内存缓冲区内容（由 F1 输入）输出结果（至带 F2 ）131、 21、 1919231、 21、 (12)2133

38、1、 26、 (12)26431、 41、 (12)315(11)、41、 (12)416(11)、(37)、(12) #711、37、1211,4、置换-选择排序 实例的实现过程： F1：31、21、19,4、置换-选择排序,实例的实现过程： 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、121181

39、5、37、1212,4、置换-选择排序 实例的实现过程： F1：31、21、19,4、置换-选择排序,实例的实现过程： 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、2315,4、置换-选择排序 实例的实现过程： F1：31、21、19,4、置换-选择排序,实

40、例的实现过程： 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 23,4、置换-选择排序 实例的实现过程： F1：31、21、19,4、置换-选择排序,实例的实现过程： F1：31、21、19、12、26、41、11、37、15、2

41、3、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、3729,4、置换-选择排序 实例的实现过程： F1：31、21、19,4、置换-选择排序,实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带 1 上,步数内存缓冲区内容（由 F1 输入

42、）输出结果（至带 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 3737,4、置换-选择排序 实例的实现过程： F1：31、21、19,4、置换-选择排序,实例的实现过程： F1：31、21、19、12、26、41、11、37、15、23、29 在带 1 上,步数内存缓冲区内容（由 F1 输入）输出结果（至带 F2 ）131、 21、

43、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#,第二个初始合并段,第一个初始合并段,4、置换-选择排序 实例的实现过程： F1：31、21、19,4、置换-选择排序,3、长度分析： 设内存可以存放 m 个记录，则首先从文件读入 m 记录到内存。这 m 个记录 肯定可以归入本初始合并段内。这样，必须从文件中读入 m 个记录。这 m 个 记录中平均有一

44、半可以归入本合并段，一半归入下一合并段。 因此，合并段的平均长度为：m + m/2 + m/4 + = 2m 所以，在平均情况下，合并段的平均长度为 2m 。 书上介绍：该结论由：EFMoore 在 1961 年从置换选择排序同扫雪机的类比中得 到的。不过我认为这种证明完全是胡扯。,4、程序实现： 可以用败者树的办法 加以实现。,4、置换-选择排序 3、长度分析：4、程序实现：,3,2,1,4,4、置换-选择排序,5、败者树实现置换-选择排序,5,2,29,0,1,0,51、49、39、46、38、29、14、61、15,461,391,491,511,291,381,5,4,3,32144、

45、置换-选择排序5、败者树实现置换-选择排序522,3,2,0,4,4、置换-选择排序,5、败者树实现置换-选择排序,5,2,2938,0,1,1,51、49、39、46、38、29、14、61、15,461,391,491,511,142,381,5,4,3,32044、置换-选择排序5、败者树实现置换-选择排序522,1,2,0,4,4、置换-选择排序,5、败者树实现置换-选择排序,5,2,293839,0,1,3,51、49、39、46、38、29、14、61、15,461,391,491,511,142,611,5,4,3,12044、置换-选择排序5、败者树实现置换-选择排序522,1

46、,2,0,4,4、置换-选择排序,5、败者树实现置换-选择排序,5,3,29383946,0,1,2,51、49、39、46、38、29、14、61、15,461,152,491,511,142,611,5,4,3,注意：在全部的 段号标志变成 2 之后，合并段 1 的记录已全部生成。,？K 值越大越好吗！,12044、置换-选择排序5、败者树实现置换-选择排序532,5、最佳归并树,1、最佳归并树 起因：由于初始归并段通常不等长。 目的：减少读写外存的次数。 限制：由于磁带寻找具有最少记录的初始归并段，必须反复倒带。所以，实用性不强。在盘 的情况下，需要有段包含的记录数信息、段的位置信息等。

47、文件如集中放置在几个相 邻的柱面上的情况比较合适。,e.g:假定由置换选择分类法生成了 9 个初始归并段，记录数分别为 9、30、12、18、3、17、 2、 6、24 。如果进行 3-路归并，请讨论在各种情况下的对外存的读写次数。,30,12,9,3,17,18,6,24,2,51,38,32,121,从外存读 121 个记录,写入外存 121 个记录,从外存读 121 个记录,写入外存 121 个记录,A.,总共读写外存 484 个记录,5、最佳归并树1、最佳归并树e.g:假定由置换选择分类法生,5、最佳归并树,1、最佳归并树,6,2,3,9,24,17,18,30,11,32,59,12

48、1,从外存读 11 个记录,写入外存 11 个记录,从外存读 91个记录,写入外存 121 个记录,B.,写入外存 91 个记录,从外存读 121 个记录,12,总共读写外存 446 个记录,5、最佳归并树1、最佳归并树 623924171830113,5、最佳归并树,1、最佳归并树,3,2,6,9,24,17,18,12,5,20,47,91,从外存读 5 个记录,写入外存 5 个记录,从外存读 67 个记录,写入外存 91 个记录,C.,写入外存 67 个记录,从外存读 91 个记录,总共读写外存 326 个记录,按照 HUFFMAN 树的思想，记录少的段最先合并。不够时增加虚段。如下例所

49、示。 8 个初始归并段，记录数分别为 9、12、18、3、17、2、6、24。,5、最佳归并树1、最佳归并树 326924171812520,5、最佳归并树,1、最佳归并树,按照 HUFFMAN 树的思想，记录少的段最先合并。不够时增加虚段。 虚段的段数的计算:,解：在 K 路平衡归并时，它的归并树的模型是一棵度为 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)。,5、最佳归并树1、最佳归并树 按照 HUFFMAN 树的思,