第九章_排序3.ppt

《第九章_排序3.ppt》由会员分享，可在线阅读，更多相关《第九章_排序3.ppt（99页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、7.9 外部排序外部排序当待排序的对象数目特别多时，在内存中不能当待排序的对象数目特别多时，在内存中不能当待排序的对象数目特别多时，在内存中不能当待排序的对象数目特别多时，在内存中不能一次处理。必须把它们以文件的形式存放于外存，一次处理。必须把它们以文件的形式存放于外存，一次处理。必须把它们以文件的形式存放于外存，一次处理。必须把它们以文件的形式存放于外存，排序时再把它们一部分一部分调入内存进行处理。排序时再把它们一部分一部分调入内存进行处理。排序时再把它们一部分一部分调入内存进行处理。排序时再把它们一部分一部分调入内存进行处理。这样，在排序过程中必须不断地在内存与外存之间这样，在排序过程中必

2、须不断地在内存与外存之间这样，在排序过程中必须不断地在内存与外存之间这样，在排序过程中必须不断地在内存与外存之间传送数据。这种基于外部存储设备（或文件）的排传送数据。这种基于外部存储设备（或文件）的排传送数据。这种基于外部存储设备（或文件）的排传送数据。这种基于外部存储设备（或文件）的排序技术就是外排序。序技术就是外排序。序技术就是外排序。序技术就是外排序。计计算算机机一一般般有有两两种种存存储储器器：内内存存储储器器和和外外存存储储器。器。内内存存储储器器存存储储的的信信息息可可随随机机存存取取、存存取取速速度度快快、价格贵、存储容量小。价格贵、存储容量小。外外存存储储器器包包括括磁磁带带和

3、和磁磁盘盘，前前者者为为顺顺序序存存取取的的设备，后者为随机存取的设备。设备，后者为随机存取的设备。磁盘是一种随机存取的设备，其特点是容量大，存磁盘是一种随机存取的设备，其特点是容量大，存磁盘是一种随机存取的设备，其特点是容量大，存磁盘是一种随机存取的设备，其特点是容量大，存取速度快，可直接存取任意字符组（记录）。取速度快，可直接存取任意字符组（记录）。取速度快，可直接存取任意字符组（记录）。取速度快，可直接存取任意字符组（记录）。磁盘的结构：磁盘的结构：磁盘的结构：磁盘的结构：动臂 主轴读写头磁盘信息的存取磁盘信息的存取一个磁盘由若干个盘面组成，一个盘面时称为单一个磁盘由若干个盘面组成，一个

4、盘面时称为单面磁盘，两个盘面时称为双面磁盘，多个盘面时称面磁盘，两个盘面时称为双面磁盘，多个盘面时称为磁盘组为磁盘组(磁盘组中，不同的盘面用不同的面号表示磁盘组中，不同的盘面用不同的面号表示)；每个盘面由若干个称为磁道的同心圆组成；每个盘面由若干个称为磁道的同心圆组成(同一同一个盘面上，不同的磁道用不同的磁道号表示个盘面上，不同的磁道用不同的磁道号表示)；每个；每个磁道又被划分为若干个称为扇区的块组成磁道又被划分为若干个称为扇区的块组成(同一个磁同一个磁道上，不同的扇区用不同的扇区号表示道上，不同的扇区用不同的扇区号表示)；数据以块；数据以块为单位存储在各个扇区上。为单位存储在各个扇区上。所以

5、，（面号，磁道号，扇区号）构成了磁盘上所以，（面号，磁道号，扇区号）构成了磁盘上标识一个数据块的唯一的地址。同磁带一样，每个标识一个数据块的唯一的地址。同磁带一样，每个块被定义成相同的大小，存取时每次以块为单位读块被定义成相同的大小，存取时每次以块为单位读写数据。写数据。磁盘上，读写一块信息所需的时间由三部分组成：磁盘上，读写一块信息所需的时间由三部分组成：磁盘上，读写一块信息所需的时间由三部分组成：磁盘上，读写一块信息所需的时间由三部分组成：T TI/OI/O=t ts s+t tl l+t trwrw 其中，其中，其中，其中，t ts s为为为为寻查时间，即读写磁头定位的时间。寻查时间，即

