数据结构课件：第7章 排序

1、第七章 排 序第七章 排序7.1 基本概念7.2 插入排序7.3 交换排序7.4 选择排序7.5 合并排序7.6 基于关键词比较的排序算法分析7.7 分布排序从数学和计算机角度而言，简单地说排序算法就是把元素按照一定的序关系列表，最常见的序关系是数字序和字典序。高效的排序算法有助于提高其他算法的效率，如查找算法。此外，在很多情况下，排序有助于规范化数据和便于人类阅读、理解。尽管排序问题本身相对于其他计算理论问题而言并不复杂，但要设计高效的、有针对性的排序算法也并非易事，因此针对它的研究一直在持续开展。排序，也叫分类，是将一组杂乱无章的数据按一定的规律排列起来的过程。 文件，是待排序数据对象的集

2、合；一个数据对象也叫作一个记录，记为R1，R2，Rn关键词域(key): 通常数据对象由多个属性域(多个数据成员)组成，其中可将一个属性域作为排序依据，该域即为关键词域。关键词记为：K1，K2，Kn；排序：将记录按关键词域递增或递减的顺序排列7.1 基本概念每个文件用哪个属性域作为关键词，要视具体的应用需要而定；即使是同一个文件表，在解决不同问题的场合也可能取不同的关键词域。主关键词: 如果在数据表中各个对象的关键词互不相同，这种关键词即主关键词。按照主关键词排序，排序的结果是唯一的。次关键词: 数据表中有些对象的关键词可能相同，这种关键词称为次关键词。按照次关键词排序，排序的结果可能不唯一。

3、排序算法的度量指标:排序的时间开销(排序算法的时间复杂性):是衡量算法好坏的最重要标志。可用算法执行中关键词的比较次数与数据的移动次数来衡量。各算法的时间复杂性一般都按平均情况进行估算。对那些受对象初始排列及对象个数影响较大的，需要按最好和最坏情况进行估算。算法的空间复杂性:主要考察排序过程所需辅助存储空间的大小。排序算法的稳定性: 如果在对象序列中有两个对象ri和rj，它们的关键词ki=kj，且在排序之前对象ri排在rj前面，如果在排序之后，对象ri仍在对象rj的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。排序算法有多种分类方法:从元素的存储设备角度可分为内排序（在内存中进

