《数据结构第十一部分外部排序》由会员分享，可在线阅读，更多相关《数据结构第十一部分外部排序（35页珍藏版）》请在金锄头文库上搜索。
1、中国科大数据结构数据结构第十一部分外部排序Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望本章内容本章内容11.1 11.1 外存信息的存取外存信息的存取外存信息的存取外存信息的存取11.2 11.2 外部排序的方法外部排序的方法外部排序的方法外部排序的方法11.3 11.3 多路平衡归并的实现多路平衡归并的实现多路平衡归并的实现多路平衡归并的实现11.4 11.4 置换置换置换置换- -选择排序选择排序选择排序选择排序11.5 11.5 最佳归并树最佳归并树最佳归并树最佳归并树11
2、- 中国科大数据结构11.1 外存信息的存取pp常用的外存储器分类：常用的外存储器分类：常用的外存储器分类：常用的外存储器分类：n n顺序存取的设备（如磁带）；顺序存取的设备（如磁带）；顺序存取的设备（如磁带）；顺序存取的设备（如磁带）；n n随机存取的设备（如磁盘）。随机存取的设备（如磁盘）。随机存取的设备（如磁盘）。随机存取的设备（如磁盘）。常用的外存储器是磁表面存储器常用的外存储器是磁表面存储器常用的外存储器是磁表面存储器常用的外存储器是磁表面存储器, , , , 信息记录在一薄层磁性材料信息记录在一薄层磁性材料信息记录在一薄层磁性材料信息记录在一薄层磁性材料的表面上的表面上的表面上的表
3、面上, , , , 这层材料附着于载体表面这层材料附着于载体表面这层材料附着于载体表面这层材料附着于载体表面, , , , 随着载体作高速旋转或直线随着载体作高速旋转或直线随着载体作高速旋转或直线随着载体作高速旋转或直线运动运动运动运动, , , , 在运动过程中用磁头进行读或写。在运动过程中用磁头进行读或写。在运动过程中用磁头进行读或写。在运动过程中用磁头进行读或写。外存信息的存取特点外存信息的存取特点外存信息的存取特点外存信息的存取特点, , , , 决定了外部排序的策略选择。决定了外部排序的策略选择。决定了外部排序的策略选择。决定了外部排序的策略选择。11- 中国科大数据结构11.1 外
4、存信息的存取pp磁带信息的存取磁带信息的存取磁带信息的存取磁带信息的存取磁带存储器的工作原理和磁带录音机一样磁带存储器的工作原理和磁带录音机一样磁带存储器的工作原理和磁带录音机一样磁带存储器的工作原理和磁带录音机一样, , , , 不同之处在于它存不同之处在于它存不同之处在于它存不同之处在于它存储的是数字信息而不是模拟信息。储的是数字信息而不是模拟信息。储的是数字信息而不是模拟信息。储的是数字信息而不是模拟信息。磁带上的信息在横向分布、纵向分布以及首尾标志等都一定的磁带上的信息在横向分布、纵向分布以及首尾标志等都一定的磁带上的信息在横向分布、纵向分布以及首尾标志等都一定的磁带上的信息在横向分布
5、、纵向分布以及首尾标志等都一定的格式。格式。格式。格式。n n以以以以1/21/21/21/2英寸九道的磁带为例英寸九道的磁带为例英寸九道的磁带为例英寸九道的磁带为例, , , , 每一横排就可表示一个字符（每一横排就可表示一个字符（每一横排就可表示一个字符（每一横排就可表示一个字符（8 8 8 8位位位位+1+1+1+1个校验位）。个校验位）。个校验位）。个校验位）。n n纵向按区进行存储纵向按区进行存储纵向按区进行存储纵向按区进行存储, , , , 区的长度不固定区的长度不固定区的长度不固定区的长度不固定, , , , 但有一个范围但有一个范围但有一个范围但有一个范围, , , , 例如例
6、如例如例如2 2 2 2到到到到4096409640964096字节字节字节字节, , , , 相邻区之间有一定长度的间隔（相邻区之间有一定长度的间隔（相邻区之间有一定长度的间隔（相邻区之间有一定长度的间隔（IBG, Inter Block IBG, Inter Block IBG, Inter Block IBG, Inter Block GapGapGapGap）, , , , 作为磁带起停之用。作为磁带起停之用。作为磁带起停之用。作为磁带起停之用。记录记录 1记录记录 3记录记录 211- 中国科大数据结构11.1 外存信息的存取pp在磁带上读写一块信息所需的时间由两部分组成：在磁带上读
7、写一块信息所需的时间由两部分组成：在磁带上读写一块信息所需的时间由两部分组成：在磁带上读写一块信息所需的时间由两部分组成：T T T TI/OI/OI/OI/O = t = t = t = ta a a a + + + + n n n n t t t tw w w wn nt t t ta a a a为延迟时间为延迟时间为延迟时间为延迟时间, , , , 即读即读即读即读/ / / /写头到达传输信息所在物理快起始位置所写头到达传输信息所在物理快起始位置所写头到达传输信息所在物理快起始位置所写头到达传输信息所在物理快起始位置所需时间；需时间；需时间；需时间；n nt t t tw w w w为
8、传输一个字符的时间。为传输一个字符的时间。为传输一个字符的时间。为传输一个字符的时间。显然显然显然显然, , , , 延迟时间和信息在磁带上的位置、当前读延迟时间和信息在磁带上的位置、当前读延迟时间和信息在磁带上的位置、当前读延迟时间和信息在磁带上的位置、当前读/ / / /写头所在的写头所在的写头所在的写头所在的位置有关。位置有关。位置有关。位置有关。所以磁带便宜、可反复使用、是一种顺序存取设备所以磁带便宜、可反复使用、是一种顺序存取设备所以磁带便宜、可反复使用、是一种顺序存取设备所以磁带便宜、可反复使用、是一种顺序存取设备, , , , 但查找费但查找费但查找费但查找费时、速度慢（尤其是查
9、找末端记录时）。时、速度慢（尤其是查找末端记录时）。时、速度慢（尤其是查找末端记录时）。时、速度慢（尤其是查找末端记录时）。11- 中国科大数据结构11.1 外存信息的存取pp磁盘信息的存取磁盘信息的存取磁盘信息的存取磁盘信息的存取磁盘是一种直接存取的存储设备磁盘是一种直接存取的存储设备磁盘是一种直接存取的存储设备磁盘是一种直接存取的存储设备(DASD(DASD(DASD(DASD）。）。）。）。pp页块的读写时间：页块的读写时间：页块的读写时间：页块的读写时间：T TI/OI/O = t = tseekseek + t + tlatencylatency + + n n t twmwmn n
10、t tseekseek：寻道时间：寻道时间：寻道时间：寻道时间n nt tlatencylatency：等待时间：等待时间：等待时间：等待时间n nt twmwm：传输时间：传输时间：传输时间：传输时间11- 中国科大数据结构11.2 外部排序的方法pp外部排序基本上由两个相对独立的阶段组成：外部排序基本上由两个相对独立的阶段组成：外部排序基本上由两个相对独立的阶段组成：外部排序基本上由两个相对独立的阶段组成：n n首先首先首先首先, , , , 按可用内存大小按可用内存大小按可用内存大小按可用内存大小, , , , 将外存上含将外存上含将外存上含将外存上含n n n n个记录的文件分成若干长
11、个记录的文件分成若干长个记录的文件分成若干长个记录的文件分成若干长度为度为度为度为l l l l的子文件或段的子文件或段的子文件或段的子文件或段(segment), (segment), (segment), (segment), 依次读入内存并利用有效的内依次读入内存并利用有效的内依次读入内存并利用有效的内依次读入内存并利用有效的内部排序方法对它们进行排序部排序方法对它们进行排序部排序方法对它们进行排序部排序方法对它们进行排序, , , , 并将排序后得到的有序子文件重并将排序后得到的有序子文件重并将排序后得到的有序子文件重并将排序后得到的有序子文件重新写入外存新写入外存新写入外存新写入外存
12、, , , , 通常称这些有序子文件为归并段或顺串通常称这些有序子文件为归并段或顺串通常称这些有序子文件为归并段或顺串通常称这些有序子文件为归并段或顺串(run)(run)(run)(run)；n n然后然后然后然后, , , , 对这些归并段进行逐躺归并对这些归并段进行逐躺归并对这些归并段进行逐躺归并对这些归并段进行逐躺归并, , , , 使归并段（有序的子文件）使归并段（有序的子文件）使归并段（有序的子文件）使归并段（有序的子文件）逐渐由小至大逐渐由小至大逐渐由小至大逐渐由小至大, , , , 直到得到整个有序文件为止。直到得到整个有序文件为止。直到得到整个有序文件为止。直到得到整个有序文
13、件为止。11- 中国科大数据结构11.2 外部排序的方法pp例：一文件含例：一文件含例：一文件含例：一文件含1000010000记录记录记录记录, , 通过通过通过通过1010次内部排序得到次内部排序得到次内部排序得到次内部排序得到1010个初始归并段个初始归并段个初始归并段个初始归并段R1R10, R1R10, 其中每一段都含有其中每一段都含有其中每一段都含有其中每一段都含有10001000个记录。个记录。个记录。个记录。然后作两两归并：然后作两两归并：然后作两两归并：然后作两两归并：R1 R2R1 R2 R3 R4R3 R4 R5 R6R5 R6 R7 R8R7 R8 R9 R10R9 R
14、10 R1 R2R1 R2 R3 R4R3 R4 R5 R5 R1 R2R1 R2 R3 R3 R1 R2R1 R2 有序文件有序文件有序文件有序文件pp由由由由1010个初始归并段到一个有序文件个初始归并段到一个有序文件个初始归并段到一个有序文件个初始归并段到一个有序文件, , 共进行了共进行了共进行了共进行了4 4趟归并趟归并趟归并趟归并, , 每一趟都从每一趟都从每一趟都从每一趟都从mm个归并段得到个归并段得到个归并段得到个归并段得到ceil(m/2)ceil(m/2)个归并段。这种归并方法称为个归并段。这种归并方法称为个归并段。这种归并方法称为个归并段。这种归并方法称为2-2-路平衡归
15、路平衡归路平衡归路平衡归并并并并。11- 中国科大数据结构11.2 外部排序的方法pp外存上信息的读外存上信息的读外存上信息的读外存上信息的读/ / / /写是以写是以写是以写是以“物理块物理块物理块物理块”为单位进行的为单位进行的为单位进行的为单位进行的, , , , 假设每个物理假设每个物理假设每个物理假设每个物理块可以容纳块可以容纳块可以容纳块可以容纳200200200200个记录个记录个记录个记录, , , , 则每一趟归并需进行则每一趟归并需进行则每一趟归并需进行则每一趟归并需进行50505050次次次次“读读读读”和和和和50505050次次次次“写写写写”, 4”, 4”, 4”
16、, 4趟归并加上内部排序时所需进行的读趟归并加上内部排序时所需进行的读趟归并加上内部排序时所需进行的读趟归并加上内部排序时所需进行的读/ / / /写使得在外排序中总写使得在外排序中总写使得在外排序中总写使得在外排序中总共需进行共需进行共需进行共需进行500500500500次读次读次读次读/ / / /写。写。写。写。11- 中国科大数据结构11.2 外部排序的方法pp外部排序所需总的时间外部排序所需总的时间外部排序所需总的时间外部排序所需总的时间 = = = = 内部排序（产生初始归并段）所需的时间内部排序（产生初始归并段）所需的时间内部排序（产生初始归并段）所需的时间内部排序（产生初始归
17、并段）所需的时间( (m m t tISIS) ) + + + + 外存信息读写的时间外存信息读写的时间外存信息读写的时间外存信息读写的时间( (d d t tIOIO) ) + + + +内部归并所需的时间内部归并所需的时间内部归并所需的时间内部归并所需的时间( (s s ututmgmg) )pp其中：其中：其中：其中： t t t tIS IS IS IS 是为得到一个初始归并段进行内部排序所需时间的均值；是为得到一个初始归并段进行内部排序所需时间的均值；是为得到一个初始归并段进行内部排序所需时间的均值；是为得到一个初始归并段进行内部排序所需时间的均值； t t t tIO IO IO
18、IO 是进行一次外存读是进行一次外存读是进行一次外存读是进行一次外存读/ / / /写时间的均值；写时间的均值；写时间的均值；写时间的均值； ututututmg mg mg mg 是对是对是对是对u u u u个记录进行内部归并所需时间；个记录进行内部归并所需时间；个记录进行内部归并所需时间；个记录进行内部归并所需时间； m m m m 为经过内部排序之后得到的初始归并段的个数；为经过内部排序之后得到的初始归并段的个数；为经过内部排序之后得到的初始归并段的个数；为经过内部排序之后得到的初始归并段的个数； s s s s 为归并的趟数；为归并的趟数；为归并的趟数；为归并的趟数； d d d d
19、 为总的读为总的读为总的读为总的读/ / / /写次数。写次数。写次数。写次数。pp于是上例进行外排序所需总的时间为：于是上例进行外排序所需总的时间为：于是上例进行外排序所需总的时间为：于是上例进行外排序所需总的时间为：10 10 t tIS IS + 500 + 500 t tIOIO + 4x10000 + 4x10000 t tmgmg显然显然显然显然t t t tIOIOIOIO较较较较t t t tmgmgmgmg要大的多要大的多要大的多要大的多, , , , 因此提高外排序的效率应主要着眼于减少外存因此提高外排序的效率应主要着眼于减少外存因此提高外排序的效率应主要着眼于减少外存因此
20、提高外排序的效率应主要着眼于减少外存信息读写的次数信息读写的次数信息读写的次数信息读写的次数d d d d。11- 中国科大数据结构11.2 外部排序的方法ppd d d d和和和和“归并过程归并过程归并过程归并过程”的关系：的关系：的关系：的关系：若对上例进行若对上例进行若对上例进行若对上例进行5 5 5 5路平衡归并：路平衡归并：路平衡归并：路平衡归并： R1 R2 R3 R4 R5R1 R2 R3 R4 R5R1 R2 R3 R4 R5R1 R2 R3 R4 R5 R6 R7 R8 R9 R10R6 R7 R8 R9 R10R6 R7 R8 R9 R10R6 R7 R8 R9 R10 R
21、1 R2R1 R2R1 R2R1 R2 有序文件有序文件有序文件有序文件仅需两趟归并仅需两趟归并仅需两趟归并仅需两趟归并, , , , 总的读总的读总的读总的读/ / / /写次数便减少为：写次数便减少为：写次数便减少为：写次数便减少为：2x100+100=300, 2x100+100=300, 2x100+100=300, 2x100+100=300, 比比比比2 2 2 2路归路归路归路归并减少了并减少了并减少了并减少了200200200200次的读次的读次的读次的读/ / / /写。对同一文件写。对同一文件写。对同一文件写。对同一文件, , , , 进行外排序时所需读进行外排序时所需读进
22、行外排序时所需读进行外排序时所需读/ / / /写外存写外存写外存写外存的次数和归并的趟数的次数和归并的趟数的次数和归并的趟数的次数和归并的趟数s s s s成正比。一般情况下成正比。一般情况下成正比。一般情况下成正比。一般情况下, , , , 对对对对m m m m个初始归并段进行个初始归并段进行个初始归并段进行个初始归并段进行k k k k路平衡归并时路平衡归并时路平衡归并时路平衡归并时, , , , 归并的趟数归并的趟数归并的趟数归并的趟数s=floor(logs=floor(logs=floor(logs=floor(logk k k km m m m).).).).可见：若能增加可见
23、：若能增加可见：若能增加可见：若能增加k k k k或减少或减少或减少或减少m m m m便能减少便能减少便能减少便能减少s, s, s, s, 因此减少因此减少因此减少因此减少d.d.d.d.11- 中国科大数据结构11.3 多路平衡归并的实现pp对于对于对于对于2 2 2 2路归并路归并路归并路归并, , , , 令两个归并段上有令两个归并段上有令两个归并段上有令两个归并段上有u u u u个记录个记录个记录个记录, , , , 每得到归并后的一个记每得到归并后的一个记每得到归并后的一个记每得到归并后的一个记录录录录, , , , 仅需一次比较即可仅需一次比较即可仅需一次比较即可仅需一次比
24、较即可, , , , 因此得到含因此得到含因此得到含因此得到含u u u u个记录的归并段需进行个记录的归并段需进行个记录的归并段需进行个记录的归并段需进行u-1u-1u-1u-1次次次次比较。比较。比较。比较。pp对于对于对于对于k k k k路归并路归并路归并路归并, , , , 令令令令u u u u个记录分布在个记录分布在个记录分布在个记录分布在k k k k个归并段上个归并段上个归并段上个归并段上, , , , 显然显然显然显然, , , , 归并后的第归并后的第归并后的第归并后的第一个记录应是一个记录应是一个记录应是一个记录应是k k k k个归并段中关键字最小的记录个归并段中关键
25、字最小的记录个归并段中关键字最小的记录个归并段中关键字最小的记录, , , , 这需要进行这需要进行这需要进行这需要进行k-1k-1k-1k-1次比次比次比次比较较较较, , , , 得到得到得到得到u u u u个记录的归并段个记录的归并段个记录的归并段个记录的归并段, , , , 共需共需共需共需(u-1)(k-1)(u-1)(k-1)次比较。由此次比较。由此次比较。由此次比较。由此, , , , 对对对对n n n n个记个记个记个记录的文件进行外排序时录的文件进行外排序时录的文件进行外排序时录的文件进行外排序时, , , , 在内部归并过程中进行的总的比较次数为在内部归并过程中进行的总
26、的比较次数为在内部归并过程中进行的总的比较次数为在内部归并过程中进行的总的比较次数为s(k-1)(n-1)s(k-1)(n-1)。假设所得初始归并段为。假设所得初始归并段为。假设所得初始归并段为。假设所得初始归并段为m m m m个个个个, , , , 则归并过程中进行比较的则归并过程中进行比较的则归并过程中进行比较的则归并过程中进行比较的总的时间为：总的时间为：总的时间为：总的时间为：floor(logfloor(logk kmm)(k-1)(n-1)t)(k-1)(n-1)tmgmg = floor(log = floor(log2 2mm/log/log2 2k k)(k-1)(n-1)
27、t)(k-1)(n-1)tmgmgpp由于由于由于由于(k-1)/log2k (k-1)/log2k 随随随随 k k k k 的增长而增长的增长而增长的增长而增长的增长而增长, , , , 这将抵消由于增大这将抵消由于增大这将抵消由于增大这将抵消由于增大k k k k而减少外而减少外而减少外而减少外存信息读写时间所得效益。存信息读写时间所得效益。存信息读写时间所得效益。存信息读写时间所得效益。11- 中国科大数据结构11.3 多路平衡归并的实现pp在进行在进行在进行在进行k k k k路归并时利用路归并时利用路归并时利用路归并时利用“败者树败者树败者树败者树(Tree of Loser)(T
28、ree of Loser)”, ”, ”, ”, 则可使在则可使在则可使在则可使在k k k k个记录个记录个记录个记录中选出关键字最小的记录时仅需进行中选出关键字最小的记录时仅需进行中选出关键字最小的记录时仅需进行中选出关键字最小的记录时仅需进行floor(log2k)floor(log2k)次比较次比较次比较次比较, , , , 从而使从而使从而使从而使总的归并时间变为：总的归并时间变为：总的归并时间变为：总的归并时间变为：floor(logfloor(log2 2m)(n-1)tm)(n-1)tmgmg与与与与k k k k无关无关无关无关, , , , 不再随不再随不再随不再随k k
29、k k的增长而增长。的增长而增长。的增长而增长。的增长而增长。11- 中国科大数据结构11.3 多路平衡归并的实现pp胜者树及其使用胜者树及其使用胜者树及其使用胜者树及其使用胜者进入下一轮胜者进入下一轮胜者进入下一轮胜者进入下一轮, , , , 直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决出冠军之后, , , , 充分充分充分充分利用上一次比赛的结果利用上一次比赛的结果利用上一次比赛的结果利用上一次比赛的结果, , , , 使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名使得
30、更快地挑出亚军、第三名 。729597654挑出冠军挑出冠军需要进行需要进行 k-1 次次比较比较, 此处需要此处需要比较比较 3 次。次。955320517654321055957299511- 中国科大数据结构11.3 多路平衡归并的实现pp胜者树及其使用胜者树及其使用胜者树及其使用胜者树及其使用胜者进入下一轮胜者进入下一轮胜者进入下一轮胜者进入下一轮, , , , 直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决出冠军之后, , , , 充分充分充分充分利用上一次比赛的结果利用上一次比赛的结果利用上一次
31、比赛的结果利用上一次比赛的结果, , , , 使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名 。7291697654挑出亚军挑出亚军需要进行需要进行 log2k 次比较次比较, 此处需此处需要比较要比较 2次。次。9773207176543210779167299711- 中国科大数据结构11.3 多路平衡归并的实现pp胜者树及其使用胜者树及其使用胜者树及其使用胜者树及其使用 胜者进入下一轮胜者进入下一轮胜者进入下一轮胜者进入下一轮, , 直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决
32、出冠军之后直至决出本次比赛的冠军。决出冠军之后, , 充分充分充分充分利用上一次比赛的结果利用上一次比赛的结果利用上一次比赛的结果利用上一次比赛的结果, , 使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名 。 决出第一名需比较：决出第一名需比较：决出第一名需比较：决出第一名需比较： k - 1 k - 1 次次次次 决出第二名需比较：决出第二名需比较：决出第二名需比较：决出第二名需比较： log log2 2k k 次次次次 决出第三名需比较：决出第三名需比较：决出第三名需比较：决出第三名需比较： log log2 2k k 次次次次
33、结果：采用胜者树后结果：采用胜者树后结果：采用胜者树后结果：采用胜者树后, , 从从从从 k k 个元素中挑选一个最小的元素仅需个元素中挑选一个最小的元素仅需个元素中挑选一个最小的元素仅需个元素中挑选一个最小的元素仅需 loglog2 2k k 次比较次比较次比较次比较, , 这时总的比较次数下降为：这时总的比较次数下降为：这时总的比较次数下降为：这时总的比较次数下降为：loglogk km logm log2 2k ( n - 1 ) tk ( n - 1 ) tmgmg log log2 2m ( n - 1 ) tm ( n - 1 ) tmgmg 该结果和该结果和该结果和该结果和 k
34、k 无关无关无关无关, , 这是通过多用空间换来的。这是通过多用空间换来的。这是通过多用空间换来的。这是通过多用空间换来的。pp改进：采用胜者树改进：采用胜者树改进：采用胜者树改进：采用胜者树, k, k个元素中最小的元素输出之后个元素中最小的元素输出之后个元素中最小的元素输出之后个元素中最小的元素输出之后, , 从根结点到它从根结点到它从根结点到它从根结点到它的相应的叶子结点路径上的结点都需要进行修改的相应的叶子结点路径上的结点都需要进行修改的相应的叶子结点路径上的结点都需要进行修改的相应的叶子结点路径上的结点都需要进行修改, , 为了加快程序运为了加快程序运为了加快程序运为了加快程序运行的
35、速度产生了败者树。行的速度产生了败者树。行的速度产生了败者树。行的速度产生了败者树。11- 中国科大数据结构11.3 多路平衡归并的实现pp败者树败者树败者树败者树在父节点中记下刚进行完的比赛中的败者在父节点中记下刚进行完的比赛中的败者在父节点中记下刚进行完的比赛中的败者在父节点中记下刚进行完的比赛中的败者, , , , 但同样让胜者去参加下但同样让胜者去参加下但同样让胜者去参加下但同样让胜者去参加下一轮的竞赛一轮的竞赛一轮的竞赛一轮的竞赛, , , , 便得到一棵便得到一棵便得到一棵便得到一棵“败者树败者树败者树败者树”。11- 中国科大数据结构11.3 多路平衡归并的实现pp下图即为一棵实
36、现下图即为一棵实现下图即为一棵实现下图即为一棵实现5-5-5-5-路归并的败者树路归并的败者树路归并的败者树路归并的败者树ls04, ls04, ls04, ls04, 图中方形结点表示图中方形结点表示图中方形结点表示图中方形结点表示叶子结点叶子结点叶子结点叶子结点( ( ( (也可看成是外结点也可看成是外结点也可看成是外结点也可看成是外结点), ), ), ), 分别为分别为分别为分别为5 5 5 5个归并段中当前参加归并个归并段中当前参加归并个归并段中当前参加归并个归并段中当前参加归并的待选择记录的关键码；败者树中根结点的待选择记录的关键码；败者树中根结点的待选择记录的关键码；败者树中根结
37、点的待选择记录的关键码；败者树中根结点ls1ls1ls1ls1的双亲结点的双亲结点的双亲结点的双亲结点ls0ls0ls0ls0为为为为“冠军冠军冠军冠军”, ”, ”, ”, 在此指示各归并段中的最小关键码记录为第三段中的记在此指示各归并段中的最小关键码记录为第三段中的记在此指示各归并段中的最小关键码记录为第三段中的记在此指示各归并段中的最小关键码记录为第三段中的记录；结点录；结点录；结点录；结点ls3ls3ls3ls3指示指示指示指示b1b1b1b1和和和和b2b2b2b2两个叶子结点中的败者即是两个叶子结点中的败者即是两个叶子结点中的败者即是两个叶子结点中的败者即是b2, b2, b2,
38、b2, 而胜者而胜者而胜者而胜者b1b1b1b1和和和和b3(b3b3(b3b3(b3b3(b3是叶子结点是叶子结点是叶子结点是叶子结点b3b3b3b3、b4b4b4b4和和和和b0b0b0b0经过两场比赛后选出的获胜者经过两场比赛后选出的获胜者经过两场比赛后选出的获胜者经过两场比赛后选出的获胜者) ) ) )进进进进行比较行比较行比较行比较, , , , 结点结点结点结点ls1ls1ls1ls1则指示它们中的败者为则指示它们中的败者为则指示它们中的败者为则指示它们中的败者为b1b1b1b1。11- 中国科大数据结构11.3 多路平衡归并的实现pp5-5-路归并的败者树例路归并的败者树例路归并
39、的败者树例路归并的败者树例920ls0ls1ls3ls2ls4b0b1b2b4b36152512374810151591820202240213061210411- 中国科大数据结构11.3 多路平衡归并的实现pp在选得最小关键码的记录之后在选得最小关键码的记录之后在选得最小关键码的记录之后在选得最小关键码的记录之后, , , , 只要修改叶子结点只要修改叶子结点只要修改叶子结点只要修改叶子结点b3b3b3b3中的值中的值中的值中的值, , , , 使其使其使其使其为同一归并段中的下一个记录的关键码为同一归并段中的下一个记录的关键码为同一归并段中的下一个记录的关键码为同一归并段中的下一个记录的
40、关键码, , , , 然后从该结点向上和双亲然后从该结点向上和双亲然后从该结点向上和双亲然后从该结点向上和双亲结点所指的关键码进行比较结点所指的关键码进行比较结点所指的关键码进行比较结点所指的关键码进行比较, , , , 败者留在该双亲败者留在该双亲败者留在该双亲败者留在该双亲, , , , 胜者继续向上直至胜者继续向上直至胜者继续向上直至胜者继续向上直至树根的双亲。如下图所示。当第树根的双亲。如下图所示。当第树根的双亲。如下图所示。当第树根的双亲。如下图所示。当第3 3 3 3个归并段中第个归并段中第个归并段中第个归并段中第2 2 2 2个记录参加归并时个记录参加归并时个记录参加归并时个记录
41、参加归并时, , , , 选得最小关键码记录为第一个归并段中的记录。为了防止在归并过选得最小关键码记录为第一个归并段中的记录。为了防止在归并过选得最小关键码记录为第一个归并段中的记录。为了防止在归并过选得最小关键码记录为第一个归并段中的记录。为了防止在归并过程中某个归并段变为空程中某个归并段变为空程中某个归并段变为空程中某个归并段变为空, , , , 可以在每个归并段中附加一个关键码为最可以在每个归并段中附加一个关键码为最可以在每个归并段中附加一个关键码为最可以在每个归并段中附加一个关键码为最大的记录。当选出的大的记录。当选出的大的记录。当选出的大的记录。当选出的“冠军冠军冠军冠军”记录的关键
42、码为最大值时记录的关键码为最大值时记录的关键码为最大值时记录的关键码为最大值时, , , , 表明此次表明此次表明此次表明此次归并已完成。归并已完成。归并已完成。归并已完成。11- 中国科大数据结构11.3 多路平衡归并的实现pp5-5-路归并的败者树例路归并的败者树例路归并的败者树例路归并的败者树例920ls0ls1ls3ls2ls4b0b1b2b4b31525123748101515918202022402014151210311- 中国科大数据结构11.3 多路平衡归并的实现pp实现实现实现实现k-k-路归并的败者树的初始化也容易实现路归并的败者树的初始化也容易实现路归并的败者树的初始化
43、也容易实现路归并的败者树的初始化也容易实现, , 只要先令所有的非终只要先令所有的非终只要先令所有的非终只要先令所有的非终端结点指向一个含最小关键码的叶子结点端结点指向一个含最小关键码的叶子结点端结点指向一个含最小关键码的叶子结点端结点指向一个含最小关键码的叶子结点, , 然后从各叶子结点出发然后从各叶子结点出发然后从各叶子结点出发然后从各叶子结点出发调整非终端结点为新的败者即可。调整非终端结点为新的败者即可。调整非终端结点为新的败者即可。调整非终端结点为新的败者即可。pp下面程序中简单描述了利用败者树进行下面程序中简单描述了利用败者树进行下面程序中简单描述了利用败者树进行下面程序中简单描述了
44、利用败者树进行k-k-路归并的过程路归并的过程路归并的过程路归并的过程, , 为了突出为了突出为了突出为了突出如何利用败者树进行归并如何利用败者树进行归并如何利用败者树进行归并如何利用败者树进行归并, , 避开了外存信息存取的细节避开了外存信息存取的细节避开了外存信息存取的细节避开了外存信息存取的细节, , 可以认为可以认为可以认为可以认为归并段已存在。归并段已存在。归并段已存在。归并段已存在。typedef int LoserTreek; /败者树是完全二叉树且不含叶子败者树是完全二叉树且不含叶子, 可采用顺序存储结构可采用顺序存储结构typedef structKeyType key;Ex
45、Node, Externalk; /外结点外结点, 只存放待归并记录的关键码只存放待归并记录的关键码11- 中国科大数据结构11.3 多路平衡归并的实现void K_Merge(LoserTree *ls, External *b)void K_Merge(LoserTree *ls, External *b) / /k-/k-路归并处理程序利用败者树路归并处理程序利用败者树路归并处理程序利用败者树路归并处理程序利用败者树lsls将编号从将编号从将编号从将编号从0 0到到到到k-1k-1的的的的k k个输入归并段中的记录归并到输出归并段个输入归并段中的记录归并到输出归并段个输入归并段中的记录归
46、并到输出归并段个输入归并段中的记录归并到输出归并段b0b0/ /到到到到bk-1bk-1为败者树上的为败者树上的为败者树上的为败者树上的k k个叶子结点个叶子结点个叶子结点个叶子结点, , 分别存放分别存放分别存放分别存放k k个输入归并段中当前记录的关键码个输入归并段中当前记录的关键码个输入归并段中当前记录的关键码个输入归并段中当前记录的关键码for(i=0;ik;i+) input(bi.key);for(i=0;i0) while(t0) if(bs.keyblst.key) if(bs.keyblst.key) slst; slst; /s/s指示新的胜者指示新的胜者指示新的胜者指示新
47、的胜者 t=t/2; t=t/2; ls0=s; ls0=s; void CreateLoserTree(LoserTree *ls)void CreateLoserTree(LoserTree *ls)/ /建立败者树建立败者树建立败者树建立败者树/ /已知已知已知已知b0b0到到到到bk-1bk-1为完全二叉树为完全二叉树为完全二叉树为完全二叉树lsls的叶子结点存有的叶子结点存有的叶子结点存有的叶子结点存有k k个关个关个关个关/ /键码键码键码键码, ,沿从叶子到根的沿从叶子到根的沿从叶子到根的沿从叶子到根的k k条路径将条路径将条路径将条路径将lsls调整为败者树调整为败者树调整为败
48、者树调整为败者树 bk.key=MINKEY; bk.key=MINKEY; / /设设设设MINKEYMINKEY为关键码可能的最小为关键码可能的最小为关键码可能的最小为关键码可能的最小值值值值 for(i=0;ik;i+) for(i=0;i0;i-) Adjust(ls, i); for(i=k-1;k0;i-) Adjust(ls, i); / /依次从依次从依次从依次从bk-1, bk-2, , b0bk-1, bk-2, , b0出发调整败者出发调整败者出发调整败者出发调整败者 最后要提及一点最后要提及一点最后要提及一点最后要提及一点, k, k值的选择并非越大越好值的选择并非越大
49、越好值的选择并非越大越好值的选择并非越大越好, , 如何选择合适的如何选择合适的如何选择合适的如何选择合适的k k是一个是一个是一个是一个需要综合考虑的问题。需要综合考虑的问题。需要综合考虑的问题。需要综合考虑的问题。11- 中国科大数据结构11.4 置换-选择排序pp归并的趟数不仅和归并的趟数不仅和归并的趟数不仅和归并的趟数不仅和k k k k成反比成反比成反比成反比, , , , 也和也和也和也和m m m m成正比成正比成正比成正比, , , , 因此减少因此减少因此减少因此减少m m m m是减少是减少是减少是减少s s s s的另的另的另的另一条途径。这里一条途径。这里一条途径。这里
50、一条途径。这里m m m m是外部文件经过内部排序之后得到的初始归并段是外部文件经过内部排序之后得到的初始归并段是外部文件经过内部排序之后得到的初始归并段是外部文件经过内部排序之后得到的初始归并段的个数的个数的个数的个数, m=ceil(n/l), m=ceil(n/l), m=ceil(n/l), m=ceil(n/l)。若要减少若要减少若要减少若要减少m, m, m, m, 就需要增加就需要增加就需要增加就需要增加l, l, l, l, 但是内存的容量有限但是内存的容量有限但是内存的容量有限但是内存的容量有限, , , , 利用上一章利用上一章利用上一章利用上一章内排序的方法无法做到内排序
51、的方法无法做到内排序的方法无法做到内排序的方法无法做到, , , , 所以必须探索新的排序方法。所以必须探索新的排序方法。所以必须探索新的排序方法。所以必须探索新的排序方法。pp置换置换置换置换- -选择排序选择排序选择排序选择排序(Replacement-Selection Sorting)(Replacement-Selection Sorting)是在树形选择排是在树形选择排是在树形选择排是在树形选择排序的基础上得来的序的基础上得来的序的基础上得来的序的基础上得来的, , 它的特点是：在整个排序（得到所有初始归并它的特点是：在整个排序（得到所有初始归并它的特点是：在整个排序（得到所有初始
52、归并它的特点是：在整个排序（得到所有初始归并段）的过程中段）的过程中段）的过程中段）的过程中, , 选择最小（或最大）关键字和输入、输出交叉或平选择最小（或最大）关键字和输入、输出交叉或平选择最小（或最大）关键字和输入、输出交叉或平选择最小（或最大）关键字和输入、输出交叉或平行进行。行进行。行进行。行进行。11- 中国科大数据结构11.4 置换-选择排序pp假设初始待排文件为输入文件假设初始待排文件为输入文件假设初始待排文件为输入文件假设初始待排文件为输入文件FI, FI, FI, FI, 初始归并段文件为输出文件初始归并段文件为输出文件初始归并段文件为输出文件初始归并段文件为输出文件FO,
53、FO, FO, FO, 内存工作区为内存工作区为内存工作区为内存工作区为WA, FOWA, FOWA, FOWA, FO和和和和WAWAWAWA的初始状态为空的初始状态为空的初始状态为空的初始状态为空, , , , 并设内存工作区并设内存工作区并设内存工作区并设内存工作区WAWAWAWA的容量为的容量为的容量为的容量为w w w w个记录个记录个记录个记录, , , , 则置换则置换则置换则置换- - - -选择排序的操作过程为：选择排序的操作过程为：选择排序的操作过程为：选择排序的操作过程为：1.1.1.1.从从从从FIFIFIFI输入输入输入输入w w w w个记录到工作区个记录到工作区个
54、记录到工作区个记录到工作区WA;WA;WA;WA;2.2.2.2.从从从从WAWAWAWA中选出其中关键字最小值的记录中选出其中关键字最小值的记录中选出其中关键字最小值的记录中选出其中关键字最小值的记录, , , , 记为记为记为记为MINIMAXMINIMAXMINIMAXMINIMAX记录；记录；记录；记录；3.3.3.3.将将将将MINIMAXMINIMAXMINIMAXMINIMAX记录输出到记录输出到记录输出到记录输出到FOFOFOFO中去；中去；中去；中去；4.4.4.4.若若若若FIFIFIFI不空不空不空不空, , , , 则从则从则从则从FIFIFIFI输入下一个记录到输入下
55、一个记录到输入下一个记录到输入下一个记录到WAWAWAWA中；中；中；中；5.5.5.5.从从从从WAWAWAWA中所有关键字比中所有关键字比中所有关键字比中所有关键字比MINIMAXMINIMAXMINIMAXMINIMAX记录的关键字大的记录中选出最记录的关键字大的记录中选出最记录的关键字大的记录中选出最记录的关键字大的记录中选出最小关键字记录小关键字记录小关键字记录小关键字记录, , , , 作为新的作为新的作为新的作为新的MINIMAXMINIMAXMINIMAXMINIMAX记录；记录；记录；记录；6.6.6.6.重复重复重复重复3-5, 3-5, 3-5, 3-5, 直至在直至在直
56、至在直至在WAWAWAWA中选不出新的中选不出新的中选不出新的中选不出新的MINIMAXMINIMAXMINIMAXMINIMAX记录为止记录为止记录为止记录为止, , , , 由此得由此得由此得由此得到一个初始归并段到一个初始归并段到一个初始归并段到一个初始归并段, , , , 输出一个归并段的结束标志到输出一个归并段的结束标志到输出一个归并段的结束标志到输出一个归并段的结束标志到FOFOFOFO中去；中去；中去；中去；7.7.7.7.重复重复重复重复2-6, 2-6, 2-6, 2-6, 直至直至直至直至WAWAWAWA为空为空为空为空, , , , 由此得到全部初始归并段。由此得到全部初
57、始归并段。由此得到全部初始归并段。由此得到全部初始归并段。11- 中国科大数据结构11.4 置换-选择排序pp例如：初始文件含例如：初始文件含例如：初始文件含例如：初始文件含24242424个记录个记录个记录个记录, , , , 关键字分别为：关键字分别为：关键字分别为：关键字分别为：51, 49, 39, 46, 38, 2951, 49, 39, 46, 38, 2951, 49, 39, 46, 38, 2951, 49, 39, 46, 38, 29, , , , 14, 61, 15, 30, 1, 4814, 61, 15, 30, 1, 4814, 61, 15, 30, 1,
58、4814, 61, 15, 30, 1, 48, , , , 52, 3, 52, 3, 52, 3, 52, 3, 63, 27, 4, 1363, 27, 4, 1363, 27, 4, 1363, 27, 4, 13, , , , 89, 24, 46, 58, 33, 7689, 24, 46, 58, 33, 7689, 24, 46, 58, 33, 7689, 24, 46, 58, 33, 76假设内存工作区可容纳假设内存工作区可容纳假设内存工作区可容纳假设内存工作区可容纳6 6 6 6个记录，则用内排序的方法可以得到个记录，则用内排序的方法可以得到个记录，则用内排序的方法可以
59、得到个记录，则用内排序的方法可以得到4 4 4 4个个个个初始段：初始段：初始段：初始段：n nRUN1: 29, 38, 39, 46, 49, 51RUN1: 29, 38, 39, 46, 49, 51RUN1: 29, 38, 39, 46, 49, 51RUN1: 29, 38, 39, 46, 49, 51n nRUN2: 1, 14, 15, 30, 48, 61RUN2: 1, 14, 15, 30, 48, 61RUN2: 1, 14, 15, 30, 48, 61RUN2: 1, 14, 15, 30, 48, 61n nRUN3: 3, 4, 13, 27, 52, 63
60、RUN3: 3, 4, 13, 27, 52, 63RUN3: 3, 4, 13, 27, 52, 63RUN3: 3, 4, 13, 27, 52, 63n nRUN3: 24, 33, 46, 58, 76, 89RUN3: 24, 33, 46, 58, 76, 89RUN3: 24, 33, 46, 58, 76, 89RUN3: 24, 33, 46, 58, 76, 89而用置换而用置换而用置换而用置换- - - -选择排序，则可求得如下选择排序，则可求得如下选择排序，则可求得如下选择排序，则可求得如下3 3 3 3个初始归并段：个初始归并段：个初始归并段：个初始归并段：n nRU
61、N1: 29, 38, 39, 46, 49, 51, 61RUN1: 29, 38, 39, 46, 49, 51, 61RUN1: 29, 38, 39, 46, 49, 51, 61RUN1: 29, 38, 39, 46, 49, 51, 61n nRUN2: 1, 3, 14, 15, 27, 30, 48, 52, 63, 89RUN2: 1, 3, 14, 15, 27, 30, 48, 52, 63, 89RUN2: 1, 3, 14, 15, 27, 30, 48, 52, 63, 89RUN2: 1, 3, 14, 15, 27, 30, 48, 52, 63, 89n n
62、RUN3: 4, 13, 24, 33, 46, 58, 76RUN3: 4, 13, 24, 33, 46, 58, 76RUN3: 4, 13, 24, 33, 46, 58, 76RUN3: 4, 13, 24, 33, 46, 58, 7611- 中国科大数据结构11.4 置换-选择排序pp置换置换置换置换- -选择排序的过程选择排序的过程选择排序的过程选择排序的过程 ( (见教材第见教材第见教材第见教材第300300页页页页) )：FOFOWAWAFIFI51, 49, 39, 46, 38, 29, 14, 61, 15, 30, 1, 48, 52, 3, 63, 27, 4,
63、51, 49, 39, 46, 38, 29, 14, 61, 15, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7613, 89, 24, 46, 58, 33, 7651, 49, 39, 46, 38, 51, 49, 39, 46, 38, 292914, 61, 15, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 14, 61, 15, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 767629295
64、1, 49, 39, 46, 51, 49, 39, 46, 3838, , 141461, 15, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7661, 15, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7629, 3829, 3851, 49, 51, 49, 3939, 46, , 46, 6161, 14, 1415, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7615, 30, 1, 48, 5
65、2, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7629, 38, 3929, 38, 3951, 49, 51, 49, 1515, , 4646, 61, 14, 61, 1430, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7630, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7629, 38, 39, 4629, 38, 39, 4651, 51, 4949, 15, 15, 30 30, 61, 14, 61, 141, 48, 52, 3
66、, 63, 27, 4, 13, 89, 24, 46, 58, 33, 761, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7629, 38, 39, 46, 4929, 38, 39, 46, 495151, , 1 1, 15, 30, 61, 14, 15, 30, 61, 1448, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7648, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7629, 38, 39, 46, 49, 5129, 38, 39, 4
67、6, 49, 514848, 1, 15, 30, , 1, 15, 30, 6161, 14, 1452, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7652, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7629, 38, 39, 46, 49, 51, 6129, 38, 39, 46, 49, 51, 6148, 1, 15, 30, 48, 1, 15, 30, 5252, 14, 143, 63, 27, 4, 13, 89, 24, 46, 58, 33, 763, 63, 27, 4, 13, 89, 24, 4
68、6, 58, 33, 7611- 中国科大数据结构11.4 置换-选择排序pp在在在在WAWAWAWA中选择中选择中选择中选择MINIMAXMINIMAXMINIMAXMINIMAX记录的过程需利用记录的过程需利用记录的过程需利用记录的过程需利用“败者树败者树败者树败者树”来实现。来实现。来实现。来实现。1.1.1.1.内存工作区中的记录作为败者树的外部节点，而败者树的根内存工作区中的记录作为败者树的外部节点，而败者树的根内存工作区中的记录作为败者树的外部节点，而败者树的根内存工作区中的记录作为败者树的外部节点，而败者树的根节点的父节点指示工作区中关键字最小的纪录；节点的父节点指示工作区中关键
69、字最小的纪录；节点的父节点指示工作区中关键字最小的纪录；节点的父节点指示工作区中关键字最小的纪录；2.2.2.2.为了便于选出为了便于选出为了便于选出为了便于选出MINIMAXMINIMAXMINIMAXMINIMAX记录，为每一个记录附设一个所在归并记录，为每一个记录附设一个所在归并记录，为每一个记录附设一个所在归并记录，为每一个记录附设一个所在归并段的序号，在进行关键字的比较时，现比较段号，段号小的段的序号，在进行关键字的比较时，现比较段号，段号小的段的序号，在进行关键字的比较时，现比较段号，段号小的段的序号，在进行关键字的比较时，现比较段号，段号小的为胜者，段号相同的则关键字小的为胜者；
70、为胜者，段号相同的则关键字小的为胜者；为胜者，段号相同的则关键字小的为胜者；为胜者，段号相同的则关键字小的为胜者；3.3.3.3.败者树的建立可从设工作区中所有记录的段号均为败者树的建立可从设工作区中所有记录的段号均为败者树的建立可从设工作区中所有记录的段号均为败者树的建立可从设工作区中所有记录的段号均为“0”“0”“0”“0”开始，开始，开始，开始，然后从然后从然后从然后从FIFIFIFI逐个输入逐个输入逐个输入逐个输入w w w w个记录到工作区是，自下而上调整败者树，个记录到工作区是，自下而上调整败者树，个记录到工作区是，自下而上调整败者树，个记录到工作区是，自下而上调整败者树，由于这些
71、记录的段号为由于这些记录的段号为由于这些记录的段号为由于这些记录的段号为“1”“1”“1”“1”，则他们对于，则他们对于，则他们对于，则他们对于“0”“0”“0”“0”段的记录而段的记录而段的记录而段的记录而言均为败者，从而逐个填充到败者树的各节点中去。言均为败者，从而逐个填充到败者树的各节点中去。言均为败者，从而逐个填充到败者树的各节点中去。言均为败者，从而逐个填充到败者树的各节点中去。11- 中国科大数据结构11.4 置换-选择排序pp可以证明可以证明可以证明可以证明, , 利用置换利用置换利用置换利用置换- -选择排序，初始归并段的平均长度可达内存选择排序，初始归并段的平均长度可达内存选
72、择排序，初始归并段的平均长度可达内存选择排序，初始归并段的平均长度可达内存允许尺寸允许尺寸允许尺寸允许尺寸ww的二倍。的二倍。的二倍。的二倍。最最小小值值 最最大大值值值递增值递增记录数记录数记录值分布按等概率记录值分布按等概率当当前前最最小小值值段段分分界界值值展开的环路均均 匀匀 下下 雪雪W积雪(内存容量)环路起、终点当前车位当前车位扫雪车在环形路上扫雪。将环路截断展开，扫雪车在环形路上扫雪。将环路截断展开，积雪截面为三角形如上图积雪截面为三角形如上图,其面积为其面积为W,则车走则车走一圈扫走的面积为一圈扫走的面积为2W.类比到置换类比到置换_选择排序选择排序如黄字所示。如黄字所示。11
73、- 中国科大数据结构11.5 最佳归并树pp由置换由置换由置换由置换- -选择生成所得的初始归并段，其各段长度不等。选择生成所得的初始归并段，其各段长度不等。选择生成所得的初始归并段，其各段长度不等。选择生成所得的初始归并段，其各段长度不等。pp假如由置换假如由置换假如由置换假如由置换- -选择得到选择得到选择得到选择得到9 9个初始归并段，其长度分别为：个初始归并段，其长度分别为：个初始归并段，其长度分别为：个初始归并段，其长度分别为：9, 30, 12, 9, 30, 12, 18, 3, 17, 2, 6, 2418, 3, 17, 2, 6, 24。作。作。作。作3-3-路平衡归并（如
74、下图），假设每个记录占路平衡归并（如下图），假设每个记录占路平衡归并（如下图），假设每个记录占路平衡归并（如下图），假设每个记录占一个物理块，则两趟归并所需对外存进行的读一个物理块，则两趟归并所需对外存进行的读一个物理块，则两趟归并所需对外存进行的读一个物理块，则两趟归并所需对外存进行的读/ /写次数为：写次数为：写次数为：写次数为：(9+30+12+18+3+17+2+6+24)x2x2=484(9+30+12+18+3+17+2+6+24)x2x2=4849301251183173826243212111- 中国科大数据结构11.5 最佳归并树pp考虑下图的归并过程，仅需对外存进行考虑下图
75、的归并过程，仅需对外存进行考虑下图的归并过程，仅需对外存进行考虑下图的归并过程，仅需对外存进行446446次读次读次读次读/ /写，这棵归并树为写，这棵归并树为写，这棵归并树为写，这棵归并树为最佳归并树最佳归并树最佳归并树最佳归并树(11+32+59+121)x2(11+32+59+121)x2，为所有归并策略中所需读，为所有归并策略中所需读，为所有归并策略中所需读，为所有归并策略中所需读/ /写次数写次数写次数写次数最小的方案。最小的方案。最小的方案。最小的方案。2361130917182459121123211- 中国科大数据结构11.5 最佳归并树pp存在有存在有存在有存在有m m m
76、m个叶节点的带权路径长度最短的个叶节点的带权路径长度最短的个叶节点的带权路径长度最短的个叶节点的带权路径长度最短的k k k k叉树，称为霍夫曼树叉树，称为霍夫曼树叉树，称为霍夫曼树叉树，称为霍夫曼树(Huffman)(Huffman)。pp对长度不等的对长度不等的对长度不等的对长度不等的m m m m个初始段，以其长度为权，构造一棵霍夫曼树作为个初始段，以其长度为权，构造一棵霍夫曼树作为个初始段，以其长度为权，构造一棵霍夫曼树作为个初始段，以其长度为权，构造一棵霍夫曼树作为归并树，便可使得在进行外部归并时所需对外存进行的读归并树，便可使得在进行外部归并时所需对外存进行的读归并树，便可使得在进
77、行外部归并时所需对外存进行的读归并树，便可使得在进行外部归并时所需对外存进行的读/ / / /写次数写次数写次数写次数达到最小。达到最小。达到最小。达到最小。235249171812479162011- 中国科大数据结构11.5 最佳归并树pp对对对对k-k-路归并而言，若路归并而言，若路归并而言，若路归并而言，若(m-1) MOD (k-1) = 0(m-1) MOD (k-1) = 0，则导出的霍夫曼树节点，则导出的霍夫曼树节点，则导出的霍夫曼树节点，则导出的霍夫曼树节点的度数刚好为的度数刚好为的度数刚好为的度数刚好为0 0或或或或k k，否则，可附加，否则，可附加，否则，可附加，否则，可
78、附加k - (m-1) MOD (k-1) 1k - (m-1) MOD (k-1) 1个虚段，即第一次归并为个虚段，即第一次归并为个虚段，即第一次归并为个虚段，即第一次归并为 (m-1) MOD (k-1) + 1 (m-1) MOD (k-1) + 1路归并。路归并。路归并。路归并。pp若按最佳归并树的归并方案进行磁盘归并排序，需在内存建立一张若按最佳归并树的归并方案进行磁盘归并排序，需在内存建立一张若按最佳归并树的归并方案进行磁盘归并排序，需在内存建立一张若按最佳归并树的归并方案进行磁盘归并排序，需在内存建立一张载有归并段的长度和它在磁盘上的物理位置的索引表。载有归并段的长度和它在磁盘上的物理位置的索引表。载有归并段的长度和它在磁盘上的物理位置的索引表。载有归并段的长度和它在磁盘上的物理位置的索引表。11- 中国科大数据结构习题pp本章习题参见教师网页：本章习题参见教师网页：本章习题参见教师网页：本章习题参见教师网页：http:/