6、读写磁头定位的时间。寻查时间，即读写磁头定位的时间。寻查时间，即读写磁头定位的时间。t tl l为为为为等等等等待待待待时时时时间间间间，即即即即等等等等待待待待信信信信息息息息块块块块的的的的初初初初始始始始位位位位置置置置旋旋旋旋转转转转到到到到磁头下面的时间。磁头下面的时间。磁头下面的时间。磁头下面的时间。t trwrw为将为将为将为将在内存和磁盘之间传输一个数据快所需要在内存和磁盘之间传输一个数据快所需要在内存和磁盘之间传输一个数据快所需要在内存和磁盘之间传输一个数据快所需要的时间。的时间。的时间。的时间。由于外部排序牵涉到待排序数据元素的输入、输由于外部排序牵涉到待排序数据元素的输入

7、、输由于外部排序牵涉到待排序数据元素的输入、输由于外部排序牵涉到待排序数据元素的输入、输出，因此，减少输入、输出的次数是外排序需要解出，因此，减少输入、输出的次数是外排序需要解出，因此，减少输入、输出的次数是外排序需要解出，因此，减少输入、输出的次数是外排序需要解决的主要问题。决的主要问题。决的主要问题。决的主要问题。当对象以文件形式存放于磁盘上的时候，通常是当对象以文件形式存放于磁盘上的时候，通常是当对象以文件形式存放于磁盘上的时候，通常是当对象以文件形式存放于磁盘上的时候，通常是按物理块存储的。物理块也叫做页块，是磁盘存取按物理块存储的。物理块也叫做页块，是磁盘存取按物理块存储的。物理块也

8、叫做页块，是磁盘存取按物理块存储的。物理块也叫做页块，是磁盘存取的基本单位。的基本单位。的基本单位。的基本单位。即使需要多遍排序，在一遍排序时，最好是所有即使需要多遍排序，在一遍排序时，最好是所有即使需要多遍排序，在一遍排序时，最好是所有即使需要多遍排序，在一遍排序时，最好是所有待排序元素输入、输出各一次。待排序元素输入、输出各一次。待排序元素输入、输出各一次。待排序元素输入、输出各一次。满足此要求的排序方法为：归并排序。满足此要求的排序方法为：归并排序。满足此要求的排序方法为：归并排序。满足此要求的排序方法为：归并排序。外部排序的要求外部排序的要求外部排序基本上由两个相对独立的阶段组成。外部

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

10、序方法对它们进行排序，入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常称并将排序后得到的有序子文件重新写入外存，通常称并将排序后得到的有序子文件重新写入外存，通常称并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为这些有序子文件为这些有序子文件为这些有序子文件为归并段归并段归并段归并段或顺串（或顺串（或顺串（或顺串（runrun）；）；）；）；然后，对这些归并段进行逐趟归并，使归并段（有然后，对这些归并段进行逐趟归并，使归并段（有然后，对这些归并段进行逐趟归并，使归并段（有然后，对这些归并段进行逐趟归并，使归并段（有序的子文件）逐渐由小至大

11、，直至得到整个有序文件序的子文件）逐渐由小至大，直至得到整个有序文件序的子文件）逐渐由小至大，直至得到整个有序文件序的子文件）逐渐由小至大，直至得到整个有序文件为止。为止。为止。为止。显然，第一阶段的工作是前面已经讨论过的内容。显然，第一阶段的工作是前面已经讨论过的内容。显然，第一阶段的工作是前面已经讨论过的内容。显然，第一阶段的工作是前面已经讨论过的内容。这里主要讨论第二阶段即归并的过程。这里主要讨论第二阶段即归并的过程。这里主要讨论第二阶段即归并的过程。这里主要讨论第二阶段即归并的过程。外部排序的方法外部排序的方法从一个具体例子来看外排中的归并是如何进行的。从一个具体例子来看外排中的归并是

12、如何进行的。从一个具体例子来看外排中的归并是如何进行的。从一个具体例子来看外排中的归并是如何进行的。假设有一个含假设有一个含假设有一个含假设有一个含1000010000个记录的文件，首先通过个记录的文件，首先通过个记录的文件，首先通过个记录的文件，首先通过1010次次次次内部排序得到内部排序得到内部排序得到内部排序得到1010个初始归并段个初始归并段个初始归并段个初始归并段R1R1R10R10，其中每一段其中每一段其中每一段其中每一段都含都含都含都含10001000个记录。然后对它们作如下图所示的两两归个记录。然后对它们作如下图所示的两两归个记录。然后对它们作如下图所示的两两归个记录。然后对它