4、行）和外排序（在外存储器上进行）。按对关键词的操作可分为基于关键词比较的排序算法和分布排序算法。按时间代价分类：平方阶排序算法，它们一般都比较简单，特点是容易实现，但时间复杂度相对较高，最坏情况下时间复杂度一般为O(n2)；线性对数阶算法，以分治策略算法为主，最坏情况下时间复杂度一般为O(nlog(n). 第七章 排序7.1 基本概念7.2 插入排序 直接插入排序 希尔排序7.3 交换排序7.4 选择排序7.5 合并排序7.6 基于关键词比较的排序算法分析7.7 分布排序7.2 插入排序 例： 原有序表：(9 15 23 28 37) 20 找插入位置 : (9 15 23 28 37) 20

5、 新有序表: (9 15 20 23 28 37)插入排序思想 基于插入操作所完成的排序。 插入:将一个记录插入到已排好序的有序表中，从而得到一个新的记录数增一的有序表。7.2.1 直接插入排序算法1. 基本思想 待排序记录 R1，R2， ，Rn1, Rn 第一步：R1 第二步：(R1 ), R2 第三步：(R1 , R2), R3 第 j 步：(R1，R2， ，Rj1), Rj 第 n 步: (R1，R2， ，Rn1), Rn例：j=59152823081 2 3 4 5 616162816231616一次插入过程1616原有序表中关键词比Rj大的记录数：dj比较次数：dj+1 移动次数：

6、dj+2 2816232. 算法描述算法 InsertSort (R,n) FOR j2 TO n DO ( /每次将Rj插入到有序表R1，Rj1中 KKj. RRj. ij-1. WHILE (i0) AND (KiK) DO (Ri+1Ri. ii-1.) Ri+1R. ) 算法InsertSortA( R, s, e ) /引入虚拟记录,Ks-1minKi| sie ISA1 逐一排序 FOR js+1 TO e DO ( ij-1KKj. RRj . WHILE KKi DO ( Ri+1Ri ii-1 ) Ri+1R ) ISA1 逐一排序 FOR js+1 TO e DO ( ij

7、-1KKj . RRj . WHILE KKi DO ( Ri+1Ri ii-l ) Ri+1R ) k1k2k3k4k0k587246j 24678872462 27 8464 7 82463 247 865 3. 算法分析 设dj是Rj左边关键词大于Kj的记录个数，则算法InsertSortA中关键词的比较次数为： 记录的移动次数为 最好情况下，排序前记录已经按关键词从小到大有序排列，即dj=0。每趟只需与前面的有序部分的最后一个记录的关键词比较 1 次，记录移动 2 次，总的关键词比较次数为 n-1，记录移动次数为 2(n-1)。最坏情况下：第i趟时，第i个记录前面所有记录的关键词都比第

8、i个记录的关键词大，即dj=j-1 总的关键词比较次数： 记录移动次数： 平均情况下，若待排序文件中记录所有可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键词比较次数和记录移动次数分别为 因此，直接插入排序的时间复杂度为 O(n2)。平均情况下，考察分析 的期望值。对于序列K1，K2，Kn ，如果1ijn，且KiKj，则称(Ki , Kj)为上述序列的一个反序对。实际上， 正好是序列K1，K2，Kn的反序对个数。 例 待排序记录：8，7，2，4，6中反序对的个数 是7个。则有,反序对的平均个数 = 0+ (0+1)/2+ (0+1+2)/3+ (0123)/4(0

9、1234)/5 (012345)/6 (012n1)/n 01/22/2 3/24/25/2( n1)/2n(n1)/4即 的期望值为n(n1)/4 . 4.直接插入排序算法总结优点:是算法的执行过程相当清晰，并且书写容易.缺点:期望复杂性为O(n2) . 稳定性：直接插入排序是稳定的排序方法。最好情况是：当被排序文件初态为正序时，算法的时间复杂度为O(n) . 辅助空间： O(1) 5. 直接插入排序算法是否可以进一步改进呢？直接插入排序算法中包含了一个查找过程，对前部已经排序完的记录执行顺序查找。这显然是其效率低下的原因之一，是否可以通过改进顺序查找来提高排序效率呢? 通过将顺序查找改为二

10、分查找，可以构造二分插入排序算法。即在插入第j个元素时，不是像直接插入排序那样顺序寻找插入的位置，而是采用对半（或二分）的方法插入。如果文件（R1，R2，Rn）采用顺序存储，则对半插入排序算法可以减少关键词的比较次数，但是记录的移动次数仍不能减少。如果文件（R1，R2，Rn）采用链接存储，不能使用对半的方法寻找插入位置。第七章 排序7.1 基本概念7.2 插入排序 直接插入排序 希尔排序7.3 交换排序7.4 选择排序7.5 合并排序7.6 基于关键词比较的排序算法分析7.7 分布排序7.8 外排序 7.2.2 希尔(shell)排序1、希尔排序（渐减增量排序法）思想： 1959年Donald

11、 L. Shell提出Shell排序法 ，源自对直接插入算法的改进. 把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。 例 将十个数进行希尔排序的示例。 0 1 2 3 4 5 6 7 8 9下标 36 25 48 12 65 25 43 58 76 32d1=525434858127625363265 25 25 48 12 32 36 43 58 76 65一趟排序结果 例 将十个数进行希尔排序的示例。 0 1 2 3 4 5 6 7 8 9下标d2=2 25 25 48 12 32

12、36 43 58 76 65254832437625123658653243481225 25 12 32 25 43 36 48 58 76 65二趟排序结果 12 25 25 32 36 43 48 58 65 76三趟排序结果d3=1 希尔排序增量的取法： d1= = =5n/210/2d2= = =2d1/25/2d3= = =1d2/22/22、算法分析Shell算法的性能与所选取的分组长度序列有很大关系。只对特定的待排序记录序列，可以准确地估算关键词的比较次数和对象移动次数。想要弄清关键词比较次数和记录移动次数与增量选择之间的关系，并给出完整的数学分析，至今仍然是数学难题。Shel

13、l算法的性能与所选取的分组长度序列有很大关系。前面介绍的实例是最简单的分组长度序列，即n/2i，最坏情况下时间复杂度为O(n2). 一般实际应用中选择2.2作为递减因子效果更好，而不是2 . 如果选择2k-1为分组长度序列，最坏情况下能达到 . 第七章 排序7.1 基本概念7.2 插入排序7.3 交换排序 冒泡排序 快速排序7.4 选择排序7.5 合并排序7.6 基于关键词比较的排序算法分析7.7 分布排序7.8 外排序 7.3 交换排序反序对：对于序列K1, K2, , Kn, 若1iKj , 则称(Ki,Kj)为上述序列的一个反序对。交换排序的思想：交换文件中存在的反序对，直到不存在反序对

14、为止。交换排序包括：冒泡排序、分划交换排序（快速排序）。7.3.1 冒泡排序 1、冒泡排序思想： 通过比较相邻记录的关键词，交换存在逆序的记录；使关键词较大的记录如气泡一般逐渐往上“飘移”直至浮出“水面”。 i = 1090216080512 1 2 3 4 5 6 7 8 9131407 1 2 3 4 5 6 7 8 9090216080512131407i = 2 1 2 3 4 5 6 7 8 90902160805121314072、冒泡排序算法算法BSort ( R，n ) BS1 冒泡过程 FOR i=n TO 2 STEP 1 DO FOR j=1 TO i1 DO IF Kj

15、 Kj+1 THEN ( RjRj+1 ). 关键词的比较次数: (n-1)+(n-2)+1= (n-1)n/2经过一趟冒泡，可以把具有最大关键词的记录移至最后（第n个位置）。第i趟冒泡，把第i大记录放在第i个位置上。做n-1趟冒泡，就可以对所有记录排序。发生一次记录交换，反序对的个数减少一个。排序中可能出现如下情况：每趟比较中，在某位置后，没有记录交换；最后几趟没有交换。i = 1090216080512 1 2 3 4 5 6 7 8 9131407 1 2 3 4 5 6 7 8 9090216080512131407i = 2 1 2 3 4 5 6 7 8 9090216080512

16、1314073、冒泡排序算法的改进算法Bubble ( R，n ) Bubble1 终止位置初始化 BOUNDn /每趟冒泡关键词比较的终止位置 Bubble2 冒泡过程 WHILE BOUND0 DO ( t0 /每趟冒泡记录交换的最后位置 FOR j1 TO BOUND1 DO IF Kj Kj+1 THEN ( RjRj+1 . tj .) BOUNDt ) . 4、算法分析最好情形：记录的初始排列按关键词从小到大排好序时，此算法只执行一趟起泡，做 n-1 次关键词比较，不发生记录交换；最坏情形：算法执行了n-1趟起泡，第 i 趟 (1 i n) 做了 n- i 次关键词比较，执行了n-

17、i 次记录交换,此时，总的关键词比较次数和记录交换次数为(n-1)n/2一般情形 假定记录序列R1，R2，Rn所对应的关键词序列为A = K1，K2，Kn 令bj（1 j n）表示A中关键词第 j 小的记录左边大于它的关键词的个数，则文件 b1，b2，bn 称为A的反序表. A=07, 09, 02, 16, 08, 05, 12, 14, 13 B=2, 4, 0, 2, 0, 1, 2, 1 , 0 经过一趟冒泡后，记录的位置发生变化，反序表也发生变化。 定理7.1 设K1，K2，Kn是序列1，2，n的一个排列，b1，b2，bn是对应的反序表. 如果算法Bubble的一趟冒泡把K1, K2

18、, Kn改变为K1, K2, Kn, 那么从b1, b2, bn中把每个非零元素减1, 就得到了相应的反序表b1,b2,bn . A=07, 09, 02, 16, 08, 05, 12, 14, 13B=2, 4, 0, 2, 0, 1, 2, 1 , 0A=07, 02, 09, 08, 05, 12, 14, 13 , 16B=1, 3, 0, 1, 0, 0, 1, 0 , 0证明：如果Kj（1 j n）的左边有大于Kj的元素，设Km = max Kt | 1 t Kj ，则由算法Bubble知，Rm一定会与Rj交换，且Rj左边的其它元素不能与Rj交换。所以 如果Kj（1 j n）的左

19、边没有大于Kj的元素，即，则说明Rj左边的所有元素都小于Kj，从而一趟冒泡之后，Rj左边的任何元素都不与Rj交换（因为它们都小于Kj），所以仍然有 . 证毕。改进的冒泡排序算法的复杂性：5、冒泡排序算法总结时间复杂度：O(n2)（包括最坏和平均） .最好情况：当被排序文件初态为正序时，算法的时间复杂度为O(n) . 稳定性：冒泡排序是稳定的排序方法。辅助存储空间：O(1) . 为了进一步提高效率，可采用气泡上浮和下沉交替的方法。 第一趟第二趟第三趟第四趟79909090905679798888 90568879794885656563243235352732273232162716272788

20、163516163535444第七章 排序7.1 基本概念7.2 插入排序7.3 交换排序 冒泡排序 快速排序7.4 选择排序7.5 合并排序7.6 基于关键词比较的排序算法分析7.7 分布排序7.8 外排序7.3.2 分划交换排序 1962年，Hoare提出了分划交换排序，也叫快速排序 (Quick Sort)。算法的出发点： 1、通过交换反序对排序，一次记录交换使得文件中反序对的数目减少得最多; 2、一趟分划把一个记录直接放在其最终的位置上。1、快速排序的基本思想:任取待排序文件中的某个记录 (例如取第一个记录)作为基准，按照该记录的关键词大小，将整个文件分划为左右两个子文件： 左侧子文件

21、中所有记录的关键词都小于或等于基准记录的关键词 右侧子文件中所有记录的关键词都大于基准记录的关键词基准记录排在两个子文件中间。分别对两个子文件重复上述方法，直到所有记录都排在相应位置上为止。2、快速排序算法描述QuickSort ( R ) if (R的长度大于1) 将文件R分划为两个子文件LeftR 和 RightR; QuickSort ( LeftR );QuickSort ( RightR ); 将两个子文件 LeftR 和 RightR合并为一个文件R; 算法QSort(R, m, n) / 快速排序的递归算法QSort1 递归出口 /Rm为基准记录，Rn+1关键词最大 IF (mn

22、) THEN/ 长度大于1 ( im . jn+1 . KKm . WHILE ij DO ( ii+1 WHILE KiK DO jj1 . IF ij THEN Ri Rj ) RmRj . / 对 Rm.n 进行一趟快排，j为基准位置 IF mj-1 QSort ( R，m，j1 ) . / 对低子序列递归进行排序 IF j+1n QSort ( R，j+1，n ) ) / 对高子序列递归进行排序 (1) (2) (3) (4) (5) (6) (7) (8) (9) 70 73 69 23 93 18 11 68 100i=1j=9i=2 70 68 69 23 93 18 11 73

23、 100j=8 70 68 69 23 93 18 11 73 100i=3j=8 70 68 69 23 93 18 11 73 100i=4j=8 70 68 69 23 93 18 11 73 100i=5j=8 70 68 69 23 93 18 11 73 100i=5j=7 70 68 69 23 11 18 93 73 100i=5j=7 70 68 69 23 11 18 93 73 100i=7j=618 68 69 23 11 70 93 73 100WHILE ij DO ( ii+1 WHILE KiK DO jj1 . IF ij THEN Ri Rj ) RmRj

24、.快速排序一次分划过程示例:18 68 69 23 11 70 93 73j=6一趟结果 11 18 68 23 69 70 73 93j=5三趟结果11 18 23 68 69 70 73 93最终结果多趟快速排序过程示例 11 18 23 68 69 70 73 93四趟结果j=411 18 69 23 68 70 73 93j=2二趟结果j=8 18 68 69 23 11 70 93 73j=611 18 69 23 68 70 93 73j=2 11 18 68 23 69 70 93 73j=511 18 23 68 69 70 73 93最终结果 11 18 23 68 69 7

25、0 73 93j=8j=4算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分划程序段 IF mj-1 QSort ( R，m，j1 ) .L1: IF j+1n QSort ( R，j+1，n ). L2: ) 栈 L0 1 8 6 L m n j L1 1 5 2 L2 3 5 5 L1 3 4 4 18 68 69 23 11 70 93 73j=611 18 69 23 68 70 93 73j=2 11 18 68 23 69 70 93 73j=511 18 23 68 69 70 73 93最终结果 11 18 23

