数据结构课件：14 第七章 排序

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

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

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

4、先应该从算法的时间代价和空间代价出发考虑（即应用环境中的CPU处理能力、存储容量等硬件约束和系统响应时间等处理效率要求），有些情况下也需要考虑算法实现的复杂程度（从软件工程角度考虑软件开发成本）。一般情况下以考虑时间代价为主。 排序算法有多种分类方法:从元素的存储设备角度可分为内排序（在内存中进行）和外排序（在外存储器上进行）。按对关键词的操作可分为基于关键词比较的排序算法和分布排序算法。按时间代价分类：平方阶排序算法，它们一般都比较简单，特点是容易实现，但时间复杂度相对较高，最坏情况下时间复杂度一般为O(n2)；线性对数阶算法，以分治策略算法为主，最坏情况下时间复杂度一般为O(nlog(n)

5、. 第七章 排序7.1 基本概念7.2 插入排序 直接插入排序 希尔排序7.3 交换排序7.4 选择排序7.5 合并排序7.6 基于关键词比较的排序算法分析7.7 分布排序7.8 外排序7.2 插入排序 例： 原有序表：(9 15 23 28 37) 20 找插入位置 : (9 15 23 28 37) 20 新有序表: (9 15 20 23 28 37)插入排序思想 基于插入操作所完成的排序。 插入:将一个记录插入到已排好序的有序表中，从而得到一个新的记录数增一的有序表。7.2.1 直接插入排序算法1. 基本思想 待排序记录 R1，R2， ，Rn1, Rn 第一步：R1 第二步：(R1 )

6、, 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 移动次数： 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. ) 算法Ins

7、ertSortA( 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 ) FOR js+1 TO e DO ( ij-1KKj . RRj . WHILE KKi DO ( Ri+1Ri ii-l ) Ri+1R ) k1k2k3k4k0k587246j 24678872462 27 8464 7 82463 247 865 3. 算法分析 设dj是Rj左边关键词大于Kj的记录个数，则算法InsertSortA中关键词的比

8、较次数为： 记录的移动次数为 最好情况下，排序前记录已经按关键词从小到大有序排列，即dj=0。每趟只需与前面的有序部分的最后一个记录的关键词比较 1 次，记录移动 2 次，总的关键词比较次数为 n-1，记录移动次数为 2(n-1)。最坏情况下：第i趟时，第i个记录前面所有记录的关键词都比第i个记录的关键词大，即dj=j-1 总的关键词比较次数： 记录移动次数： 平均情况下，若待排序文件中记录所有可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键词比较次数和记录移动次数分别为 因此，直接插入排序的时间复杂度为 O(n2)。 平均情况下，考察分析 的期望值。对于序列K1