13、们作如下图所示的两两归并，直至得到一个有序文件为止。并，直至得到一个有序文件为止。并，直至得到一个有序文件为止。并，直至得到一个有序文件为止。R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 R14 R15 R21 R22 R31 R41将两个有序段归并成一个有序段的过程，若在内将两个有序段归并成一个有序段的过程，若在内将两个有序段归并成一个有序段的过程，若在内将两个有序段归并成一个有序段的过程，若在内存进行，则很简单。但在外部排序中需要做额外的工存进行，则很简单。但在外部排序中需要做额外的工存进行，则很简单。但在外部排序中需要做额外的工存进行，则很简单。但

14、在外部排序中需要做额外的工作。作。作。作。对外存上信息的读对外存上信息的读对外存上信息的读对外存上信息的读/写是以写是以写是以写是以“物理块物理块物理块物理块”为单位的。为单位的。为单位的。为单位的。假设在上例中每个物理块可以容纳假设在上例中每个物理块可以容纳假设在上例中每个物理块可以容纳假设在上例中每个物理块可以容纳10001000个记录，则个记录，则个记录，则个记录，则1000 01000 0个记录需要个记录需要个记录需要个记录需要1010个物理快存放，每一趟归并需进个物理快存放，每一趟归并需进个物理快存放，每一趟归并需进个物理快存放，每一趟归并需进行行行行1010次次次次“读读读读”和和

15、和和1010次次次次“写写写写”，四趟归并加上得到初始，四趟归并加上得到初始，四趟归并加上得到初始，四趟归并加上得到初始归并段所需内部排序时所需进行的读归并段所需内部排序时所需进行的读归并段所需内部排序时所需进行的读归并段所需内部排序时所需进行的读/写使得在外排写使得在外排写使得在外排写使得在外排中总共需进行（中总共需进行（中总共需进行（中总共需进行（10101010）44（10101010）100100次的次的次的次的读读读读/写。写。写。写。若把内存区域等份地分为若把内存区域等份地分为若把内存区域等份地分为若把内存区域等份地分为3 3个缓冲区。其中的两个个缓冲区。其中的两个个缓冲区。其中的

16、两个个缓冲区。其中的两个为输入缓冲区，一个为输出缓冲区，可以在内存中利为输入缓冲区，一个为输出缓冲区，可以在内存中利为输入缓冲区，一个为输出缓冲区，可以在内存中利为输入缓冲区，一个为输出缓冲区，可以在内存中利用简单用简单用简单用简单2 2路归并函数路归并函数路归并函数路归并函数mergemerge实现实现实现实现2 2路归并。路归并。路归并。路归并。首先首先首先首先,从参加归并排序的两个输入归并段从参加归并排序的两个输入归并段从参加归并排序的两个输入归并段从参加归并排序的两个输入归并段R1R1和和和和R2R2中分别读入一块，放在输入缓冲区中分别读入一块，放在输入缓冲区中分别读入一块，放在输入缓

17、冲区中分别读入一块，放在输入缓冲区1 1和输入缓冲区和输入缓冲区和输入缓冲区和输入缓冲区2 2中。中。中。中。然后，在内存中进行然后，在内存中进行然后，在内存中进行然后，在内存中进行2 2路归并，归并出来的对象顺序存路归并，归并出来的对象顺序存路归并，归并出来的对象顺序存路归并，归并出来的对象顺序存放到输出缓冲区中。放到输出缓冲区中。放到输出缓冲区中。放到输出缓冲区中。如果用如果用如果用如果用t tISIS表示为得到一个初始归并段进行内部排表示为得到一个初始归并段进行内部排表示为得到一个初始归并段进行内部排表示为得到一个初始归并段进行内部排序所需时间的均值、序所需时间的均值、序所需时间的均值、

18、序所需时间的均值、t tIOIO表示一个数据快进行一次外存表示一个数据快进行一次外存表示一个数据快进行一次外存表示一个数据快进行一次外存读读读读/写时间的均值、写时间的均值、写时间的均值、写时间的均值、t tmgmg表示对每个记录进行内部归并表示对每个记录进行内部归并表示对每个记录进行内部归并表示对每个记录进行内部归并所需时间、所需时间、所需时间、所需时间、mm为经过内部排序之后得到的初始归并段为经过内部排序之后得到的初始归并段为经过内部排序之后得到的初始归并段为经过内部排序之后得到的初始归并段的个数、的个数、的个数、的个数、s s为归并的趟数、为归并的趟数、为归并的趟数、为归并的趟数、d d