26、 68 69 70 73 93j=8j=4栈 L0 1 8 6 L m n j L1 1 5 2 L2 3 5 5 算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分划程序段 IF mj-1 QSort ( R，m，j1 ) .L1: IF j+1n QSort ( R，j+1，n ). L2: ) 18 68 69 23 11 70 93 73j=611 18 69 23 68 70 93 73j=2 11 18 68 23 69 70 93 73j=511 18 23 68 69 70 73 93最终结果 11 18 23

27、68 69 70 73 93j=8j=4栈 L0 1 8 6 L m n j L1 1 5 2 算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分划程序段 IF mj-1 QSort ( R，m，j1 ) .L1: IF j+1n QSort ( R，j+1，n ). L2: ) 18 68 69 23 11 70 93 73j=611 18 69 23 68 70 93 73j=2 11 18 68 23 69 70 93 73j=511 18 23 68 69 70 73 93最终结果 11 18 23 68 69 70 7

28、3 93j=8j=4栈 L0 1 8 6 L m n j 算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分划程序段 IF mj-1 QSort ( R，m，j1 ) .L1: IF j+1n QSort ( R，j+1，n ). L2: ) 18 68 69 23 11 70 93 73j=611 18 69 23 68 70 93 73j=2 11 18 68 23 69 70 93 73j=511 18 23 68 69 70 73 93最终结果 11 18 23 68 69 70 73 93j=8j=4栈 L0 1 8

