算法与数据结构课件-DSC11

第十一章.外部排序（Chapter11.ExternalSorting)待排序列记录数量太大，不能全部存放在计算机随机存储器中，排序过程中需对计算机外存进行访问，这种排序过程称为外部排序。§11.1外存信息的存取一、磁带信息的存取：

磁带是在一条塑料薄膜上涂有磁性材料用以记录数据的存储介质。其记录组之间有一定的空隙IRG（InterRecordGap），它不是连续运转的设备，读写二、磁盘信息的存取：

磁盘是在一片塑料薄膜上涂有磁性材料用以记录数据的存储介质。它分成多个磁道（柱面），每个磁道又分为多个扇区，多个磁盘组成的磁盘组还涉及到盘片号（磁头号），磁盘绕轴高速旋转，读写头则沿其一条半径作直线运动以寻道。它也不是信息只能在运行稳定时进行，且找到要读写的记录也需要一定的绕带时间，因此，在磁带上读写信息所需的时间由两部分组成：TI/O=td+ntw，其中td

为延迟时间，即读写磁头到达信息所在物理块起始位置所需时间，tw

为传输一个记录的时间。磁带是一种顺序存储设备。§11.2外部排序的方法

总体要用归并排序，亦即将待排序列分成若干子序列分别进入内存排成有序序列（初始归并段），再用归并排序将所有归并段排序成一个有序序列。连续运转的设备，读写信息只能在旋转稳定时进行，且找到要读写的记录也需要一定的寻道、寻扇区时间，因此，在磁盘上读写信息所需的时间由三部分组成：TI/O=tseek+tla+ntw，其中tseek

为寻道时间（seektime），tla

为寻扇区时间（latencytimetime），tw

为传输时间（transmissiontime）。磁盘是一种随机存储设备。

一般情况下，外部排序所需的总时间由三部分构成：内部排序（产生初始归并段）所需时间（m*tIS

）、外存信息读写时间（d*tIO

）、内部归并所需时间（s*utmg

）。其中tIS

是为得到一个初始归并段进行内部排序所序的平均时间，tIO

是进行一次外存读写的平均时间，utmg

是对u个记录进行内部归并所需的时间，m为初始归并段的个数，s为归并的趟数，d为总的读写次数。但由于访问外存储器的时间开销太大，即tIO

远远大于tmg，因此，要提高外部排序速度，就必须减少访问外存的次数。

对同一待排序列而言，外部排序访问外存的总次数d与归并的趟数s成正比，而对m

个初始归并段进行k路平衡归并所需的趟数s=logkm，因此，增加k或减少m均能减少s。

利用败者树（treeofloser）可解决这一问题：类似于锦标赛排序的思想，在进行k路平衡归并时，将相互比较过的关键字值较大的初始归并段号（败者）留在树结点中，将关键字值较小的初始归并段号（胜者）上传，直到找到最终的胜者（最小值的段号）；将其归并后，其下一记录将替换它参加新的一轮比赛以找到新的最小值段号；反复此过程，直至全部k个初始归并段合并成一个有序序列为止。此时的归并时间为log2m(n-1)tmg，与k无关，但k也并非越大越好。§11.3多路平衡归并的实现若单纯增加k以减少s，将会增加内部归并的时间utmg

，这将抵销d随s减少而得到的效益，如何解决这一矛盾呢？516128305233416283112141781015303856b3b4b0b1b2[0][1][2][3][4]

初始归并段

0b55555516045165033002830801125058135232334482316316124128018101015291030210120110151529885-路平衡归并的败者树：

例：§11.4置换-选择排序…

利用置换-选择排序（replacement-selectionsort）可以达到这个目的（也用败者树实现）：

置换-选择排序是在选择排序的基础上，当最小关键字记录被选出后，它空出的位置补充进一个新的记录，以后再求最小记录时，不能选择比刚才的最小记录关键字小的记录，只能从大于它的记录中寻找新的最小关键字记录。反复此过程，直至工作区中所有记录的关键字均比刚出去的最小记录的关键字小为止，此时得到的就是一个完整的初始归并段。