19、为总的读为总的读为总的读为总的读/写次数，则一般写次数，则一般写次数，则一般写次数，则一般情况下，外部排序所需总的时间为：情况下，外部排序所需总的时间为：情况下，外部排序所需总的时间为：情况下，外部排序所需总的时间为：m*m*t tISIS+d*+d*t tIOIO+s*n*+s*n*t tmgmg 其中其中其中其中t tIOIO取决于所用的外部设备，显然，取决于所用的外部设备，显然，取决于所用的外部设备，显然，取决于所用的外部设备，显然，t tIOIO较较较较t tISIS和和和和t tmgmg要大得多。从数据组织的角度，对相邻的数据快，要大得多。从数据组织的角度，对相邻的数据快，要大得多。

20、从数据组织的角度，对相邻的数据快，要大得多。从数据组织的角度，对相邻的数据快，我们可通过将它们放置在相同的扇区或相邻的磁道上我们可通过将它们放置在相同的扇区或相邻的磁道上我们可通过将它们放置在相同的扇区或相邻的磁道上我们可通过将它们放置在相同的扇区或相邻的磁道上以减少寻道时间和等待时间。以减少寻道时间和等待时间。以减少寻道时间和等待时间。以减少寻道时间和等待时间。形成初始形成初始归并段归并段输入输出输入输出的时间的时间s趟归并排趟归并排序的时间序的时间对于公式：对于公式：对于公式：对于公式：m*m*t tISIS+d*+d*t tIOIO+s*n*+s*n*t tmgmg由于：由于：由于：由于

21、：t tI I/O/O=t ts s+t tl l+t trwrw 其其其其中中中中，t ts s和和和和t tl l是是是是机机机机械械械械动动动动作作作作，而而而而t trwrw、t tISIS、t tmgmg是是是是电电电电子子子子线路的动作，所以线路的动作，所以线路的动作，所以线路的动作，所以 t tIOIO t tISIS，t tIOIO t tmgmg。提高机械运动速度是有上限的，因此，想要提提高机械运动速度是有上限的，因此，想要提提高机械运动速度是有上限的，因此，想要提提高机械运动速度是有上限的，因此，想要提高外排的效率，应主要着眼于减少外存信息读写高外排的效率，应主要着眼于减少

22、外存信息读写高外排的效率，应主要着眼于减少外存信息读写高外排的效率，应主要着眼于减少外存信息读写的次数的次数的次数的次数d d。下面来分析下面来分析d和和“归并过程归并过程”的关系。若对上例中的关系。若对上例中所得的所得的10个初始归并段进行个初始归并段进行5-路平衡归并（即每一趟将路平衡归并（即每一趟将5个或个或5个以下的有序子文件归并成一个有序子文件），个以下的有序子文件归并成一个有序子文件），则从下图可见，仅需进行二趟归并，外排时总的读则从下图可见，仅需进行二趟归并，外排时总的读/写写次数便减至次数便减至2(10+10)+(10+10)=60，比，比2-路归并减少了路归并减少了40次的读

23、次的读/写。写。R1 R2 R3 R4 R5 R6 R7 R8 R9 R10R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R1 R2 R1 R2 若对若对4500的元素进行排序，每个初始归并段含的元素进行排序，每个初始归并段含900个元素。在同样页块大小的情况下做个元素。在同样页块大小的情况下做2路、路、3路及路及6路路归并归并(当然当然,内存缓冲区的数目也要变化内存缓冲区的数目也要变化)，则可做大，则可做大致比较：致比较：可见，对同一文件而言，进行外排时所需读可见，对同一文件而言，进行外排时所需读/写外写外存的次数和归并的趟数存的次数和归并的趟数s成正比。一般情况下，对成正比

24、。一般情况下，对m个个初始归并段进行初始归并段进行k-路平衡归并时，归并的趟数：路平衡归并时，归并的趟数：s=logkm 。因此，增大归并路数，或减少初始归并段数因此，增大归并路数，或减少初始归并段数因此，增大归并路数，或减少初始归并段数因此，增大归并路数，或减少初始归并段数量，可望减少归并趟数，进而减少读写磁盘次数量，可望减少归并趟数，进而减少读写磁盘次数量，可望减少归并趟数，进而减少读写磁盘次数量，可望减少归并趟数，进而减少读写磁盘次数d d。归并路数归并路数归并路数归并路数 k k 总读写磁盘次数总读写磁盘次数总读写磁盘次数总读写磁盘次数 d d 归并趟数归并趟数归并趟数归并趟数 S S