29、6 L m n j L2 7 8 8 算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分划程序段 IF mj-1 QSort ( R，m，j1 ) .L1: IF j+1n QSort ( R，j+1，n ). L2: ) 18 68 69 23 11 70 93 73j=611 18 69 23 68 70 93 73j=2 11 18 68 23 69 70 93 73j=511 18 23 68 69 70 73 93最终结果 11 18 23 68 69 70 73 93j=8j=4栈 L0 1 8 6 L m n j

30、算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分划程序段 IF mj-1 QSort ( R，m，j1 ) .L1: IF j+1n QSort ( R，j+1，n ). L2: ) 18 68 69 23 11 70 93 73j=611 18 69 23 68 70 93 73j=2 11 18 68 23 69 70 93 73j=511 18 23 68 69 70 73 93最终结果 11 18 23 68 69 70 73 93j=8j=4栈空 L m n j 算法QSort(R，m，n) IF m n THEN

31、( im . jn+1 . KKm . QSort1；/一次分划程序段 IF mj-1 QSort ( R，m，j1 ) .L1: IF j+1n QSort ( R，j+1，n ). L2: ) 3、算法分析算法Qsort是递归的算法，其递归树如图所示。一个结点表示一次递归调用。快速排序的趟数取决于递归树的深度。每次分划后，基准记录的左右子序列长度相同，是最理想的情况。7093731869682311一次分划过程(R,m,n)，有两个记录与基准记录比较两次，其余的记录和基准记录各比较一次。关键词的比较次数为n-m+2。 (1) (2) (3) (4) (5) (6) (7) (8) (9)

