数据结构第十一章外部排序课件

《数据结构第十一章外部排序课件》由会员分享，可在线阅读，更多相关《数据结构第十一章外部排序课件（35页珍藏版）》请在装配图网上搜索。

1、 数据结构课程中国科学技术大学网络学院中国科学技术大学网络学院中国科学技术大学网络学院中国科学技术大学网络学院数据结构第十一章第十一章外部排序外部排序本章内容本章内容11.1 11.1 外存信息的存取外存信息的存取外存信息的存取外存信息的存取11.2 11.2 外部排序的方法外部排序的方法外部排序的方法外部排序的方法11.3 11.3 多路平衡归并的实现多路平衡归并的实现多路平衡归并的实现多路平衡归并的实现11.4 11.4 置换置换置换置换-选择排序选择排序选择排序选择排序11.5 11.5 最佳归并树最佳归并树最佳归并树最佳归并树11-中国科大数据结构11.1 外存信息的存取pp常用的外存

2、储器分类：常用的外存储器分类：常用的外存储器分类：常用的外存储器分类：n n顺序存取的设备（如磁带）；顺序存取的设备（如磁带）；顺序存取的设备（如磁带）；顺序存取的设备（如磁带）；n n随机存取的设备（如磁盘）。随机存取的设备（如磁盘）。随机存取的设备（如磁盘）。随机存取的设备（如磁盘）。常用的外存储器是磁表面存储器常用的外存储器是磁表面存储器常用的外存储器是磁表面存储器常用的外存储器是磁表面存储器,信息记录在一薄层磁性材料信息记录在一薄层磁性材料信息记录在一薄层磁性材料信息记录在一薄层磁性材料的表面上的表面上的表面上的表面上,这层材料附着于载体表面这层材料附着于载体表面这层材料附着于载体表面

3、这层材料附着于载体表面,随着载体作高速旋转或直线随着载体作高速旋转或直线随着载体作高速旋转或直线随着载体作高速旋转或直线运动运动运动运动,在运动过程中用磁头进行读或写。在运动过程中用磁头进行读或写。在运动过程中用磁头进行读或写。在运动过程中用磁头进行读或写。外存信息的存取特点外存信息的存取特点外存信息的存取特点外存信息的存取特点,决定了外部排序的策略选择。决定了外部排序的策略选择。决定了外部排序的策略选择。决定了外部排序的策略选择。11-中国科大数据结构11.1 外存信息的存取pp磁带信息的存取磁带信息的存取磁带信息的存取磁带信息的存取磁带存储器的工作原理和磁带录音机一样磁带存储器的工作原理和

4、磁带录音机一样磁带存储器的工作原理和磁带录音机一样磁带存储器的工作原理和磁带录音机一样,不同之处在于它存不同之处在于它存不同之处在于它存不同之处在于它存储的是数字信息而不是模拟信息。储的是数字信息而不是模拟信息。储的是数字信息而不是模拟信息。储的是数字信息而不是模拟信息。磁带上的信息在横向分布、纵向分布以及首尾标志等都一定的磁带上的信息在横向分布、纵向分布以及首尾标志等都一定的磁带上的信息在横向分布、纵向分布以及首尾标志等都一定的磁带上的信息在横向分布、纵向分布以及首尾标志等都一定的格式。格式。格式。格式。n n以以以以1/21/21/21/2英寸九道的磁带为例英寸九道的磁带为例英寸九道的磁带

5、为例英寸九道的磁带为例,每一横排就可表示一个字符（每一横排就可表示一个字符（每一横排就可表示一个字符（每一横排就可表示一个字符（8 8 8 8位位位位+1+1+1+1个校验位）。个校验位）。个校验位）。个校验位）。n n纵向按区进行存储纵向按区进行存储纵向按区进行存储纵向按区进行存储,区的长度不固定区的长度不固定区的长度不固定区的长度不固定,但有一个范围但有一个范围但有一个范围但有一个范围,例如例如例如例如2 2 2 2到到到到4096409640964096字节字节字节字节,相邻区之间有一定长度的间隔（相邻区之间有一定长度的间隔（相邻区之间有一定长度的间隔（相邻区之间有一定长度的间隔（IBG

6、,Inter Block IBG,Inter Block IBG,Inter Block IBG,Inter Block GapGapGapGap）,作为磁带起停之用。作为磁带起停之用。作为磁带起停之用。作为磁带起停之用。记录记录 1记录记录 3记录记录 211-中国科大数据结构11.1 外存信息的存取pp在磁带上读写一块信息所需的时间由两部分组成：在磁带上读写一块信息所需的时间由两部分组成：在磁带上读写一块信息所需的时间由两部分组成：在磁带上读写一块信息所需的时间由两部分组成：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

7、 nt t t ta a a a为延迟时间为延迟时间为延迟时间为延迟时间,即读即读即读即读/写头到达传输信息所在物理快起始位置所写头到达传输信息所在物理快起始位置所写头到达传输信息所在物理快起始位置所写头到达传输信息所在物理快起始位置所需时间；需时间；需时间；需时间；n nt t t tw w w w为传输一个字符的时间。为传输一个字符的时间。为传输一个字符的时间。为传输一个字符的时间。显然显然显然显然,延迟时间和信息在磁带上的位置、当前读延迟时间和信息在磁带上的位置、当前读延迟时间和信息在磁带上的位置、当前读延迟时间和信息在磁带上的位置、当前读/写头所在的写头所在的写头所在的写头所在的位置有