25、 2 40 3 3 30 2 6 20 1一般情况下，对一般情况下，对m个初始归并段进行个初始归并段进行k-路平衡归并路平衡归并时，归并的趟数时，归并的趟数 s=logkm 可见，在可见，在m不变的情况下，增加归并的路数不变的情况下，增加归并的路数k便能减便能减少归并的趟数少归并的趟数s，从而减少外存的读写次数。下图是一从而减少外存的读写次数。下图是一个六路归并的例子：个六路归并的例子：k k路平衡归并与败路平衡归并与败者树者树下面讨论增大下面讨论增大k的问题。如果单纯增加的问题。如果单纯增加k将增加内部归并的时间，分析如下：将增加内部归并的时间，分析如下：对于二路归并，若对于二路归并，若u个

26、记录分布在两个归个记录分布在两个归并段上，最坏情况下，将两个归并段归并成并段上，最坏情况下，将两个归并段归并成一段需要一段需要u-1次比较。次比较。对于对于k路归并，若路归并，若u个记录分布在个记录分布在k个归并个归并段上，最坏情况下，每归并出一个记录都需段上，最坏情况下，每归并出一个记录都需要进行要进行k-1次比较，所以将含有次比较，所以将含有u个记录的个记录的k个个归并段归并成一有序段需要归并段归并成一有序段需要(k-1)(u-1)次比较。次比较。因此，对因此，对n个记录的文件进行外部排序时，个记录的文件进行外部排序时，如果排序需要的总的趟数为如果排序需要的总的趟数为s，则需要的总比则需要

27、的总比较次数为较次数为s(k-1)(n-1),设初始归并段为设初始归并段为m个，则个，则总的比较次数为：总的比较次数为：logkm (k-1)(n-1)=log2m (k-1)(n-1)/log2k =log2m (n-1)(k-1)/log2k（logkm=log2m/log2k)而而(k-1)/log2k 是是k的递增函数，因此使得内部归的递增函数，因此使得内部归并时间也随着并时间也随着k的增长而增长。当的增长而增长。当k增大到一定程度后，增大到一定程度后，就会抵消掉由于减少磁盘读写次数而赢得的时间。就会抵消掉由于减少磁盘读写次数而赢得的时间。然而若在然而若在k路归并时利用败者树，则可使在

28、路归并时利用败者树，则可使在k个记录个记录中选出最小记录的比较次数从中选出最小记录的比较次数从k1次减少到次减少到 log2k 次。次。式：式：logkm (k-1)(n-1)=log2m (k-1)(n-1)/log2k 转化为：转化为：转化为：转化为：logkm log2k (n-1)=log2m log2k (n-1)/log2k =log2m (n-1)即与即与即与即与k k无关。无关。无关。无关。败者树是一棵记录排序过程的二叉树，双亲结败者树是一棵记录排序过程的二叉树，双亲结点中记录的是竞赛的败者，而胜者去参加下一轮更点中记录的是竞赛的败者，而胜者去参加下一轮更高层次的竞赛。高层次的

29、竞赛。败者树实际上是一棵完全二叉树，其中败者树实际上是一棵完全二叉树，其中:败败者树者树n每个叶结点存放着各归并段在归并过程中当前参每个叶结点存放着各归并段在归并过程中当前参加比较的元素。加比较的元素。n每个非叶结点记忆它两个子结点中关键字较大的每个非叶结点记忆它两个子结点中关键字较大的结点（败者）所在段号。结点（败者）所在段号。n n另外增加一个结点另外增加一个结点另外增加一个结点另外增加一个结点(结点结点结点结点0)0)记忆树中当前对象关键记忆树中当前对象关键记忆树中当前对象关键记忆树中当前对象关键码最小的结点码最小的结点码最小的结点码最小的结点(胜者胜者胜者胜者)所在段号。所在段号。下图

30、就是一棵实现下图就是一棵实现5路归并的败者树。路归并的败者树。Run0:17,21,Run0:17,21,Run1:05,44,Run1:05,44,Run2:10,12,Run2:10,12,Run3:29,32,Run3:29,32,Run4:15,56,Run4:15,56,29293232 15155656 17172121 05054444 10101212 151510100505171729293 30 02 24 41 1k k3 3k k4 4k k0 0k k1 1k k2 2RunRun3 3RunRun4 4RunRun0 0RunRun1 1RunRun2 2ls l