32、70 73 69 23 93 18 11 68 100i=1j=9i=2 70 68 69 23 93 18 11 73 100j=8 70 68 69 23 93 18 11 73 100i=3j=8 70 68 69 23 93 18 11 73 100i=4j=8 70 68 69 23 93 18 11 73 100i=5j=8 70 68 69 23 93 18 11 73 100i=5j=7 70 68 69 23 11 18 93 73 100i=5j=7 70 68 69 23 11 18 93 73 100i=7j=618 68 69 23 11 70 93 73 1004、

33、快速排序算法总结时间复杂度: O(n2)/最坏 . 时间复杂度: O(nlog2n) /最好和平均辅助空间： O(log2n) .稳定性：快速排序是不稳定的排序方法。快速排序方法对于 n 较大的平均情况而言，是目前内部排序中最好、最快的排序方法。但当 n 很小时，这种排序方法往往比其它简单排序方法还慢。第七章 排序7.1 基本概念7.2 插入排序7.3 交换排序7.4 选择排序 直接选择排序 堆排序7.5 合并排序7.6 基于关键词比较的排序算法分析7.7 分布排序7.8 外排序 7.4 选择排序 思想：对待排序的文件进行n次选择操作，其中第i次选择第i小(或大)的记录放在第i(或n-i+1)