8、关。位置有关。位置有关。位置有关。所以磁带便宜、可反复使用、是一种顺序存取设备所以磁带便宜、可反复使用、是一种顺序存取设备所以磁带便宜、可反复使用、是一种顺序存取设备所以磁带便宜、可反复使用、是一种顺序存取设备,但查找费但查找费但查找费但查找费时、速度慢（尤其是查找末端记录时）。时、速度慢（尤其是查找末端记录时）。时、速度慢（尤其是查找末端记录时）。时、速度慢（尤其是查找末端记录时）。11-中国科大数据结构11.1 外存信息的存取pp磁盘信息的存取磁盘信息的存取磁盘信息的存取磁盘信息的存取磁盘是一种直接存取的存储设备磁盘是一种直接存取的存储设备磁盘是一种直接存取的存储设备磁盘是一种直接存取的存

9、储设备(DASD(DASD(DASD(DASD）。）。）。）。pp页块的读写时间：页块的读写时间：页块的读写时间：页块的读写时间：T TI/OI/O=t tseekseek+t tlatencylatency+n n t twmwmn nt tseekseek：寻道时间：寻道时间：寻道时间：寻道时间n nt tlatencylatency：等待时间：等待时间：等待时间：等待时间n nt twmwm：传输时间：传输时间：传输时间：传输时间11-中国科大数据结构11.2 外部排序的方法pp外部排序基本上由两个相对独立的阶段组成：外部排序基本上由两个相对独立的阶段组成：外部排序基本上由两个相对独立的

10、阶段组成：外部排序基本上由两个相对独立的阶段组成：n n首先首先首先首先,按可用内存大小按可用内存大小按可用内存大小按可用内存大小,将外存上含将外存上含将外存上含将外存上含n n n n个记录的文件分成若干长个记录的文件分成若干长个记录的文件分成若干长个记录的文件分成若干长度为度为度为度为l l l l的子文件或段的子文件或段的子文件或段的子文件或段(segment),(segment),(segment),(segment),依次读入内存并利用有效的内依次读入内存并利用有效的内依次读入内存并利用有效的内依次读入内存并利用有效的内部排序方法对它们进行排序部排序方法对它们进行排序部排序方法对它们

11、进行排序部排序方法对它们进行排序,并将排序后得到的有序子文件重并将排序后得到的有序子文件重并将排序后得到的有序子文件重并将排序后得到的有序子文件重新写入外存新写入外存新写入外存新写入外存,通常称这些有序子文件为归并段或顺串通常称这些有序子文件为归并段或顺串通常称这些有序子文件为归并段或顺串通常称这些有序子文件为归并段或顺串(run)(run)(run)(run)；n n然后然后然后然后,对这些归并段进行逐躺归并对这些归并段进行逐躺归并对这些归并段进行逐躺归并对这些归并段进行逐躺归并,使归并段（有序的子文件）使归并段（有序的子文件）使归并段（有序的子文件）使归并段（有序的子文件）逐渐由小至大逐渐

12、由小至大逐渐由小至大逐渐由小至大,直到得到整个有序文件为止。直到得到整个有序文件为止。直到得到整个有序文件为止。直到得到整个有序文件为止。11-中国科大数据结构11.2 外部排序的方法pp例：一文件含例：一文件含例：一文件含例：一文件含1000010000记录记录记录记录,通过通过通过通过1010次内部排序得到次内部排序得到次内部排序得到次内部排序得到1010个初始归并段个初始归并段个初始归并段个初始归并段R1R10,R1R10,其中每一段都含有其中每一段都含有其中每一段都含有其中每一段都含有10001000个记录。个记录。个记录。个记录。然后作两两归并：然后作两两归并：然后作两两归并：然后作

13、两两归并：R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R1 R2 R3 R4 R5 R1 R2 R3 R1 R2 有序文件有序文件pp由由由由1010个初始归并段到一个有序文件个初始归并段到一个有序文件个初始归并段到一个有序文件个初始归并段到一个有序文件,共进行了共进行了共进行了共进行了4 4趟归并趟归并趟归并趟归并,每一趟都从每一趟都从每一趟都从每一趟都从mm个归并段得到个归并段得到个归并段得到个归并段得到ceil(m/2)ceil(m/2)个归并段。这种归并方法称为个归并段。这种归并方法称为个归并段。这种归并方法称为个归并段。这种归并方法称为2-2-路平衡归路平衡归路平衡

14、归路平衡归并并并并。11-中国科大数据结构11.2 外部排序的方法pp外存上信息的读外存上信息的读外存上信息的读外存上信息的读/写是以写是以写是以写是以“物理块物理块物理块物理块”为单位进行的为单位进行的为单位进行的为单位进行的,假设每个物理假设每个物理假设每个物理假设每个物理块可以容纳块可以容纳块可以容纳块可以容纳200200200200个记录个记录个记录个记录,则每一趟归并需进行则每一趟归并需进行则每一趟归并需进行则每一趟归并需进行50505050次次次次“读读读读”和和和和50505050次次次次“写写写写”,4,4,4,4趟归并加上内部排序时所需进行的读趟归并加上内部排序时所需进行的读

15、趟归并加上内部排序时所需进行的读趟归并加上内部排序时所需进行的读/写使得在外排序中总写使得在外排序中总写使得在外排序中总写使得在外排序中总共需进行共需进行共需进行共需进行500500500500次读次读次读次读/写。写。写。写。11-中国科大数据结构11.2 外部排序的方法pp外部排序所需总的时间外部排序所需总的时间外部排序所需总的时间外部排序所需总的时间 =内部排序（产生初始归并段）所需的时间内部排序（产生初始归并段）所需的时间内部排序（产生初始归并段）所需的时间内部排序（产生初始归并段）所需的时间(m m t tISIS)+外存信息读写的时间外存信息读写的时间外存信息读写的时间外存信息读写

16、的时间(d d t tIOIO)+内部归并所需的时间内部归并所需的时间内部归并所需的时间内部归并所需的时间(s s ututmgmg)pp其中：其中：其中：其中：t t t tISISISIS 是为得到一个初始归并段进行内部排序所需时间的均值；是为得到一个初始归并段进行内部排序所需时间的均值；是为得到一个初始归并段进行内部排序所需时间的均值；是为得到一个初始归并段进行内部排序所需时间的均值；t t t tIOIOIOIO 是进行一次外存读是进行一次外存读是进行一次外存读是进行一次外存读/写时间的均值；写时间的均值；写时间的均值；写时间的均值；ututututmgmgmgmg 是对是对是对是对u

17、 u u u个记录进行内部归并所需时间；个记录进行内部归并所需时间；个记录进行内部归并所需时间；个记录进行内部归并所需时间；m m m m 为经过内部排序之后得到的初始归并段的个数；为经过内部排序之后得到的初始归并段的个数；为经过内部排序之后得到的初始归并段的个数；为经过内部排序之后得到的初始归并段的个数；s s s s 为归并的趟数；为归并的趟数；为归并的趟数；为归并的趟数；d d d d 为总的读为总的读为总的读为总的读/写次数。写次数。写次数。写次数。pp于是上例进行外排序所需总的时间为：于是上例进行外排序所需总的时间为：于是上例进行外排序所需总的时间为：于是上例进行外排序所需总的时间为

18、：10 10 t tISIS +500+500 t tIOIO+4x10000 +4x10000 t tmgmg显然显然显然显然t t t tIOIOIOIO较较较较t t t tmgmgmgmg要大的多要大的多要大的多要大的多,因此提高外排序的效率应主要着眼于减少外存因此提高外排序的效率应主要着眼于减少外存因此提高外排序的效率应主要着眼于减少外存因此提高外排序的效率应主要着眼于减少外存信息读写的次数信息读写的次数信息读写的次数信息读写的次数d d d d。11-中国科大数据结构11.2 外部排序的方法ppd d d d和和和和“归并过程归并过程归并过程归并过程”的关系：的关系：的关系：的关系

19、：若对上例进行若对上例进行若对上例进行若对上例进行5 5 5 5路平衡归并：路平衡归并：路平衡归并：路平衡归并：R1 R2 R3 R4 R5R1 R2 R3 R4 R5 R6 R7 R8 R9 R10R6 R7 R8 R9 R10 R1R1 R2 R2 有序文件有序文件仅需两趟归并仅需两趟归并仅需两趟归并仅需两趟归并,总的读总的读总的读总的读/写次数便减少为：写次数便减少为：写次数便减少为：写次数便减少为：2x100+100=300,2x100+100=300,2x100+100=300,2x100+100=300,比比比比2 2 2 2路归路归路归路归并减少了并减少了并减少了并减少了2002

20、00200200次的读次的读次的读次的读/写。对同一文件写。对同一文件写。对同一文件写。对同一文件,进行外排序时所需读进行外排序时所需读进行外排序时所需读进行外排序时所需读/写外存写外存写外存写外存的次数和归并的趟数的次数和归并的趟数的次数和归并的趟数的次数和归并的趟数s s s s成正比。一般情况下成正比。一般情况下成正比。一般情况下成正比。一般情况下,对对对对m m m m个初始归并段进行个初始归并段进行个初始归并段进行个初始归并段进行k k k k路平衡归并时路平衡归并时路平衡归并时路平衡归并时,归并的趟数归并的趟数归并的趟数归并的趟数s=s=s=s=floor(logfloor(log

21、floor(logfloor(logk k k km m m m).).).).可见：若能增加可见：若能增加可见：若能增加可见：若能增加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个记录个记录个记录个记录,每得到归并后的一个记每得到归并后的一个记每得到归并后的一个记每得到归并后的一个记录录录录,仅需一次比较

22、即可仅需一次比较即可仅需一次比较即可仅需一次比较即可,因此得到含因此得到含因此得到含因此得到含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个归并段中关键字最小的记录个归并段中关键字最小的记

23、录个归并段中关键字最小的记录个归并段中关键字最小的记录,这需要进行这需要进行这需要进行这需要进行k-1k-1k-1k-1次比次比次比次比较较较较,得到得到得到得到u u u u个记录的归并段个记录的归并段个记录的归并段个记录的归并段,共需共需共需共需(u-1)(k-1)(u-1)(k-1)次比较。由此次比较。由此次比较。由此次比较。由此,对对对对n n n n个记个记个记个记录的文件进行外排序时录的文件进行外排序时录的文件进行外排序时录的文件进行外排序时,在内部归并过程中进行的总的比较次数为在内部归并过程中进行的总的比较次数为在内部归并过程中进行的总的比较次数为在内部归并过程中进行的总的比较次

24、数为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)t)(k-1)(n-1)tmgmgpp由于由于由于由于(k-1)/log2k(k-1)/log2k 随

25、随随随 k k k k 的增长而增长的增长而增长的增长而增长的增长而增长,这将抵消由于增大这将抵消由于增大这将抵消由于增大这将抵消由于增大k k k k而减少外而减少外而减少外而减少外存信息读写时间所得效益。存信息读写时间所得效益。存信息读写时间所得效益。存信息读写时间所得效益。11-中国科大数据结构11.3 多路平衡归并的实现pp在进行在进行在进行在进行k k k k路归并时利用路归并时利用路归并时利用路归并时利用“败者树败者树败者树败者树(Tree of Loser)(Tree of Loser)”,则可使在则可使在则可使在则可使在k k k k个记录个记录个记录个记录中选出关键字最小的记

26、录时仅需进行中选出关键字最小的记录时仅需进行中选出关键字最小的记录时仅需进行中选出关键字最小的记录时仅需进行floor(log2k)floor(log2k)次比较次比较次比较次比较,从而使从而使从而使从而使总的归并时间变为：总的归并时间变为：总的归并时间变为：总的归并时间变为：floor(logfloor(log2 2m)(n-1)tm)(n-1)tmgmg与与与与k k k k无关无关无关无关,不再随不再随不再随不再随k k k k的增长而增长。的增长而增长。的增长而增长。的增长而增长。11-中国科大数据结构11.3 多路平衡归并的实现pp胜者树及其使用胜者树及其使用胜者树及其使用胜者树及其

27、使用胜者进入下一轮胜者进入下一轮胜者进入下一轮胜者进入下一轮,直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决出冠军之后,充分充分充分充分利用上一次比赛的结果利用上一次比赛的结果利用上一次比赛的结果利用上一次比赛的结果,使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名 。729597654挑出冠军挑出冠军需要进行需要进行 k-1 次次比较比较,此处需要此处需要比较比较 3 次次。955320517654321055957299511-中国科大数据结构11

28、.3 多路平衡归并的实现pp胜者树及其使用胜者树及其使用胜者树及其使用胜者树及其使用胜者进入下一轮胜者进入下一轮胜者进入下一轮胜者进入下一轮,直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决出冠军之后,充分充分充分充分利用上一次比赛的结果利用上一次比赛的结果利用上一次比赛的结果利用上一次比赛的结果,使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名 。7291697654挑出亚军挑出亚军需要进行需要进行 log2k 次比较次比较,此处需此处需要比较要比较

29、2次次。9773207176543210779167299711-中国科大数据结构11.3 多路平衡归并的实现pp胜者树及其使用胜者树及其使用胜者树及其使用胜者树及其使用 胜者进入下一轮胜者进入下一轮胜者进入下一轮胜者进入下一轮,直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决出冠军之后直至决出本次比赛的冠军。决出冠军之后,充分充分充分充分利用上一次比赛的结果利用上一次比赛的结果利用上一次比赛的结果利用上一次比赛的结果,使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名使得更快地挑出亚军、第三名 。决出第一名需比较：

30、决出第一名需比较：决出第一名需比较：决出第一名需比较：k-1 k-1 次次次次 决出第二名需比较：决出第二名需比较：决出第二名需比较：决出第二名需比较：log log2 2k k 次次次次 决出第三名需比较：决出第三名需比较：决出第三名需比较：决出第三名需比较：log log2 2k k 次次次次 结果：采用胜者树后结果：采用胜者树后结果：采用胜者树后结果：采用胜者树后,从从从从 k k 个元素中挑选一个最小的元素仅需个元素中挑选一个最小的元素仅需个元素中挑选一个最小的元素仅需个元素中挑选一个最小的元素仅需 loglog2 2k k 次比较次比较次比较次比较,这时总的比较次数下降为：这时总的比

31、较次数下降为：这时总的比较次数下降为：这时总的比较次数下降为：loglogk km logm log2 2k (n-1)tk (n-1)tmgmg log log2 2m (n-1)tm (n-1)tmgmg 该结果和该结果和该结果和该结果和 k k 无关无关无关无关,这是通过多用空间换来的。这是通过多用空间换来的。这是通过多用空间换来的。这是通过多用空间换来的。pp改进：采用胜者树改进：采用胜者树改进：采用胜者树改进：采用胜者树,k k个元素中最小的元素输出之后个元素中最小的元素输出之后个元素中最小的元素输出之后个元素中最小的元素输出之后,从根结点到它从根结点到它从根结点到它从根结点到它的相

32、应的叶子结点路径上的结点都需要进行修改的相应的叶子结点路径上的结点都需要进行修改的相应的叶子结点路径上的结点都需要进行修改的相应的叶子结点路径上的结点都需要进行修改,为了加快程序运为了加快程序运为了加快程序运为了加快程序运行的速度产生了败者树。行的速度产生了败者树。行的速度产生了败者树。行的速度产生了败者树。11-中国科大数据结构11.3 多路平衡归并的实现pp败者树败者树败者树败者树在父节点中记下刚进行完的比赛中的败者在父节点中记下刚进行完的比赛中的败者在父节点中记下刚进行完的比赛中的败者在父节点中记下刚进行完的比赛中的败者,但同样让胜者去参加下但同样让胜者去参加下但同样让胜者去参加下但同样

33、让胜者去参加下一轮的竞赛一轮的竞赛一轮的竞赛一轮的竞赛,便得到一棵便得到一棵便得到一棵便得到一棵“败者树败者树败者树败者树”。11-中国科大数据结构11.3 多路平衡归并的实现pp下图即为一棵实现下图即为一棵实现下图即为一棵实现下图即为一棵实现5-5-5-5-路归并的败者树路归并的败者树路归并的败者树路归并的败者树ls0ls0ls0ls04,4,4,4,图中方形结点表示图中方形结点表示图中方形结点表示图中方形结点表示叶子结点叶子结点叶子结点叶子结点(也可看成是外结点也可看成是外结点也可看成是外结点也可看成是外结点),),),),分别为分别为分别为分别为5 5 5 5个归并段中当前参加归并个归并