31、s1 1ls ls0 0ls ls2 2ls ls4 4ls ls3 3冠军冠军冠军冠军 (最小对象最小对象最小对象最小对象),),),),输出段输出段输出段输出段1 1 1 1当前对象当前对象当前对象当前对象选中选中在在ls0（根结点）中记忆的是当前找到的最小元（根结点）中记忆的是当前找到的最小元素所在的归并段号（这里是素所在的归并段号（这里是1）。根据该段号可取出）。根据该段号可取出这个元素，将它送入结果归并段，再取该归并段的这个元素，将它送入结果归并段，再取该归并段的下一个元素，将其送入对应的叶结点（这里是下一个元素，将其送入对应的叶结点（这里是44），），然后从该叶结点到根结点自下而上

32、沿子女双亲路然后从该叶结点到根结点自下而上沿子女双亲路线进行比较和调整。使下一个具有次小关键字的元线进行比较和调整。使下一个具有次小关键字的元素所在的归并段号调整到冠军位置（最高层结点）。素所在的归并段号调整到冠军位置（最高层结点）。这里，次小关键字元素所在队列号为这里，次小关键字元素所在队列号为2。Run0:17,21,Run0:17,21,Run1:05,44,Run1:05,44,Run2:10,12,Run2:10,12,Run3:29,32,Run3:29,32,Run4:15,56,Run4:15,56,29293232 15155656 17172121 4444 1010121

33、2 151510104444171729293 30 02 24 41 1k k3 3k k4 4k k0 0k k1 1k k2 2RunRun3 3RunRun4 4RunRun0 0RunRun1 1RunRun2 2ls ls1 1ls ls0 0ls ls2 2ls ls4 4ls ls3 3冠军冠军冠军冠军 (最小对象最小对象最小对象最小对象),),),),输出段输出段输出段输出段1 1 1 1当前对象当前对象当前对象当前对象选中选中输出段输出段1 1最小对象，最小对象，段段1 1下一对象参选，下一对象参选，调整败者树调整败者树29293232 15155656 17172121

34、05054444 10101212 151510104444171729293 30 01 14 42 2k k3 3k k4 4k k0 0k k1 1k k2 2RunRun3 3RunRun4 4RunRun0 0RunRun1 1RunRun2 2ls ls1 1ls ls0 0ls ls2 2ls ls4 4ls ls3 3次最小对象次最小对象次最小对象次最小对象选中选中利用败者树进行利用败者树进行利用败者树进行利用败者树进行5 5路平衡归并的过程路平衡归并的过程路平衡归并的过程路平衡归并的过程(1)(1)初始状态初始状态初始状态初始状态 (2)(2)加入加入加入加入15,29,15

35、,29,调整调整调整调整29155 5175 5055 510-5 55 5k k3 3k k4 4k k5 5k k0 0k k1 1k k2 2ls ls1 1ls ls0 0ls ls2 2ls ls3 3ls ls4 410k k2 25 505ls ls3 3k k1 1174 4k k0 0ls ls2 23 3ls ls4 41515k k4 4-k k5 52929k k3 35 5ls ls1 15 5ls ls0 0利用败者树进行利用败者树进行利用败者树进行利用败者树进行5 5路平衡归并的过程路平衡归并的过程路平衡归并的过程路平衡归并的过程292915153 3174 40

36、5052 21010-1 15 5k k3 3k k4 4k k5 5k k0 0k k1 1k k2 2ls ls1 1ls ls0 0ls ls2 2ls ls3 3ls ls4 41010k k2 22 20505ls ls3 3k k1 117170 0k k0 0ls ls2 23 3ls ls4 41515k k4 4-k k5 52929k k3 34 4ls ls1 11 1ls ls0 0(3)(3)加入加入加入加入10,05,10,05,调整调整调整调整 (4)(4)加入加入加入加入17,17,调整调整调整调整输出输出0505利用败者树进行利用败者树进行利用败者树进行利用败

37、者树进行5 5路平衡归并的过程路平衡归并的过程路平衡归并的过程路平衡归并的过程292915153 317170 044441 110104 42 2k k3 3k k4 4k k0 0k k1 1k k2 2ls ls1 1ls ls0 0ls ls2 2ls ls3 3ls ls4 41212k k2 21 14444ls ls3 3k k1 117170 0k k0 0ls ls2 23 3ls ls4 41515k k4 42929k k3 34 4ls ls1 12 2ls ls0 0(5)(5)输出输出输出输出0505后调整后调整后调整后调整 (6)(6)输出输出输出输出1010后调