34、的位置上。 直接选择排序、堆排序7.4.1 直接选择排序 1、直接选择排序思想： 选择第 i （i = 1,2, , n-1）大的记录的具体办法：在剩余的n-i+1个记录中进行一趟比较，确定出第i大记录，放在第n-i+1位置上。 17 78 6 54 34 38 17 38 6 54 34 78 17 38 6 34 54 782、直接选择排序算法算法 SSort (R, n) /待排序文件(R1,R2,Rn)SS1 排序 FOR j=n TO 2 STEP 1 DO ( /从1到j找最大元素的下标t t1 . FOR i2 TO j DO IF KtKi THEN ti RjRt ) / 将

35、Rt放到第j个位置上 (1) (2) (3) (4) (5) (6) i t 21 25 49 25* 16 08 2 1 初始序列 2 算法 SSort（R，n） FOR j=n TO 2 STEP -1 DO ( t1 . FOR i2 TO j DO IF Kt Ki THEN ti Rj Rt) 21 25 49 25* 16 08 3 2 21 25 49 25* 16 08 4 3 21 25 49 25* 16 08 5 3 21 25 49 25* 16 08 6 3 21 25 08 25* 16 49 21 25 49 25* 16 08一趟直接选择排序过程示例多趟直接选择

36、排序过程示例 (1) (2) (3) (4) (5) (6) t 1 21 25 08 25* 16 49 2 2 21 16 08 25* 25 49 4 3 21 16 08 25* 25 49 1 5 08 16 21 25* 25 49 21 25 49 25* 16 08 3 初始序列 4 08 16 21 25* 25 49 2 3、算法分析直接选择排序的关键词比较次数与记录的初始排列无关。假定整个待排序文件有 n 个记录，则第 i 趟选择所需的比较次数是 n-i 次。总的关键词比较次数为 (n-1)+(n-2)+1= (n-1)n/2记录交换次数是选择的趟数: n-1. 4、直接

