数据结构简明教程（第3版）课件 第9章排序(下)

第9章排序9.1排序的基本概念9.2插入排序9.3交换排序9.4选择排序9.5归并排序9.6基数排序9.7外排序第9章

排序1/32（1）生成若干初始归并段（顺串）：这一过程也称为文件预处理，常规方法：

①把含有n个元素的文件，按内存大小分成若干长度为L的子文件（归并段）。

②分别将各子文件（归并段）调入内存，采用有效的内排序方法排序后送回外存。

（2）多路归并：对这些初始归并段进行多遍归并，使得有序的归并段逐渐扩大，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。9.7外排序9.7外排序外排序的基本方法是归并排序法。它分为以下两个步骤：2/32内存abc.databc1.databc2.dat…abcn.dat内存abc1.databc2.dat…abcn.databc.dat第1步第2步有序均有序某内排序算法某排序算法：一般为归并算法9.7外排序3/32外排序的时间：读写文件的时间：用读写元素次数表示。关键字比较的时间：内存中的元素比较。外排序的时间≈读写文件时间+关键字比较时间9.7外排序4/329.7.1磁盘排序过程磁盘（磁盘是一种直接存取设备）排序过程如下：Fin文件内存读写Fout文件F1文件F2文件Fm文件…写写写内存读读读

生成若干初始归并段

归并成一个有序文件9.7外排序5/32设有一个文件Fin.dat，内含4500个元素：A1,A2,…,A4500。现在要对该文件进行排序。可占用的内存空间至多只能对750个元素进行排序。输入文件（被排序的文件）放在磁盘上，页块长为250个元素。文件Fin.dat（含4500个元素）容量为750个元素产生6个长度为750个元素的有序文件F1～F6。第一阶段某种内排序方法9.7外排序6/32可用内存空间大小为750个元素第二阶段：归并过程

F1F2F3F4F5F6F7F8F9F10F119.7外排序7/329.7.2初始归并段的生成方法1采用前面介绍的常规内排序方法，可以实现初始归并段的生成，但所生成的归并段的大小正好等于一次能放入内存中的元素个数。显然存在局限性。

内存abc.databc1.databc2.dat…abcn.dat均有序某内排序算法特点：产生的初始归并段个数多，每个初始归并段的长度大致相等。9.7外排序8/32采用置换－选择排序算法用于生成初始归并段。方法2

特点：产生的初始归并段个数少，每个初始归并段的长度可能差异大。9.7外排序9/32

【例9.9】设某个磁盘文件中共有18个元素，各元素的关键字分别为（15，4，97，64，17，32，108，44，76，9，39，82，56，31，80，73，255，68）。

若内存工作区可容纳5个元素，用置换-选择排序算法可产生几个初始归并段，每个初始归并段包含哪些元素？9.7外排序10/32173294476108398256318073154976425568∞18个元素（w=5）：内存工作区w=5归并段1：归并段2：Rmin=415173244647682971089依次类推，产生归并段2：9，31，39，56，68，73，80，2559.7外排序11/32k=2时,采用平衡归并时，如果初始归并段有m个，那么这样的归并树就有

log2m

+1层。要对数据进行

log2m

趟扫描。9.7.3多路平衡归并

说明：如果所有初始归并段的长度（初始归并段中的元素个数）相等或大致相等，可采用k路平衡归并。1.k路平衡归并的效率分析9.7外排序12/32例如：二路平衡归并5初始序列：（5,4,1,6,8,3,2,7）4168327451638271456237812345678高度log2m=4归并3趟每个页块读写各1次假设一个页块存放1个元素读或者写元素次数恰好是WPL，这里WPL=8*1*3=24读写元素次数=2WPL，这里为48用WPL反映外排序中的读写文件的时间9.7外排序13/32k路平衡归并的读写文件时间分析：若有m个初始归并段，共u个元素归并趟数=

logkm

k越大，WPL越少，则读写元素的次数越少。在内存空间允许的情况下，k越大越好！9.7外排序14/32若在归并中采用简单选择方法，每次在k个元素中选择最小者，需要关键字比较k-1次。每趟归并u个元素需要做(u-1)*(k-1)次比较，s=

logkm

）趟归并总共需要的关键字比较次数为：k路平衡归并的关键字比较时间分析：k越大，关键字比较次数越多！增大归并路数k，会使内部归并的时间增大。若k增大到一定的程度，就会抵消掉由于减少读写磁盘次数而赢得的时间。s*(u-1)*(k-1)=

logkm

*(u-1)*(k-1)=

log2m

*(u-1)*(k-1)／

log2k

9.7外排序15/32在k路归并中从k个元素简单选择最小元素2.利用败者树实现k路平衡归并采用败者树从k个元素简单选择最小元素9.7外排序16/32利用败者树实现k路平衡归并的过程是：