38、整后调整后调整后调整输入输入4444输出输出12输出输出10 0输入输入1212利用败者树进行利用败者树进行利用败者树进行利用败者树进行5 5路平衡归并的过程路平衡归并的过程路平衡归并的过程路平衡归并的过程292915153 317170 044442 2 1 14 4k k3 3k k4 4k k0 0k k1 1k k2 2ls ls1 1ls ls0 0ls ls2 2ls ls3 3ls ls4 4 k k2 22 24444ls ls3 3k k1 117173 3k k0 0ls ls2 24 4ls ls4 45656k k4 42929k k3 31 1ls ls1 10 0l

39、s ls0 0输入输入 输出输出17输出输出15 5输入输入5656(7)(7)输出输出输出输出1212后调整后调整后调整后调整 (8)(8)输出输出输出输出1515后调整后调整后调整后调整利用败者树进行利用败者树进行利用败者树进行利用败者树进行5 5路平衡归并的过程路平衡归并的过程路平衡归并的过程路平衡归并的过程292956564 421213 344442 2 1 10 0k k3 3k k4 4k k0 0k k1 1k k2 2ls ls1 1ls ls0 0ls ls2 2ls ls3 3ls ls4 4 k k2 22 24444ls ls3 3k k1 1 0 0k k0 0ls

40、 ls2 24 4ls ls4 45656k k4 42929k k3 31 1ls ls1 13 3ls ls0 0输入输入2121输出输出29输出输出21输入输入 (9)(9)输出输出输出输出1717后调整后调整后调整后调整 (10)(10)输出输出输出输出2121后调整后调整后调整后调整 利用败者树进行利用败者树进行利用败者树进行利用败者树进行5 5路平衡归并的过程路平衡归并的过程路平衡归并的过程路平衡归并的过程323256564 4 0 044442 2 1 13 3k k3 3k k4 4k k0 0k k1 1k k2 2ls ls1 1ls ls0 0ls ls2 2ls ls3

41、 3ls ls4 4 k k2 22 24444ls ls3 3k k1 1 0 0k k0 0ls ls2 23 3ls ls4 45656k k4 4 k k3 34 4ls ls1 11 1ls ls0 0输入输入32 2输出输出44输出输出32输入输入 (11)(11)输出输出输出输出2929后调整后调整后调整后调整 (12)(12)输出输出输出输出3232后调整后调整后调整后调整利用败者树进行利用败者树进行利用败者树进行利用败者树进行5 5 5 5路平衡归并的过程路平衡归并的过程路平衡归并的过程路平衡归并的过程 56563 3 0 0 2 2 1 14 4k k3 3k k4 4k

42、k0 0k k1 1k k2 2ls ls1 1ls ls0 0ls ls2 2ls ls3 3ls ls4 4 k k2 22 2 ls ls3 3k k1 1 0 0k k0 0ls ls2 23 3ls ls4 4 k k4 4 k k3 31 1ls ls1 14 4ls ls0 0输出输出 ，结束结束结束结束输出输出56输入输入 输入输入 (13)(13)输出输出输出输出4444后调整后调整后调整后调整 (14)(14)输出输出输出输出5656后调整后调整后调整后调整n n败者树的高度为败者树的高度为败者树的高度为败者树的高度为 loglog2 2k k ，在每次调整时，找下一个具在

43、每次调整时，找下一个具在每次调整时，找下一个具在每次调整时，找下一个具有最小关键码对象时有最小关键码对象时有最小关键码对象时有最小关键码对象时,最多做最多做最多做最多做 loglog2 2k k 次关键码比较。次关键码比较。次关键码比较。次关键码比较。n n在内存中应为每一个归并段分配一个输入缓冲区，其在内存中应为每一个归并段分配一个输入缓冲区，其在内存中应为每一个归并段分配一个输入缓冲区，其在内存中应为每一个归并段分配一个输入缓冲区，其大小应能容纳一个页块的对象，编号与归并段号一致。大小应能容纳一个页块的对象，编号与归并段号一致。大小应能容纳一个页块的对象，编号与归并段号一致。大小应能容纳一

44、个页块的对象，编号与归并段号一致。每个输入缓冲区应有一个指针，指示当前参加归并的每个输入缓冲区应有一个指针，指示当前参加归并的每个输入缓冲区应有一个指针，指示当前参加归并的每个输入缓冲区应有一个指针，指示当前参加归并的对象。对象。对象。对象。n n在内存中还应设立一个输出缓冲区，其大小相当于一在内存中还应设立一个输出缓冲区，其大小相当于一在内存中还应设立一个输出缓冲区，其大小相当于一在内存中还应设立一个输出缓冲区，其大小相当于一个页块大小。它也有一个缓冲区指针，指示当前可存个页块大小。它也有一个缓冲区指针，指示当前可存个页块大小。它也有一个缓冲区指针，指示当前可存个页块大小。它也有一个缓冲区指