37、选择排序算法总结时间复杂度: O(n2)（包括最好、最坏和平均） . 稳定性：不稳定的排序方法。辅助空间： O(1) . 优点：简单、书写容易第七章 排序7.1 基本概念7.2 插入排序7.3 交换排序7.4 选择排序 直接选择排序 堆排序7.5 合并排序7.6 基于关键词比较的排序算法分析7.7 分布排序7.8 外排序7.4.2 堆排序1、堆排序的原理 选择排序的关键：找最大记录 堆排序：利用淘汰赛的方式寻找当前序列中的最大记录淘汰赛的思想：对n个选手，两两比赛，得到 n/2 个优胜者，作为第一轮的结果；然后对这n/2个选手，再两两比赛，如此重复，直到选出一个冠军。满二叉树的叶结点，存放待排

38、序记录的关键词。如果 n 不是2的 k 次幂，则让叶结点数补足到满足 2k-1 n 2k 的2k个。非叶结点是关键词两两比较的结果，根结点的关键词最大。63Winner 49631663492521254925*160863tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14比赛树的概念每次两两比较的结果是把关键词大者作为优胜者上升到双亲结点，称这种树为比赛树。位于最底层的叶结点叫做比赛树的外结点，非叶结点称为比赛树的内结点。每个结点除了存放记录的关键词外，还存放了此对象在满二叉树中的序号。比赛树最顶层是树的根，表示最后选择出来的具有最大关键

39、词的记录。形成初始比赛树（最大关键词上升到根）得到最大记录R763Winner 49631663492521254925*160863tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14R7利用比赛树的排序第1步将剩余6个记录，调整为新的比赛树得到第2大记录R649Winner 491616-492521254925*1608-tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14R6利用比赛树的排序第2步将剩余6个记录，调整为新的比赛树得到第2大记录R625Winner 251616-25*

40、25212525*1608-tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14R5利用比赛树的排序第3步-上述过程重复进行结果全部输出时，比赛树的状态08Winner 0808-08-tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14R1-2、堆的定义如果有一个关键码的集合Kk1,k2,kn把它的所有元素按完全二叉树的顺序(数组)存储方式存放在一个一维数组中。并且满足 ki k2i且ki k2i+1 / 小根堆 或 ki k2i且ki k2i+1 / 大根堆 94937591854451

41、1848581034例 1 2 3 4 5 6 7 8 9 10 11 12 94 93 75 91 85 44 51 18 48 58 10 34堆的定义完全二叉树的数组表示 Ki K2i & Ki K2i+1完全二叉树的数组表示 Ki K2i & Ki K2i+1 3、堆排序算法设数组R存放堆，则R1是关键词最大的记录，将R1和Rn互换，使得最大记录放在Rn的位置。调整R1，Rn-1，使之成为新堆，则R1是其中最大者，再交换R1与Rn-1，使Rn-1中放入次最大记录。再对R1，R2，Rn-2调整，使之成为新堆，再进行类似的交换，上述操作反复进行，直到调整范围只剩下一个记录R1为止。此时，R

42、1是n个记录中最小的，且数组Rn中的记录已经按从小到大排列了。堆排序算法的粗略描述： （l）建立包含Kl，K2，Kn的堆； （2）FOR in TO 2 STEP 1 DO （R1Ri 重建包含K1，K2，Ki1的堆 ）需解决的两个问题： 如何建堆 如何调整新堆问题 初始建堆: 将以序号n/2，n/21 , 1的结点为根的子树都调整为堆即可。 例 关键词序列（42,13,91,23,24,16,05,88)。4213912324160588421391232416058842139188241605234213918824160523421391882416052342889113241605

43、234288911324160523428891232416051342889123241605139188422324160513初始建堆过程图形说明：9188422324160513问题重建堆：R1与Ri交换后，只有R1与其左右儿子不满足堆的性质。13884223241605914288912324160513884223241605428891232416058813422324160542889123241605881342232416054288912324160588244223131605428891232416058824422313160591堆排序过程图形说明：428891

44、232416051391884223241605134288912324160513918842232416051342889123241605131388422324160591428891232416051313884223241605914288912324160513881342232416059142889123241605138813422324160591428891232416051388244223131605914288912324160513882442231316059142889123241605138824422313160591428891232416051305