除了增加k可以减小s外，减小m也是减小s的另一有效途径。但减小m就意味着要增加初始归并段长度，这又受到计算机内存大小的制约，又该如何解决这个问题呢？设计算机工作区大小为W=5，试给出下面待排序列利用置换-选择排序得到的初始归并段：{23,45,12,5,2,6,27,39,16,44,55,24,1,13,78,123,4,21,66,168,35,3,18,33,96,51,49,72,22,41}。

例：初始归并段1为：2,5,6,12,16,23,27,39,44,45,55,78,123初始归并段2为：1,4,13,21,24,35,66,96,168初始归并段3为：3,18,22,33,41,49,51,72可见，利用置换-选择排序所得到的初始归并段数明显比直接用选择排序少得多。如上面的例子，直接用选择排序要生成六个初始归并段，但利用置换-选择排序后，只得到了三个归并段。

那么，利用置换-选择排序到底能使初始归并段的长度增加多少呢？

E.F.Moore用类比的办法解决了这个问题：设天上正匀速地下着大雪，有一台扫雪机也匀速地沿着一个环形跑道在扫雪，当达到某一平衡点时，单位时间内扫雪机扫去的雪和天上下的雪的量正好相等，跑道上的积雪量保持不变，则积雪形成了一个斜面：扫雪机前面的积雪厚度最大，扫雪机后面的积雪厚度为零。此时跑道上的积雪量就相当于计算机的工作区大小W，而扫雪机工作一圈所扫去的积雪量就相当于初始归并段的长度——2W。生成初始归并段的时间（不考虑输入输出）为O(nlogW)。§11.5缓冲区及并行操作设定相应的输入输出缓冲区，让输入、输出和内部归并三种操作同时进行（并行操作），也能提高总的外部排序时间。但增加缓冲区数目，必将减小工作区大小W，又使得初始归并段长度减小从而增加排序总时间。因此，外部排序总的时间与归并排序路数k的选择、缓冲区大小的设置以及各种外设参数的设置等有关，实际应用时要综合考虑各种因数。§11.6最佳归并树

用置换-选择排序得到的初始归并段长度各不相同，那应如何进行k路平衡归并呢？这实际上是建立k叉霍夫曼树的问题：当初始归并段总数不足（(m-1)MOD(k-1)≠0）时，需附加k-(m-1)MOD(k-1)-1个长度为零的虚段，亦即第一次归并时只对(m-1)MOD(k-1)+1个初始归并段归并。建立k叉霍夫曼树每次仍是选择记录数相对少的初始归并段先进行归并。最佳归并树不适合磁带归并排序。作业34.

已知某文件经过置换-选择排序之后，得到长度分别为47，9，39，18，4，12，23和7的八个初始归并段。试为3-路平衡归并设计一个读写外存次数最少的归并方案，并求出总的读写外存次数。§11.7磁带归并排序前面所介绍的各种技术除最佳归并树外均适合于磁带归并排序，但由于磁带是顺序存取设备，在实现外部排序时，有些特殊的问题需考虑。一、平衡归并

实现k-路平衡归并，需要2k台磁带机，其中k台用于输入，k台用于输出，待一趟归并完后，输入磁带机改为输出磁带机，输出磁带机也改为输入磁带机，再进行下一趟归并；反复此过程，直至全部记录归并为一段有序序列。二、多步归并

仔细分析一下磁带k-路平衡归并可以发现，其实只执行一趟k-路归并并不需要2k台磁带机，只需k+1台磁带机即可，多余的磁带机目的是为了下一趟归并。当然，只用k+1台磁带机也能实现k-路平衡归并，即在每趟归并完后，再将各输出归并段（在同一磁带机上）分配到k台磁带机上用于下一趟归并。但这需要花费很多时间，有没有更好的办法呢？

多步归并排序（polyphasemerging

sorting）能解决这个矛盾。与平衡归并不同，一趟多步归并不是文件中的全部记录都参与归并。设有4台磁带机和17个初始归并段，采用3-路多步归并排序，其归并过程为：

例：

3-路多步归并效率比3-路平衡归并差，但比2-路平衡归并强。那么，初始归并段又是如何分配在各磁带机上的呢？利用k-阶广义费波拉契序列，当初始归并段总数为某一费波拉契数（不足用虚段填充）时，各磁带机上分布的初始归并段数由下式给出：t1(k)

=fj-1(k)+fj-2(k)+fj-3(k)+…+fj-k