45、针，指示当前可存放结果对象的位置。每当一个对象放结果对象的位置。每当一个对象放结果对象的位置。每当一个对象放结果对象的位置。每当一个对象i i被选出，就执行被选出，就执行被选出，就执行被选出，就执行OutputRecord(iOutputRecord(i)操作，将对象按输出缓冲区指针所操作，将对象按输出缓冲区指针所操作，将对象按输出缓冲区指针所操作，将对象按输出缓冲区指针所指位置存放到输出缓冲区中。指位置存放到输出缓冲区中。指位置存放到输出缓冲区中。指位置存放到输出缓冲区中。n n在实现利用败者树进行多路平衡归并算法时，把败者在实现利用败者树进行多路平衡归并算法时，把败者在实现利用败者树进行多

46、路平衡归并算法时，把败者在实现利用败者树进行多路平衡归并算法时，把败者树的叶结点和非叶结点分开定义。树的叶结点和非叶结点分开定义。树的叶结点和非叶结点分开定义。树的叶结点和非叶结点分开定义。n n败者树叶结点败者树叶结点败者树叶结点败者树叶结点keykkeyk有有有有k+1k+1个，个，个，个，key0key0到到到到keyk-1keyk-1存放各存放各存放各存放各归并段当前参加归并的对象的关键码，归并段当前参加归并的对象的关键码，归并段当前参加归并的对象的关键码，归并段当前参加归并的对象的关键码，keykkeyk是辅助是辅助是辅助是辅助工作单元，在初始建立败者树时使用，存放一个最小工作单元，

47、在初始建立败者树时使用，存放一个最小工作单元，在初始建立败者树时使用，存放一个最小工作单元，在初始建立败者树时使用，存放一个最小的在各归并段中不可能出现的关键码的在各归并段中不可能出现的关键码的在各归并段中不可能出现的关键码的在各归并段中不可能出现的关键码:-:-:-:-MaxNumMaxNum。n n败者树非叶结点败者树非叶结点败者树非叶结点败者树非叶结点loserk-1loserk-1有有有有k k个，其中个，其中个，其中个，其中loser1loser1到到到到loserk-1loserk-1存放各次比较的败者的归并段号，存放各次比较的败者的归并段号，存放各次比较的败者的归并段号，存放各次

48、比较的败者的归并段号，loser0loser0中中中中是最后胜者所在的归并段号。另外还有一个对象数组是最后胜者所在的归并段号。另外还有一个对象数组是最后胜者所在的归并段号。另外还有一个对象数组是最后胜者所在的归并段号。另外还有一个对象数组rkrk，存放各归并段当前参加归并的对象。存放各归并段当前参加归并的对象。存放各归并段当前参加归并的对象。存放各归并段当前参加归并的对象。void kwaymerge(Element*r,int k)int i,q;r=new Elementk;/创建对象数组创建对象数组 int*key=new intk+1;/创建外结点数组创建外结点数组 int*loser

49、=new intk;/创建败者树数组创建败者树数组 for(int i=0;i k;i+)/传送参选关键码，初始化传送参选关键码，初始化key数组数组 InputRecord(ri);keyi=ri.key;for(i=0;i 0;i-)/调整形成败者树调整形成败者树 adjust(key,loser,k,i);k k路平衡归并排序算法路平衡归并排序算法 while(keyloser0!=MaxNum)/选归并段选归并段 q=loser0;/最小对象的段号最小对象的段号 OutputRecord(rq);/输出输出 InputRecord(rq);/从该段补入对象从该段补入对象 keyq=rq

50、.key;adjust(key,loser,k,q);/调整调整 Output end of run marker;/输出段结束标志输出段结束标志 delete r;delete key;delete loser;n以后每选出一个当前关键码最小的对象，就需以后每选出一个当前关键码最小的对象，就需要在将它送入输出缓冲区之后，从相应归并段要在将它送入输出缓冲区之后，从相应归并段的输入缓冲区中取出下一个参加归并的对象，的输入缓冲区中取出下一个参加归并的对象，替换已经取走的最小对象，再从叶结点到根结替换已经取走的最小对象，再从叶结点到根结点，沿某一特定路径进行调整，将下一个关键点，沿某一特定路径进行调