34、段中当前参加归并个归并段中当前参加归并个归并段中当前参加归并的待选择记录的关键码；败者树中根结点的待选择记录的关键码；败者树中根结点的待选择记录的关键码；败者树中根结点的待选择记录的关键码；败者树中根结点ls1ls1ls1ls1的双亲结点的双亲结点的双亲结点的双亲结点ls0ls0ls0ls0为为为为“冠军冠军冠军冠军”,在此指示各归并段中的最小关键码记录为第三段中的记在此指示各归并段中的最小关键码记录为第三段中的记在此指示各归并段中的最小关键码记录为第三段中的记在此指示各归并段中的最小关键码记录为第三段中的记录；结点录；结点录；结点录；结点ls3ls3ls3ls3指示指示指示指示b1b1b1b

35、1和和和和b2b2b2b2两个叶子结点中的败者即是两个叶子结点中的败者即是两个叶子结点中的败者即是两个叶子结点中的败者即是b2,b2,b2,b2,而胜者而胜者而胜者而胜者b1b1b1b1和和和和b3(b3b3(b3b3(b3b3(b3是叶子结点是叶子结点是叶子结点是叶子结点b3b3b3b3、b4b4b4b4和和和和b0b0b0b0经过两场比赛后选出的获胜者经过两场比赛后选出的获胜者经过两场比赛后选出的获胜者经过两场比赛后选出的获胜者)进进进进行比较行比较行比较行比较,结点结点结点结点ls1ls1ls1ls1则指示它们中的败者为则指示它们中的败者为则指示它们中的败者为则指示它们中的败者为b1b1

36、b1b1。11-中国科大数据结构11.3 多路平衡归并的实现pp5-5-路归并的败者树路归并的败者树路归并的败者树路归并的败者树例例例例920ls0ls1ls3ls2ls4b0b1b2b4b36152512374810151591820202240213061210411-中国科大数据结构11.3 多路平衡归并的实现pp在选得最小关键码的记录之后在选得最小关键码的记录之后在选得最小关键码的记录之后在选得最小关键码的记录之后,只要修改叶子结点只要修改叶子结点只要修改叶子结点只要修改叶子结点b3b3b3b3中的值中的值中的值中的值,使其使其使其使其为同一归并段中的下一个记录的关键码为同一归并段中的

37、下一个记录的关键码为同一归并段中的下一个记录的关键码为同一归并段中的下一个记录的关键码,然后从该结点向上和双亲然后从该结点向上和双亲然后从该结点向上和双亲然后从该结点向上和双亲结点所指的关键码进行比较结点所指的关键码进行比较结点所指的关键码进行比较结点所指的关键码进行比较,败者留在该双亲败者留在该双亲败者留在该双亲败者留在该双亲,胜者继续向上直至胜者继续向上直至胜者继续向上直至胜者继续向上直至树根的双亲。如树根的双亲。如树根的双亲。如树根的双亲。如下下下下图所示。当第图所示。当第图所示。当第图所示。当第3 3 3 3个归并段中第个归并段中第个归并段中第个归并段中第2 2 2 2个记录参加归并时

38、个记录参加归并时个记录参加归并时个记录参加归并时,选得最小关键码记录为第一个归并段中的记录。为了防止在归并过选得最小关键码记录为第一个归并段中的记录。为了防止在归并过选得最小关键码记录为第一个归并段中的记录。为了防止在归并过选得最小关键码记录为第一个归并段中的记录。为了防止在归并过程中某个归并段变为空程中某个归并段变为空程中某个归并段变为空程中某个归并段变为空,可以在每个归并段中附加一个关键码为最可以在每个归并段中附加一个关键码为最可以在每个归并段中附加一个关键码为最可以在每个归并段中附加一个关键码为最大的记录。当选出的大的记录。当选出的大的记录。当选出的大的记录。当选出的“冠军冠军冠军冠军”

39、记录的关键码为最大值时记录的关键码为最大值时记录的关键码为最大值时记录的关键码为最大值时,表明此次表明此次表明此次表明此次归并已完成。归并已完成。归并已完成。归并已完成。11-中国科大数据结构11.3 多路平衡归并的实现pp5-5-路归并的败者树路归并的败者树路归并的败者树路归并的败者树例例例例920ls0ls1ls3ls2ls4b0b1b2b4b31525123748101515918202022402014151210311-中国科大数据结构11.3 多路平衡归并的实现pp实现实现实现实现k-k-路归并的败者树的初始化也容易实现路归并的败者树的初始化也容易实现路归并的败者树的初始化也容易实

40、现路归并的败者树的初始化也容易实现,只要先令所有的非终只要先令所有的非终只要先令所有的非终只要先令所有的非终端结点指向一个含最小关键码的叶子结点端结点指向一个含最小关键码的叶子结点端结点指向一个含最小关键码的叶子结点端结点指向一个含最小关键码的叶子结点,然后从各叶子结点出发然后从各叶子结点出发然后从各叶子结点出发然后从各叶子结点出发调整非终端结点为新的败者即可。调整非终端结点为新的败者即可。调整非终端结点为新的败者即可。调整非终端结点为新的败者即可。pp下面程序中简单描述了利用败者树进行下面程序中简单描述了利用败者树进行下面程序中简单描述了利用败者树进行下面程序中简单描述了利用败者树进行k-k

41、-路归并的过程路归并的过程路归并的过程路归并的过程,为了突出为了突出为了突出为了突出如何利用败者树进行归并如何利用败者树进行归并如何利用败者树进行归并如何利用败者树进行归并,避开了外存信息存取的细节避开了外存信息存取的细节避开了外存信息存取的细节避开了外存信息存取的细节,可以认为可以认为可以认为可以认为归并段已存在。归并段已存在。归并段已存在。归并段已存在。typedef int LoserTreek;/败者树是完全二叉树且不含叶子败者树是完全二叉树且不含叶子,可采用顺序存储结构可采用顺序存储结构typedef structKeyType key;ExNode,Externalk;/外结点外结

42、点,只存放待归并记录的关键码只存放待归并记录的关键码11-中国科大数据结构11.3 多路平衡归并的实现void K_Merge(LoserTree*ls,External*b)/k-路归并处理程序利用败者树路归并处理程序利用败者树ls将编号从将编号从0到到k-1的的k个输入归并段中的记录归并到输出归并段个输入归并段中的记录归并到输出归并段b0/到到bk-1为败者树上的为败者树上的k个叶子结点个叶子结点,分别存放分别存放k个输入归并段中当前记录的关键码个输入归并段中当前记录的关键码for(i=0;i0)if(bs.keyblst.key)slst;/s指示新的胜者指示新的胜者 t=t/2;ls0

43、=s;void CreateLoserTree(LoserTree*ls)/建立败者树建立败者树/已知已知b0到到bk-1为完全二叉树为完全二叉树ls的叶子结点存有的叶子结点存有k个关个关/键码键码,沿从叶子到根的沿从叶子到根的k条路径将条路径将ls调整为败者树调整为败者树 bk.key=MINKEY;/设设MINKEY为关键码可能的最小为关键码可能的最小值值 for(i=0;i0;i-)Adjust(ls,i);/依次从依次从bk-1,bk-2,b0出发调整败者出发调整败者 最后要提及一点最后要提及一点最后要提及一点最后要提及一点,k,k值的选择并非越大越好值的选择并非越大越好值的选择并非越

44、大越好值的选择并非越大越好,如何选择合适的如何选择合适的如何选择合适的如何选择合适的k k是一个是一个是一个是一个需要综合考虑的问题。需要综合考虑的问题。需要综合考虑的问题。需要综合考虑的问题。11-中国科大数据结构11.4 置换-选择排序pp归并的趟数不仅和归并的趟数不仅和归并的趟数不仅和归并的趟数不仅和k k k k成反比成反比成反比成反比,也和也和也和也和m m m m成正比成正比成正比成正比,因此减少因此减少因此减少因此减少m m m m是减少是减少是减少是减少s s s s的另的另的另的另一条途径。这里一条途径。这里一条途径。这里一条途径。这里m m m m是外部文件经过内部排序之后

45、得到的初始归并段是外部文件经过内部排序之后得到的初始归并段是外部文件经过内部排序之后得到的初始归并段是外部文件经过内部排序之后得到的初始归并段的个数的个数的个数的个数,m=,m=,m=,m=ceil(n/lceil(n/lceil(n/lceil(n/l)。若要减少若要减少若要减少若要减少m,m,m,m,就需要增加就需要增加就需要增加就需要增加l,l,l,l,但是内存的容量有限但是内存的容量有限但是内存的容量有限但是内存的容量有限,利用上一章利用上一章利用上一章利用上一章内排序的方法无法做到内排序的方法无法做到内排序的方法无法做到内排序的方法无法做到,所以必须探索新的排序方法。所以必须探索新的

46、排序方法。所以必须探索新的排序方法。所以必须探索新的排序方法。pp置换置换置换置换-选择排序选择排序选择排序选择排序(Replacement-Selection Sorting)(Replacement-Selection Sorting)是在树形选择排是在树形选择排是在树形选择排是在树形选择排序的基础上得来的序的基础上得来的序的基础上得来的序的基础上得来的,它的特点是：在整个排序（得到所有初始归并它的特点是：在整个排序（得到所有初始归并它的特点是：在整个排序（得到所有初始归并它的特点是：在整个排序（得到所有初始归并段）的过程中段）的过程中段）的过程中段）的过程中,选择最小（或最大）关键字和输

47、入、输出交叉或平选择最小（或最大）关键字和输入、输出交叉或平选择最小（或最大）关键字和输入、输出交叉或平选择最小（或最大）关键字和输入、输出交叉或平行进行。行进行。行进行。行进行。11-中国科大数据结构11.4 置换-选择排序pp假设初始待排文件为输入文件假设初始待排文件为输入文件假设初始待排文件为输入文件假设初始待排文件为输入文件FI,FI,FI,FI,初始归并段文件为输出文件初始归并段文件为输出文件初始归并段文件为输出文件初始归并段文件为输出文件FO,FO,FO,FO,内存工作区为内存工作区为内存工作区为内存工作区为WA,FOWA,FOWA,FOWA,FO和和和和WAWAWAWA的初始状态

48、为空的初始状态为空的初始状态为空的初始状态为空,并设内存工作区并设内存工作区并设内存工作区并设内存工作区WAWAWAWA的容量为的容量为的容量为的容量为w w w w个记录个记录个记录个记录,则置换则置换则置换则置换-选择排序的操作过程为：选择排序的操作过程为：选择排序的操作过程为：选择排序的操作过程为：1.1.1.1.从从从从FIFIFIFI输入输入输入输入w w w w个记录到工作区个记录到工作区个记录到工作区个记录到工作区WA;WA;WA;WA;2.2.2.2.从从从从WAWAWAWA中选出其中关键字最小值的记录中选出其中关键字最小值的记录中选出其中关键字最小值的记录中选出其中关键字最小

49、值的记录,记为记为记为记为MINIMAXMINIMAXMINIMAXMINIMAX记录；记录；记录；记录；3.3.3.3.将将将将MINIMAXMINIMAXMINIMAXMINIMAX记录输出到记录输出到记录输出到记录输出到FOFOFOFO中去；中去；中去；中去；4.4.4.4.若若若若FIFIFIFI不空不空不空不空,则从则从则从则从FIFIFIFI输入下一个记录到输入下一个记录到输入下一个记录到输入下一个记录到WAWAWAWA中；中；中；中；5.5.5.5.从从从从WAWAWAWA中所有关键字比中所有关键字比中所有关键字比中所有关键字比MINIMAXMINIMAXMINIMAXMINIM

50、AX记录的关键字大的记录中选出最记录的关键字大的记录中选出最记录的关键字大的记录中选出最记录的关键字大的记录中选出最小关键字记录小关键字记录小关键字记录小关键字记录,作为新的作为新的作为新的作为新的MINIMAXMINIMAXMINIMAXMINIMAX记录；记录；记录；记录；6.6.6.6.重复重复重复重复3-5,3-5,3-5,3-5,直至在直至在直至在直至在WAWAWAWA中选不出新的中选不出新的中选不出新的中选不出新的MINIMAXMINIMAXMINIMAXMINIMAX记录为止记录为止记录为止记录为止,由此得由此得由此得由此得到一个初始归并段到一个初始归并段到一个初始归并段到一个初

51、始归并段,输出一个归并段的结束标志到输出一个归并段的结束标志到输出一个归并段的结束标志到输出一个归并段的结束标志到FOFOFOFO中去；中去；中去；中去；7.7.7.7.重复重复重复重复2-6,2-6,2-6,2-6,直至直至直至直至WAWAWAWA为空为空为空为空,由此得到全部初始归并段。由此得到全部初始归并段。由此得到全部初始归并段。由此得到全部初始归并段。11-中国科大数据结构11.4 置换-选择排序pp例如：初始文件含例如：初始文件含例如：初始文件含例如：初始文件含24242424个记录个记录个记录个记录,关键字分别为：关键字分别为：关键字分别为：关键字分别为：51,49,39,46,

52、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,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个记

53、录，则用内排序的方法可以得到个记录，则用内排序的方法可以得到个记录，则用内排序的方法可以得到个记录，则用内排序的方法可以得到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,63RUN3:3,4,1

54、3,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 nRUN1:29,38,39,46,49,51,61RUN1:29,38,39,46,49,51,61RUN1:29,38

55、,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 nRUN3: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置换置换置

56、换置换-选择排序的过程选择排序的过程选择排序的过程选择排序的过程 (见教材第见教材第见教材第见教材第300300页页页页)：FOFOWAWAFIFI51,49,39,46,38,29,14,61,15,30,1,48,52,3,63,27,4,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

57、,30,1,48,52,3,63,27,4,13,89,24,46,58,33,7676292951,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,52,3,63,27,4,13,89,24,46,58

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,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,49515

59、1,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,46,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,1

60、4,143,63,27,4,13,89,24,46,58,33,763,63,27,4,13,89,24,46,58,33,7611-中国科大数据结构11.4 置换-选择排序pp在在在在WAWAWAWA中选择中选择中选择中选择MINIMAXMINIMAXMINIMAXMINIMAX记录的过程需利用记录的过程需利用记录的过程需利用记录的过程需利用“败者树败者树败者树败者树”来实现。来实现。来实现。来实现。1.1.1.1.内存工作区中的记录作为败者树的外部节点，而败者树的根内存工作区中的记录作为败者树的外部节点，而败者树的根内存工作区中的记录作为败者树的外部节点，而败者树的根内存工作区中的记录作为

61、败者树的外部节点，而败者树的根节点的父节点指示工作区中关键字最小的纪录；节点的父节点指示工作区中关键字最小的纪录；节点的父节点指示工作区中关键字最小的纪录；节点的父节点指示工作区中关键字最小的纪录；2.2.2.2.为了便于选出为了便于选出为了便于选出为了便于选出MINIMAXMINIMAXMINIMAXMINIMAX记录，为每一个记录附设一个所在归并记录，为每一个记录附设一个所在归并记录，为每一个记录附设一个所在归并记录，为每一个记录附设一个所在归并段的序号，在进行关键字的比较时，现比较段号，段号小的段的序号，在进行关键字的比较时，现比较段号，段号小的段的序号，在进行关键字的比较时，现比较段号

62、，段号小的段的序号，在进行关键字的比较时，现比较段号，段号小的为胜者，段号相同的则关键字小的为胜者；为胜者，段号相同的则关键字小的为胜者；为胜者，段号相同的则关键字小的为胜者；为胜者，段号相同的则关键字小的为胜者；3.3.3.3.败者树的建立可从设工作区中所有记录的段号均为败者树的建立可从设工作区中所有记录的段号均为败者树的建立可从设工作区中所有记录的段号均为败者树的建立可从设工作区中所有记录的段号均为“0 0 0 0”开始，开始，开始，开始，然后从然后从然后从然后从FIFIFIFI逐个输入逐个输入逐个输入逐个输入w w w w个记录到工作区是，自下而上调整败者树，个记录到工作区是，自下而上调

63、整败者树，个记录到工作区是，自下而上调整败者树，个记录到工作区是，自下而上调整败者树，由于这些记录的段号为由于这些记录的段号为由于这些记录的段号为由于这些记录的段号为“1 1 1 1”，则他们对于，则他们对于，则他们对于，则他们对于“0 0 0 0”段的记录而段的记录而段的记录而段的记录而言均为败者，从而逐个填充到败者树的各节点中去。言均为败者，从而逐个填充到败者树的各节点中去。言均为败者，从而逐个填充到败者树的各节点中去。言均为败者，从而逐个填充到败者树的各节点中去。11-中国科大数据结构11.4 置换-选择排序pp可以证明可以证明可以证明可以证明,利用置换利用置换利用置换利用置换-选择排序

64、，初始归并段的平均长度可达内存选择排序，初始归并段的平均长度可达内存选择排序，初始归并段的平均长度可达内存选择排序，初始归并段的平均长度可达内存允许尺寸允许尺寸允许尺寸允许尺寸ww的二倍。的二倍。的二倍。的二倍。最最小小值值 最最大大值值值递增值递增记录数记录数记录值分布按等概率记录值分布按等概率当当前前最最小小值值段段分分界界值值展开的环路均均 匀匀 下下 雪雪W积雪(内存容量)环路起、终点当前车位当前车位扫雪车在环形路上扫雪。将环路截断展开，扫雪车在环形路上扫雪。将环路截断展开，积雪截面为三角形如上图积雪截面为三角形如上图,其面积为其面积为W,则车走则车走一圈扫走的面积为一圈扫走的面积为2

65、W.类比到置换类比到置换_选择排序选择排序如黄字所示。如黄字所示。11-中国科大数据结构11.5 最佳归并树pp由置换由置换由置换由置换-选择生成所得的初始归并段，其各段长度不等。选择生成所得的初始归并段，其各段长度不等。选择生成所得的初始归并段，其各段长度不等。选择生成所得的初始归并段，其各段长度不等。pp假如由置换假如由置换假如由置换假如由置换-选择得到选择得到选择得到选择得到9 9个初始归并段，其长度分别为：个初始归并段，其长度分别为：个初始归并段，其长度分别为：个初始归并段，其长度分别为：9,30,12,9,30,12,18,3,17,2,6,2418,3,17,2,6,24。作。作。

66、作。作3-3-路平衡归并（如下图），假设每个记录占路平衡归并（如下图），假设每个记录占路平衡归并（如下图），假设每个记录占路平衡归并（如下图），假设每个记录占一个物理块，则两趟归并所需对外存进行的读一个物理块，则两趟归并所需对外存进行的读一个物理块，则两趟归并所需对外存进行的读一个物理块，则两趟归并所需对外存进行的读/写次数为：写次数为：写次数为：写次数为：(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考虑下图的归并过程，仅需对外存进行考虑下图的归并过程，仅需对外存进行考虑下图的归并过程，仅需对外存进行考虑下图的归并过程，仅需对外存进行446446次读次读次读次读/写，这棵归并树为写，这棵归并树为写，这棵归并树为写，这棵归并树为最佳归并树最佳归并树最佳归并树最佳归并树(11+32+59+121)x2(11+32+59+121)x2，为所有归并策略中所需读，为所有归并策略中所需读，为所有归并策略中所需读，为所有归并策