45、2442231316889142889123241605134224162313058891堆排序过程：4288912324160513052416231342889142889123241605132423160513428891堆排序过程：42889123241605134224162313058891堆排序过程：428891232416051324231605134288914288912324160513132316052442889142889123241605132313160524428891堆排序过程：42889123241605132313160524428891428891

46、2324160513051316232442889142889123241605131613052324428891堆排序过程：428891232416051316130523244288914288912324160513051316232442889142889123241605131305162324428891堆排序过程：428891232416051313051623244288914288912324160513051316232442889142889123241605130513162324428891算法Restore（R，f，e）/ 建堆R1 初始化 jf R2 建堆 WH

47、ILE je/2 DO (IF(2j e)AND(K2j Kj THEN（RmRj . jm ） ELSE je ）42139123241605884213912324160588j=4HS1 初始建堆FOR in2 TO 1 STEP 1 DORestore（R，i，n） 42139188241605234213918824160523j=842139188241605234213918824160523j=342139188241605234213918824160523j=242889113241605234288911324160523j=44288911324160523428891

48、1324160523j=442889123241605134288912324160513j=842889123241605134288912324160513j=191884223241605139188422324160513j=3算法HeapSort ( R，n ) / 堆排序算法 HS1 初始建堆 FOR in2 TO 1 STEP 1 DO Restore（R，i，n） HS2 排序 FOR in TO 2 STEP 1 DO ( R1Ri . Restore ( R，1，i1 ) ) 4288912324160513918842232416051342889123241605139

49、188422324160513428891232416051313884223241605914288912324160513138842232416059142889123241605138813422324160591428891232416051388134223241605914288912324160513882442231316059142889123241605138824422313160591重建堆算法的时间复杂度为 O(log2n)138842232416059188244223131605914、堆排序算法总结时间复杂度: 最好、最坏和平均情况相同 重建堆算法为 O(lo

50、g2n) 堆排序算法为O(nlog2n) . 稳定性：堆排序是不稳定的排序方法。辅助存储空间： O(1) . 492525*211608012345082525*16214902543149 25 21 25* 16 0808 25 21 25* 16 49交换 0 号与 5 号对象,5 号对象就位初始最大堆2525*082116490123451625*0825214902543125 25* 21 08 16 4916 25* 21 08 25 492525*082116490123451625*0825214902543125 25* 21 08 16 4916 25* 21 08 25

51、 49交换 0 号与 4 号对象,4 号对象就位从 0 号到 4 号 重新调整为最大堆25*1608212549012345081625*25214902543125* 16 21 08 25 4908 16 21 25* 25 49交换 0 号与 3 号对象,3 号对象就位从 0 号到 3 号 重新调整为最大堆211625*082549012345081625*25214902543121 16 08 25* 25 4908 16 21 25* 25 49交换 0 号与 2 号对象,2 号对象就位从 0 号到 2 号 重新调整为最大堆堆存在于顺序线性表（数组）中160825*21254901

52、2345081625*25214902543116 08 21 25* 25 4908 16 21 25* 25 49交换 0 号与 1 号对象,1 号对象就位从 0 号到 1 号 重新调整为最大堆第七章 排序7.1 基本概念7.2 插入排序7.3 交换排序7.4 选择排序7.5 合并排序7.6 基于关键词比较的排序算法分析7.7 分布排序7.5 合并排序1、合并合并(归并)：把两个或多个有序文件合并成一个单一的有序文件。合并的基本思想：设两个有序表A和B的记录个数(表长)分别为 al 和 bl，变量 i 和 j 分别是表A和表B的当前检测指针。设表C是归并后的新有序表，变量 k 是它的当前存放指针。08 21 25 25* 49 62 72 93 16 37 54 l m m+1 ni j08 16 21 25 25* 37 49 54 62 72 93 l nkC当