败者树类似于堆排序中的堆。先建立败者树。然后对k个输入有序段进行k路平衡归并。9.7外排序17/32

【例9.10】设有5个初始归并段，它们中各元素的关键字分别是：

F0：{17，21，∞}

F1：{5，44，∞}

F2：{10，12，∞}

F3：{29，32，∞}

F4：{15，56，∞}

其中，∞是段结束标志。说明利用败者树进行k=5路平衡归并排序的过程。9.7外排序18/32解：

构建败者树29F315F417F05F110F25(-∞)5(-∞)5(-∞)5(-∞)冠军（最小者）k=5：创建含有k个叶子结点的完全二叉树，总共2k-1=9个结点，另外添加一个冠军结点。每个叶子结点对应一个归并段，段号为0～4。初始时每个分支结点（含冠军）取值“5(-∞)”，5表示段号（此时为虚拟段号），-∞表示最小关键字。例如，某结点取值为“4(15)”，表示结点值来自4号段的关键字15对应的元素。9.7外排序19/3229F315F417F05F110F2冠军（最小者）5(-∞)5(-∞)5(-∞)5(-∞)5(-∞)4(15)3(29)4(15)2(10)1(5)0(17)4(15)1(5)败者树构建完毕

调整产生冠军（最小者）的过程：从F4F0操作：将当前结点的关键字与父结点比较，将大的（败者）放在父结点中，小者（胜者）继续进行，直到根结点。最后将胜者放在冠军结点中。9.7外排序20/3221∞29F315F417F05F110F2冠军（最小者）5(-∞)

用败者树进行归并5(-∞)5(-∞)5(-∞)5(-∞)4(15)3(29)4(15)2(10)1(5)0(17)4(15)1(5)44∞12∞15∞32∞归并文件：51(44)2(10)10依此进行，直到冠军为∞才结束。每次产生一个冠军，比较次数约为log2k。9.7外排序21/32

logkm

×(u-1)×

log2k

=

log2m

×(u-1)×

log2k

/

log2k

=

log2m

×(u-1)利用败者树实现k路平衡归并时，总共需要的关键字比较次数为：

结论：关键字比较次数与k无关

总的内部归并时间不会随k的增大而增大。

只要内存空间允许，尽可能增大归并路数k。利用败者树实现k路平衡归并9.7外排序22/329.7.4最佳归并树k路平衡归并适合初始归并段中的元素个数相同的情况，当初始归并段中的元素个数不同时，怎么办？

当初始归并段和k已确定的情况时哪些初始归并段先归并，哪些后归并的问题。归并方案转化为9.7外排序23/32显然采用k叉哈夫曼树的归并方案。剩下只有2个归并段了，怎么办？

存在的问题（假设k=3）：WPL最小在内存中归并时，可以利用败者树减少关键字比较次数9.7外排序24/32解决的方法是加虚段（长度为0的段），每次恰好k个段进行归并！应加(k-1)-(m-1)

Mod

(k-1)个虚段前面问题的解决方法：加上1个虚段：加多少个虚段呢？9.7外排序25/32

若x=(m-1)Mod(k-1)≠0，则需附加(k-1)-x个虚段，以使每次归并都可以对应k个段。

按照哈夫曼树的构造原则（权值越小的结点离根结点越远）构造最佳归并树。

最佳归并树（m个初始归并段）是带权路径长度最短的k叉（阶）哈夫曼树，构造步骤如下：k=2时，x=(m-1)Mod1=0，所以二路归并（哈夫曼树构造中）不需要增加虚段9.7外排序26/32

【例9.11】

设文件经预处理后，得到长度为

(49，9，35，18，4，12，23，7，21，14，26)的11个初始归并段，试为4路归并设计一个读写文件次数最少的归并方案（假如每个元素占用一个页块）。各个初始归并段中的元素个数，而非关键字序列9.7外排序27/32

初始归并段个数m=11，k=4。x=(m-1)Mod(k-1)=1≠0，因此需附加：

(k-1)-x=2个长度为0的虚段。根据集合：

(49，9，35，18，4，12，23，7，21，14，26，0，0)构造4阶哈夫曼树。9.7外排序28/324路最佳归并树的构造过程：004711182123268891214463549218按元素个数递增排序：(0，0，4，7，9，12，14，18，21，23，26，35，49)9.7外排序一棵4路最佳归并树29/32004711182123268891214463549218abdc读写文件次数最少的归并方案:第1次将长度为4和7的初始归并段（另增加2个虚段）归并为长度为11的有序段a。第2次将长度为9、12和14的初始归并段以及有序段a归并为长度为46的有序段b。第3次将长度为18、21、23和26的初始归并段归并为长度为88的有序段c。第4次将长度为35和