9、，K2，Kn ，如果1ijn，且KiKj，则称(Ki , Kj)为上述序列的一个反序对。实际上， 正好是序列K1，K2，Kn的反序对个数。 则有反序对的平均个数 = 0+ (0+1)/2+ (0+1+2)/3+ + (0+1+2+n1)/n = 0+1/2+2/2+ +( n1)/n = n(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 选

11、择排序7.5 合并排序7.6 基于关键词比较的排序算法分析7.7 分布排序7.8 外排序 7.2.2 希尔(shell)排序1、希尔排序（渐减增量排序法）思想： 1959年Donald L. Shell提出Shell排序法 ，源自对直接插入算法的改进. 把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。 例 将十个数进行希尔排序的示例。 0 1 2 3 4 5 6 7 8 9 36 25 48 12 65 25 43 58 76 32下标d1=525434858127625363265 25

12、 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 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算法的性能与所选取的分组长度序列有很大关

13、系。只对特定的待排序记录序列，可以准确地估算关键词的比较次数和对象移动次数。想要弄清关键词比较次数和记录移动次数与增量选择之间的关系，并给出完整的数学分析，至今仍然是数学难题。Shell算法的性能与所选取的分组长度序列有很大关系。前面介绍的实例是最简单的分组长度序列，即n/2i，最坏情况下时间复杂度为O(n2). 一般实际应用中选择2.2作为递减因子效果更好，而不是2 . 如果选择2k-1为分组长度序列，最坏情况下能达到 . V. Pratt于1969年证明如下结论：如果渐减增量序列取值为形如 且小于n的所有自然数的集合（即 ），则Shell算法的时间复杂度为 . Knuth利用大量的实验统计

14、资料得出，当 n 很大时，关键词平均比较次数和记录平均移动次数大约在 n1.25 到 1.6n1.25 的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。不稳定的排序算法第七章 排序7.1 基本概念7.2 插入排序7.3 交换排序 冒泡排序 快速排序7.4 选择排序7.5 合并排序7.6 基于关键词比较的排序算法分析7.7 分布排序7.8 外排序 7.3 交换排序反序对：对于序列K1, K2, , Kn, 若1iKj , 则称(Ki,Kj)为上述序列的一个反序对。交换排序的思想：交换文件中存在的反序对，直到不存在反序对为止。交换排序包括：冒泡排序、分划交换排序（快速排序）。7.

15、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 Kj+1 THEN ( RjRj+1 ). 关键词的比较次

16、数: (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 90902160805121314073、冒泡排序算法的改进算法Bubble ( R，

17、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-i 次记录交换,此时，总的关键词比较次数和记录交换次数为(n

18、-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, Kn改变为K1, K2, Kn, 那么从b1, b2,

19、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）的左边没有大于Kj的元素，即，则说明Rj左边的所有元素都小于Kj

20、，从而一趟冒泡之后，Rj左边的任何元素都不与Rj交换（因为它们都小于Kj），所以仍然有 . 证毕。推论7.1 算法Bubble的冒泡趟数A=1+max b1，b2，bn；记录交换次数B=nbi ；关键词的比较次数C=ACi ，其中Ci等于第i趟冒泡时的BOUND减1. A、B、C分布较为复杂，平均情形复杂度的计算较为复杂(略)； 改进的冒泡排序算法的复杂性：5、冒泡排序算法总结时间复杂度：O(n2)（包括最坏和平均） .最好情况：当被排序文件初态为正序时，算法的时间复杂度为O(n) . 稳定性：冒泡排序是稳定的排序方法。辅助存储空间：O(1) . 为了进一步提高效率，可采用气泡上浮和下沉交替的

21、方法。 第一趟第二趟第三趟第四趟79909090905679798888 90568879794885656563243235352732273232162716272788163516163535444第七章 排序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、一趟分划把一个记录

22、直接放在其最终的位置上。1、快速排序的基本思想:任取待排序文件中的某个记录 (例如取第一个记录)作为基准，按照该记录的关键词大小，将整个文件分划为左右两个子文件： 左侧子文件中所有记录的关键词都小于或等于基准记录的关键词 右侧子文件中所有记录的关键词都大于基准记录的关键词基准记录排在两个子文件中间。分别对两个子文件重复上述方法，直到所有记录都排在相应位置上为止。2、快速排序算法描述QuickSort ( R ) if (R的长度大于1) 将文件R分划为两个子文件LeftR 和 RightR; QuickSort ( LeftR );QuickSort ( RightR ); 将两个子文件 Le

23、ftR 和 RightR合并为一个文件R; (1) (2) (3) (4) (5) (6) (7) (8) (9)70 73 69 23 93 18 11 68 100 i(第一个大于) (第一个小于) j70 68 69 23 93 18 11 73 10070 68 69 23 11 18 93 73 10070 68 69 23 11 18 93 73 10018 68 69 23 11 70 93 73 100算法QSort(R, m, n) / Hoare快速排序的递归算法QSort1 递归出口 /Rm为基准记录，Rn+1关键词最大 IF (mn) THEN ( im . jn+1

24、. KKm . WHILE ij DO ( ii+1 WHILE KiK DO jj1 . IF ij THEN Ri Rj ) RmRj . QSort ( R, m, j1 ) . 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 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

25、 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 .快速排序一次分划过程示例:18 68 69 23 11 70 93 73j=6一趟结果 11 18 68 23 69 70 73 93j=5三趟结果11 18 23 68

26、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 70 73 93j=8j=4算法QSort(R，m，n) IF m Kn THEN Rm+1Rn . IF KmKn THEN RmRn . IF Km+1Km THEN Rm

27、+1Rm . Part2 分划开始 im jn+1 KKm .Part3 用Km分划文件( Rm，Rm+1，Rn ) WHILE ij DO ( ii1 WHILE KiK DO ii1 jj 1 WHILE KjK DO jj1 . IF ij THEN RiRj ) RmRj 4、快速排序算法总结时间复杂度: O(n2)/最坏 . 时间复杂度: O(nlog2n) /最好和平均辅助空间： O(log2n) .稳定性：快速排序是不稳定的排序方法。快速排序方法对于 n 较大的平均情况而言，是目前内部排序中最好、最快的排序方法。但当 n 很小时，这种排序方法往往比其它简单排序方法还慢。第七章 排

28、序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)的位置上。 直接选择排序、堆排序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

29、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 ) / 将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 n DO IF Kt Ki THEN ti Ri Rt) 21 2

30、5 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 08 25* 16 49 21 25 49 25* 16 08一趟直接选择排序过程示例多趟直接选择排序过程示例 (1) (2) (3) (4) (5) (6)it 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

31、 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、直接选择排序算法总结时间复杂度: O(n2)（包括最好、最坏和平均） . 稳定性：不稳定的排序方法。辅助空间： O(1) . 优点：简单、书写容易第七章 排序7.1 基本概念7.2 插入排序7.3 交换排序7.4 选择排序 直接选择排序 堆排序7.5 合并排序7.6 基于关键词比

32、较的排序算法分析7.7 分布排序7.8 外排序7.4.2 堆排序1、堆排序的原理 选择排序的关键：找最大记录 堆排序：利用淘汰赛的方式寻找当前序列中的最大记录淘汰赛的思想：对n个选手，两两比赛，得到 n/2 个优胜者，作为第一轮的结果；然后对这n/2个选手，再两两比赛，如此重复，直到选出一个冠军。满二叉树的叶结点，存放待排序记录的关键词。如果 n 不是2的 k 次幂，则让叶结点数补足到满足 2k-1 n 2k 的2k个。非叶结点是关键词两两比较的结果，根结点的关键词最大。63Winner 49631663492521254925*160863tree7 tree8 tree9 tree10 t

33、ree11 tree12 tree13 tree14比赛树的概念每次两两比较的结果是把关键词大者作为优胜者上升到双亲结点，称这种树为比赛树。位于最底层的叶结点叫做比赛树的外结点，非叶结点称为比赛树的内结点。每个结点除了存放记录的关键词外，还存放了此对象在满二叉树中的序号。比赛树最顶层是树的根，表示最后选择出来的具有最大关键词的记录。形成初始比赛树（最大关键词上升到根）得到最大记录R763Winner 49631663492521254925*160863tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14R7利用比赛树的排序第1步将剩余6个记

34、录，调整为新的比赛树得到第2大记录R649Winner 491616-492521254925*1608-tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14R6利用比赛树的排序第2步上述过程重复进行结果全部输出时，比赛树的状态08Winner 0808-08-tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14R1-2、堆的定义 完全二叉树中的任意结点的关键词大于等于它的两个儿子结点的关键词。 我们把这样的数据结构称为堆(极大堆)。 极大(大根)堆 极小(小根)堆9493759185445

35、11848581034例 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为止。此时，

36、R1是n个记录中最小的，且数组Rn中的记录已经按从小到大排列了。堆排序算法的粗略描述： （l）建立包含Kl，K2，Kn的堆； （2）FOR in TO 2 STEP 1 DO （R1Ri 重建包含K1，K2，Ki1的堆 ）需解决的两个问题： 如何建堆 如何调整新堆问题重建堆：R1与Ri交换后，只有R1与其左右儿子不满足堆的性质。138842232416059142889123241605138842232416054288912324160588134223241605428891232416058813422324160542889123241605882442231316054288912

37、32416058824422313160591重建堆算法算法Restore(R，f，e) R1 初始化 jf R2 建堆 WHILE je/2 DO /判断j是否为内结点 ( IF (2je) AND (K2jKj THEN（RmRj . jm . ） ELSE je . ） 重建堆算法的时间复杂度为 O(log2n)问题 初始建堆: 将以序号n/2，n/21 , 1的结点为根的子树都调整为堆即可。 例 关键词序列（42,13,91,23,24,16,05,88)。4213912324160588堆排序算法算法HeapSort ( R，n ) HS1 初始建堆 FOR in2 TO 1 STE

38、P 1 DO Restore（R，i，n） HS2 排序 FOR in TO 2 STEP 1 DO ( R1Ri . Restore ( R，1，i1 ) ) 堆排序过程关键字序列(42,13,91,23,24,16,05,88)42889123241605139188422324160513428891232416051388244223131605911、建立初始堆2、交换，并重建堆42889123241605134224162313058891428891232416051324231605134288914288912324160513231316052442889142889123

39、24160513161305232442889142889123241605131305162324428891428891232416051305131623244288914、堆排序算法总结时间复杂度: 最好、最坏和平均情况相同 重建堆算法为 O(log2n) 堆排序算法为O(nlog2n) . 稳定性：堆排序是不稳定的排序方法。辅助存储空间： O(1) . 492525*211608012345082525*16214902543149 25 21 25* 16 0808 25 21 25* 16 49交换 0 号与 5 号对象,5 号对象就位初始最大堆2525*082116490123

40、451625*0825214902543125 25* 21 08 16 4916 25* 21 08 25 492525*082116490123451625*0825214902543125 25* 21 08 16 4916 25* 21 08 25 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*08254901

41、2345081625*25214902543121 16 08 25* 25 4908 16 21 25* 25 49交换 0 号与 2 号对象,2 号对象就位从 0 号到 2 号 重新调整为最大堆堆存在于顺序线性表（数组）中160825*212549012345081625*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

42、.8 外排序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当 i 和 j 都在两个表的表长内变化时，根据Ai与Bj的关键词大小，依次把关键词小的对象排放到新表Ck中；当 i 与 j 中有一个已经超出表长时，将另

43、一 个表中的剩余部分照抄到新表Ck中。合并算法描述： 算法Merge (R，t，m，n . X) M1 初始化指针 it jm1 k1 M2 比较 i和 j所指记录 WHILE（im） AND（jn） DO （IF KiKj THEN（XkRi ii1 . ） ELSE（XkRj jj1 . ） kk+1 . ） M3 复制余留记录 WHILE (im) DO (XkRi . ii1. kk+1.) WHILE (jn) DO (XkRj . jj1. kk+1.) Merge算法分析：关键词比较次数n-t+1记录移动次数为 n-t+12、合并排序：两路合并：一次合并两个文件合并排序：利用两路

44、合并过程进行排序。 基本思想：设初始文件有 n 个记录，首先把它看成是 n 个长度为 1 的有序子序列 (合并项)，先做两两合并，得到 n / 2 个长度为 2 的合并项 (如果 n 为奇数，则最后一个有序子序列的长度为1)；再做两两合并，如此重复，最后得到一个长度为 n 的有序序列。开始255748371292863325,5737,4812,9233,86第一次合并25,37,48,5712,33,86,92第二次合并12,25,33,37,48,57,86,92第三次合并合并排序过程示例算法Merge (R, t, m, n. X)：合并算法，假定文件(Rt, Rt1, ,Rm)和(Rm

45、1, , Rn)已经有序，合并这两个文件，得到排序好的新文件(Xt, Xt1, , Xn)； 算法MPass (R, n, 1engthX)：一趟合并算法，将文件R中长度为length的所有子文件两两合并到文件X中，n是R记录数，该函数中调用了Merge()；算法MSort (R，n) ：合并排序算法，该函数通过调用函数Mpass()，实现两路合并排序。一趟合并MPass (R, n, 1ength. X)的基本思想设文件R中的n个记录已经分为一些长度为len的子文件，将这些子文件两两合并，合并成一些长度为2len的子文件，结果放到X中。如果n不是2len的整数倍，则一趟合并到最后，可能遇到两

46、种情形： 剩下一个长度为len的子文件和另一个长度不足len的子文件，可用一次merge算法，将它们合并成一个长度小于2len的子文件。 只剩下一个子文件，其长度小于或等于len，可将它直接抄到X中。一趟归并算法算法MPass(R, n, 1engthX) MP1 初始化 i1 MP2 合并相邻的两个长度为length的子文件 WHILE in 2*length + 1 DO ( Merge(R, i, ilength-1, i2*length-1. X ) . ii2*length ) MP3 处理余留的长度小于2*length的子文件 IF i+length1n THEN Merge(R,

47、 i, i+length-1, n. X) ELSE FOR j=i TO n DO XjRj 归并排序算法212525*25*936272083716544921254962930872163754212525*490862729316375408082116252125*254925*623772499354163754627293len=1len=2len=4len=8len=16两路合并排序算法算法MSort(R, n) /X是辅助文件，其记录结构与R相同MS1 初始化 length1 MS2 交替合并 WHILE lengthn DO （ MPass(R, n, length. X)

48、. length2*length MPass(X, n, length. R). length2*length） 3、算法分析一趟两路合并MPass，要调用Merge函数n/(2*len) O(n/len)次，而Merge的复杂度为O(len). 所以, MPass的复杂度为O(n).合并排序算法MSort，调用MPass正好log2n 次，所以算法总的时间复杂度为O(nlog2n)。辅助存储空间：O(n)归并排序是稳定的排序方法。 通过实例仔细分析合并排序算法，不难发现它的两个缺点：(1) 当数据集非常小时，比如只有2个元素，仍然采用分治策略，影响效率。(2) Merge算法基于元素移动，当

49、元素比较大时会比较费时。针对这两个问题的解决办法：(1) 对于非常小的数据集，以及前几次归并动作，调用直接插入排序算法。(2) 将数组存储改为链表存储，这样记录移动就变为指针移动了。第七章 排序7.1 基本概念7.2 插入排序7.3 交换排序7.4 选择排序7.5 合并排序7.6 基于关键词比较的排序算法分析7.7 分布排序7.8 外排序 7.6.1 各种内排序方法的比较 排序方法最好时间平均时间最坏时间稳定性辅助空间直接选择O(n2)O(n2)O(n2)不稳定O(1)希尔 O(n1.25) 不稳定O(1)直接插入O(n)O(n2)O(n2)稳定O(1) 冒泡O(n)O(n2)O(n2)稳定O

50、(1)快速O(nlog2n)O(nlog2n)O(n2)不稳定O(log2n)堆O(nlog2n)O(nlog2n)O(nlog2n)不稳定O(1)归并O(nlog2n)O(nlog2n)O(nlog2n)稳定O(n) 7.6.2 排序下界下界：如果一个领域问题的输入规模为n，则“该领域问题的算法的时间复杂性下界为L(n)”含义是：不存在解该领域问题的算法，它的时间复杂性小于L(n) . 排序下界: O(nlog2n)任何基于关键词比较的排序算法，其关键词比较次数至少为 nlog2n。第七章 排序7.1 基本概念7.2 插入排序7.3 交换排序7.4 选择排序7.5 合并排序7.6 基于关键词

51、比较的排序算法分析7.7 分布排序7.8 外排序7.7 分布排序当预先知道待排序关键词的一些知识时，比如其分布范围，就能构造出非基于关键词比较的排序算法，而且有些算法能在最坏情况下达到线性时间。如扑克牌的排序、英文单词的排序等，可采用基于关键词的数字性质的分“桶”排序方法。 “桶”个数的选择是根据关键词的数字性质，而且“桶”的个数将直接影响排序算法的效率。两种分布排序：基数分布和值分布。 7.7.1 基数分布假定记录 R1，R2，Rn相应的关键词K1，K2，Kn都有如下的表示形式: Ki = (Ki , p，Ki , p1，Ki , 1)，且对于每个t(1t p)都有0 Ki , tr，r为基

52、数.基数分布排序是基于关键词的表示，按其字典序由小到大排列。其中，字典序规定如下： Ki = (Ki , p，Ki , 1)Kj = (Kj , p，Kj , 1)当且仅当存在tp，使得当st时Ki, s= Kj, s 而 Ki , tKj , t 基数分布排序最高次序位法：先按高位分桶，然后桶内进行排序 如：英文单词，扑克牌最低次序位法 ：首先按最低位排序，然后按下一个次低位排序，最后按最高位排序 。1221630281016*20618按最低位分配r0 r1 r2 r3 r4 r5 r6 r7 r8 r9f0 f1 f2 f3 f4 f5 f6 f7 f8 f91221630281016*206183010201221616*62818r0 r1 r2 r3 r4 r5 r6 r7 r8 r9f0 f1 f2 f3 f4 f5 f6 f7 f8 f91816*