第七章_排序(新)

1、1数据结构国家精品课程2022-5-26第七章第七章 排排 序序2数据结构国家精品课程2022-5-263数据结构国家精品课程2022-5-267.1 排序问题的基本概念排序问题的基本概念l文件文件：给定待排序的给定待排序的 n 个数据对象个数据对象，R1，R2，Rn，这些，这些数据对象为记录，并称这数据对象为记录，并称这 n 个记录的集合为一个文个记录的集合为一个文件；件；l关键词关键词通常通常数据对象包括多个数据对象包括多个属性域属性域，可将其中的一个属性，可将其中的一个属性域作为排序的依据，称其为关键词域。上述域作为排序的依据，称其为关键词域。上述 n 个记个记录的录的关键词分别是关键词

2、分别是 K1，K2，Kn；l排序排序按规定按规定的的顺序顺序，以关键词为依据，对一个文件中的诸，以关键词为依据，对一个文件中的诸记录进行记录进行排列排列的过程的过程。Struct student char name10; int score; int ID;4数据结构国家精品课程2022-5-26排序算法的度量指标排序算法的度量指标:l 时间时间开销开销( (时间复杂性时间复杂性) )是是衡量算法好坏的最重要标志。可用算法执行中衡量算法好坏的最重要标志。可用算法执行中关键词的比较次数关键词的比较次数与与数据的移动次数数据的移动次数来衡量。来衡量。l 空间复杂性空间复杂性主要主要考察排序考察排序

3、过程占用存储空间过程占用存储空间的大小。的大小。l 排序算法的排序算法的稳定性稳定性如果两如果两个对象个对象ri和和rj, 其关键词相同其关键词相同, 且且在在排序前排序前ri在在rj的前面，若排序后，的前面，若排序后，ri仍仍在在rj的前面，的前面，则称这个排序方法是稳定的，否则称这个排序方则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。法是不稳定的。5数据结构国家精品课程2022-5-26排序排序算法算法的的分类分类l 从存储设备从存储设备角度可分为角度可分为内内排序和外排序排序和外排序. 在排序过程在排序过程中中, 所所有待有待排序记录排序记录都在都在内存中内存中, 称为称为内内

4、排序排序; 当当输入输入文件所文件所占存储空间大到计算机内存不能占存储空间大到计算机内存不能容纳容纳, 排序排序过过程必需借助外存来完成，这时的排序就称为程必需借助外存来完成，这时的排序就称为外外排序排序.l 按对关键词的按对关键词的操作操作可可分为分为基于关键词比较的基于关键词比较的排序排序和和分布分布排序排序。l 按时间按时间代价代价平方平方阶排序算法阶排序算法，它们一般，它们一般都较都较简单简单，易，易于于实现实现，但，但时间复杂性较高时间复杂性较高，最坏，最坏情况时间复杂性为情况时间复杂性为 O(n2)；线性线性对数阶算法对数阶算法，以分治策略算法为主，最坏，以分治策略算法为主，最坏情

5、况时情况时间复杂性为间复杂性为 O(nlogn). 6数据结构国家精品课程2022-5-26 排序算法很多，在解决特定问题时应如何选择排序排序算法很多，在解决特定问题时应如何选择排序算法呢？算法呢？l首先应该从算法的首先应该从算法的时间代价和空间代价时间代价和空间代价出发考虑（出发考虑（即应用环境中的即应用环境中的CPU处理能力、存储容量等硬件约处理能力、存储容量等硬件约束和系统响应时间等处理效率要求），有些情况下束和系统响应时间等处理效率要求），有些情况下也需要考虑也需要考虑算法实现的复杂程度算法实现的复杂程度（从软件工程角度（从软件工程角度考虑软件开发成本）。一般情况下以考虑时间代价考虑软

6、件开发成本）。一般情况下以考虑时间代价为主。为主。 7数据结构国家精品课程2022-5-267.2.1 直接插入排序直接插入排序l直接插入排序的思想：直接插入排序的思想： 将一个记录插入到已排好序的有序表中，从而得到将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增一个新的、记录数增1的有序表。的有序表。7.2 插入排序插入排序例：例：原原有序表：有序表：(9 15 23 28 37) 20找找插入位置插入位置 : (9 15 23 28 37) 20新新有序表有序表: (9 15 20 23 28 37)8数据结构国家精品课程2022-5-26排序方法排序方法:第一步：第一步：R

7、1第二步：第二步：R1 , R2 第三步：第三步：R1 , R2, R3 第第j步：步：R1，R2，Rj1, Rj 第第n步：步：R1，R2，Rn1 , Rn9数据结构国家精品课程2022-5-26 插入排序的算法插入排序的算法算法算法InsertSort ( R，n ) IS1 逐一排序逐一排序 FOR j2 TO n DO ( ij-1 / 每次循环将每次循环将Rj插入到插入到R1，Rj1中中 KKj . RRj . WHILE i0 AND Ki K DO ( Ri+1Ri ii-1 ) Ri+1R. ) 10数据结构国家精品课程2022-5-26各趟排序结果各趟排序结果1 2 3 4

8、5 61 2 3 4 5 6 Rj = 21 2 3 4 5 6 Rj = 311数据结构国家精品课程2022-5-261 2 3 4 5 6 Rj = 5j = 6j = 41 2 3 4 5 6 R1 2 3 4 5 6 R12数据结构国家精品课程2022-5-26j = 5 时的排序过程时的排序过程完成j = 5i = 4j = 5i = 41 2 3 4 5 61 2 3 4 5 6 R1 2 3 4 5 6 R13数据结构国家精品课程2022-5-261 2 3 4 5 6 Rj = 5i = 3j = 5i = 2j = 5i = 1 11 2 3 4 5 6 R1 2 3 4 5

9、 6 R14数据结构国家精品课程2022-5-26j = 5i = 0 00 1 2 3 4 5 6 Ri15数据结构国家精品课程2022-5-26 改进后的插入排序算法改进后的插入排序算法 算法算法InsertSortA( R, s, e ) /* s , e 分别为文件记录序列的左端和右端分别为文件记录序列的左端和右端下标，下标，引入引入虚拟虚拟记录记录Rs-1 ，Ks-1 min Ki | s i e */ ISA1 逐一排序逐一排序 FOR js+1 TO e DO ( ij-1 KKj . RRj . WHILE Ki K DO ( Ri+1Ri ii-1 ) Ri+1R ) 16数

10、据结构国家精品课程2022-5-26 FOR js+1 TO e DO ( ij-1 KKj . RRj . WHILE KKi DO ( Ri+1Ri ii-1 ) Ri+1R ) k1k2k3k4k0k587246j 24678 872462 27 8464 7 82463 247 86517数据结构国家精品课程2022-5-26插入算法分析：设插入算法分析：设dj是是Rj左边关键词大于左边关键词大于Kj的记录个数，的记录个数，则算则算法法InsertSortA中关键词的比较次数为：中关键词的比较次数为： 记录的移动次数为记录的移动次数为njnjjjdnd221)1( 18数据结构国家精品

11、课程2022-5-26最好情况：最好情况：排序排序前记录前记录已按已按关键词从小到关键词从小到大排列大排列，即即 dj 0. 每每趟只需与前面的趟只需与前面的有序有序序列序列的的最后一个记录的最后一个记录的关键词比较关键词比较 1 次，记录移动次，记录移动 2 次，总的关键词次，总的关键词比较次数为比较次数为 n 1，记录移动次数为，记录移动次数为 2(n 1).19数据结构国家精品课程2022-5-26最坏最坏情况情况：第第 i 趟趟时，时，第第 i 个个记录前面所有记录的关键词记录前面所有记录的关键词都比都比第第 i 个个记录的关键词大，记录的关键词大，即即 dj j 1总总的关键词比较次

12、数：的关键词比较次数：记录记录移动次数移动次数：211112 2=()/2()( + )/jjnndnn nnn 22121114 2=()()()/2()( + )/jjnndnn nnn20数据结构国家精品课程2022-5-26l考察分析考察分析 的期望值。的期望值。l对于对于序列序列K1，K2，Kn ，如果，如果1ijn，且，且KiKj，则称，则称(Ki , Kj)为上述序列的一个反序对为上述序列的一个反序对。l实际上实际上， 正好正好是序列是序列K1，K2，Kn的反序的反序对个数。对个数。 njjd2njjd221数据结构国家精品课程2022-5-26对于关键词对于关键词K1，K2，K

13、n，设，设K(1)， K(2) ，K(n) 是排序结果。假设是排序结果。假设K(j)插入到插入到K(1) ，K(2) ，K(j1)每个位置的概率相等，则对于原始序列每个位置的概率相等，则对于原始序列K1，K2，Kn：K(2)出现在出现在K(1)左边或右边的概率是左边或右边的概率是1/2；K(3)出现在出现在K(1)和和K(2)左边、中间和右边的概率是左边、中间和右边的概率是1/3； K(n)出现在出现在K(1)，K(n1)中间的任何位置的概率中间的任何位置的概率均为均为1/n .22数据结构国家精品课程2022-5-26则有则有反序对的平均个数反序对的平均个数 = 0+ (0+1)/2+ (0

14、+1+2)/3+ + (0+1+2+n1)/n = 0+1/2+2/2+ +( n1)/n = n(n1)/4即即 的期望值为的期望值为n(n1)/4 . njjd223数据结构国家精品课程2022-5-2624数据结构国家精品课程2022-5-26直接插入排序算法直接插入排序算法l优点：算法的执行过程相当清晰，并且书写容易。优点：算法的执行过程相当清晰，并且书写容易。l缺点：期望复杂性为缺点：期望复杂性为O(n2) . l稳定性：直接插入排序是稳定的排序方法。稳定性：直接插入排序是稳定的排序方法。l最好情况：当被排序文件初态为正序时，算法的时最好情况：当被排序文件初态为正序时，算法的时间复杂

15、度为间复杂度为O(n) . l辅助空间：辅助空间：O(1) .25数据结构国家精品课程2022-5-26 直接插入排序算法是否可以进一步改进呢？直接插入排序算法是否可以进一步改进呢？ 直接插入排序算法中包含了一个查找过程，对前直接插入排序算法中包含了一个查找过程，对前部已经排序完的记录执行顺序查找。这显然是其效部已经排序完的记录执行顺序查找。这显然是其效率低下的原因之一，是否可以通过改进顺序查找来率低下的原因之一，是否可以通过改进顺序查找来提高排序效率呢提高排序效率呢? 26数据结构国家精品课程2022-5-26l通过将顺序查找改为二分查找，可构造通过将顺序查找改为二分查找，可构造二分插入排二

16、分插入排序算法序算法。即在插入第。即在插入第 j 个元素时，不是像直接插入排个元素时，不是像直接插入排序那样顺序寻找插入位置，而是采用一种二分方法序那样顺序寻找插入位置，而是采用一种二分方法，譬如对半查找方法，寻找插入位置，譬如对半查找方法，寻找插入位置.l如果如果文件（文件（R1，R2，Rn）采用顺序存储（比如）采用顺序存储（比如数组），数组），则对半插入排序算法可以减少关键词的比则对半插入排序算法可以减少关键词的比较次数，但是记录的移动次数仍不能减少较次数，但是记录的移动次数仍不能减少。如果文。如果文件（件（R1，R2，Rn）采用链接存储，）采用链接存储，不能使用对不能使用对半的方法寻找插

17、入位置。半的方法寻找插入位置。27数据结构国家精品课程2022-5-26l对半插入排序就平均性能来说比直接插入排序对半插入排序就平均性能来说比直接插入排序要快。要快。l它所需要的关键词比较次数与待排序记录序列它所需要的关键词比较次数与待排序记录序列的初始排列无关，仅依赖于记录个数。的初始排列无关，仅依赖于记录个数。在插入在插入第第 i 个记录时，需要经过个记录时，需要经过 log2i +1 次关键词比次关键词比较较，确定，确定它应插入的位置它应插入的位置。但是记录的移动次但是记录的移动次数仍不能减少。数仍不能减少。28数据结构国家精品课程2022-5-26 7.2.2 希尔排序希尔排序希尔排序

18、（渐减增量排序法）思想：希尔排序（渐减增量排序法）思想：1959年年Donald L. Shell提出提出Shell排序法排序法，是对直接是对直接插入算法的改进。插入算法的改进。把记录按下标的一定增量分组，把记录按下标的一定增量分组，对每组使用直接插对每组使用直接插入排序法，随着增量逐渐减少，所分成的组包含的入排序法，随着增量逐渐减少，所分成的组包含的关键词越来越多，到增量值减至关键词越来越多，到增量值减至1时，整个文件恰时，整个文件恰好被分成一个组，算法便告终止。好被分成一个组，算法便告终止。29数据结构国家精品课程2022-5-26 希尔排序增量的取法：希尔排序增量的取法： d1= n/2

19、 = 10/2 =5d2= d1/2 = 5/2 =2d3= d1/2 = 2/2 =130数据结构国家精品课程2022-5-26 例例 将十个数进行希尔排序的示例。将十个数进行希尔排序的示例。 0 1 2 3 4 5 6 7 8 9 36 25 48 12 65 43 58 76 32下标下标d1=5254348581276363265 25 48 12 32 36 43 58 76 65第一趟第一趟排序结果排序结果31数据结构国家精品课程2022-5-26 例例 将十个数进行希尔排序的示例。将十个数进行希尔排序的示例。 0 1 2 3 4 5 6 7 8 9下标下标d2=2 25 25 4

20、8 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=132数据结构国家精品课程2022-5-26l 渐减增量排序的原理渐减增量排序的原理 开始时增量值较大，子序列中的记录较少，开始时增量值较大，子序列中的记录较少，排序速度较快；随着排序进展，增量值逐渐变排序速度较快；随着排序进展，增量值逐渐变小，子序列中记录个数逐渐变多，由于前面工小，子序列中记录个数逐渐变多，由

21、于前面工作的基础，大多数记录已基本有序，所以排序作的基础，大多数记录已基本有序，所以排序速度仍然很快。速度仍然很快。33数据结构国家精品课程2022-5-26l 增量的取法增量的取法v 最初最初 Shell 提出取提出取 d1 = n/2 ，d2= d1 /2 ，直，直到到dt = 1 .v 后来后来Knuth 提出取提出取dj+1 = dj /3 +1 .v 取奇数取奇数v 各增量互质各增量互质34数据结构国家精品课程2022-5-26算法分析算法分析lShell算法是不稳定的排序算法。算法是不稳定的排序算法。lShell算法的性能与所选取的算法的性能与所选取的分组长度序列分组长度序列有很大

22、有很大关系关系l前面介绍的实例是最简单的分组长度序列，即前面介绍的实例是最简单的分组长度序列，即n/(2i)，最坏情况下时间复杂度为，最坏情况下时间复杂度为O(n2).35数据结构国家精品课程2022-5-26l一般一般实际应用中选择实际应用中选择2.2作为递减因子效果作为递减因子效果更好更好. 如果如果选择选择2k 1为分组长度为分组长度序列序列, 最坏最坏情况下能达到情况下能达到 O(n2/3). l1969年，普拉特（年，普拉特（V. Pratt）证明了如）证明了如下结论：如果下结论：如果渐减增量序列取值为形渐减增量序列取值为形如如 2p3q且且小于小于n的所有自然数的所有自然数的的集合

23、集合, 即即2p3q|2p3q n, 则则 Shell 算法算法的的时间复杂性时间复杂性O(n(log2n)2).l克努斯（克努斯（Knuth）从大量）从大量的实验统计的实验统计资料中得出资料中得出，当，当 n 很大时，很大时，关键词的平均关键词的平均比较比较次数大约是次数大约是n1.25，记录，记录的平均的平均移动移动次数大约是次数大约是 1.6n1.25 .36数据结构国家精品课程2022-5-26l反序对反序对l交换排序采用交换的思想，不断交换序列中的反交换排序采用交换的思想，不断交换序列中的反序对，直到不再有反序对为止。序对，直到不再有反序对为止。 l冒泡排序、分划交换排序（快速排序）

24、冒泡排序、分划交换排序（快速排序）7.3 交换排序交换排序37数据结构国家精品课程2022-5-26冒泡排序思想：自下而上（或从左到右）比较冒泡排序思想：自下而上（或从左到右）比较相邻记录的关键词，交换存在逆序的记录相邻记录的关键词，交换存在逆序的记录(若若KjKj+1，则互换，则互换Rj和和Rj+1)；使关键词较大的记录；使关键词较大的记录如气泡一般逐渐往上如气泡一般逐渐往上“飘移飘移”直至直至“水面水面”。7.3.1 冒泡排序冒泡排序38数据结构国家精品课程2022-5-26 1 2 3 4 5 6 7 8 9i = n 1 2 3 4 5 6 7 8 9i = n-1 1 2 3 4 5

25、 6 7 8 939数据结构国家精品课程2022-5-26算法算法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 ) 40数据结构国家精品课程2022-5-26l经过一趟冒泡，可以把具有最大关键词的记录移至最经过一趟冒泡，可以把具有最大关键词的记录移至最后（第后（第n个位置）。个位置）。l第第i趟冒泡，把第趟冒泡，把第i大记录放在第大记录放在第n-i+1个位置上。个位置上。l做做n-1趟冒泡，就可以对所有记录排序。趟冒泡，就可以对所有记录排序。l发生一

26、次记录交换，反序对的个数减少一个。发生一次记录交换，反序对的个数减少一个。n关键词的比较次数为关键词的比较次数为 (n-1)+(n-2)+1= (n-1)n/241数据结构国家精品课程2022-5-26l在每一趟比较中，当比较结束后，如果发现位置在每一趟比较中，当比较结束后，如果发现位置t是最后一次记录交换，即说明从是最后一次记录交换，即说明从Rt+1 Rn已经排序已经排序，从而下一趟比较只要进行到位置，从而下一趟比较只要进行到位置t即可。这样可即可。这样可以减少算法的关键词比较次数。以减少算法的关键词比较次数。l据此可以给出一种改进的冒泡排序算法。据此可以给出一种改进的冒泡排序算法。算法的改

27、进算法的改进07 02 09 08 05 12 13 14 1642数据结构国家精品课程2022-5-26算法算法Bubble ( R，n ) /改进的冒泡排序算法改进的冒泡排序算法Bubble1 终止位置初始化终止位置初始化 BOUND n Bubble2 冒泡过程冒泡过程 WHILE BOUND0 DO ( t 0 . / t用来记录一趟冒泡最后记录交换的位置用来记录一趟冒泡最后记录交换的位置 FOR j1 TO BOUND 1 DO IF Kj Kj+1 THEN ( RjRj+1 . tj ) . BOUND t ) 加速示例加速示例 pp205 图图7.443数据结构国家精品课程20

28、22-5-26假定记录序列假定记录序列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经过一趟冒泡后，记录的位置发生变化，反序表也会经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。发生变化。44数据结构国家精品课程2022-5-26定理定理

29、7.1 设设K1，K2，Kn是序列是序列1，2，n的的一个排列，一个排列，b1，b2，bn是对应的反序表是对应的反序表. 如果算如果算法法Bubble的一趟冒泡把的一趟冒泡把K1, K2, Kn改变为改变为K1 , K2 , , Kn , 那么从那么从b1, b2, bn中把每个非零元素减中把每个非零元素减1, 就得到了相应的反序表就得到了相应的反序表b1 , b2 , , bn . 45数据结构国家精品课程2022-5-26推论推论7.1 算法算法Bubble的冒泡的冒泡趟数趟数A = 1 + max b1，b2，bn ；记录交换次数记录交换次数B=nbi (消除反序对消除反序对个数个数)；

30、关键词的比较次数关键词的比较次数C=ACi ，其中，其中Ci等于第等于第i趟冒泡时的趟冒泡时的BOUND减减1. 46数据结构国家精品课程2022-5-26l记录的初始排列是按关键词从小到大排好序时，记录的初始排列是按关键词从小到大排好序时，此算法只执行一趟起泡，做此算法只执行一趟起泡，做 n-1 次关键词比较，次关键词比较，不发生记录交换；这是最好的情形。不发生记录交换；这是最好的情形。l最坏的情形是算法执行了最坏的情形是算法执行了n趟起泡，第趟起泡，第 i 趟趟 (1 i n) 做了做了 n- i 次关键词比较，执行了次关键词比较，执行了n-i 次记录交次记录交换。这样在最坏情形下总的关键

31、词比较次数和记换。这样在最坏情形下总的关键词比较次数和记录录交换交换次数均为：次数均为：(n-1)n/247数据结构国家精品课程2022-5-26 比比较较 交交换换 趟趟数数 最最好好 n1 0 1 平平均均 )()ln(21nOnnn ) 1(41nn ) 1 (2/Onn 最最坏坏 ) 1(21nn ) 1(21nn n 冒泡排序时间复杂性分析冒泡排序时间复杂性分析48数据结构国家精品课程2022-5-26冒泡排序算法冒泡排序算法l时间复杂度：时间复杂度：O(n2)（包括最坏和平均）（包括最坏和平均） . l稳定性：稳定性：冒泡排序是冒泡排序是稳定的稳定的排序方法。排序方法。l最好情况是

32、：最好情况是：当被排序文件初态为正序时，算法当被排序文件初态为正序时，算法的时间复杂度为的时间复杂度为O(n) . l空间复杂度：空间复杂度： O(1) . l可以采用气泡上浮和下沉交替的方法排序。可以采用气泡上浮和下沉交替的方法排序。49数据结构国家精品课程2022-5-26 初始上浮下沉上浮下沉79909090905679798888 905688797948856565632432353527322732321627162727881635161635354446：450数据结构国家精品课程2022-5-26l为了加快排序的速度，为了加快排序的速度，C. A. R. Hoare于于196

33、2年提出年提出了一种了一种快速排序方法快速排序方法(Quick Sort) （或称为分划交换（或称为分划交换排序）。排序）。l特点：特点：一趟分划把一个记录放在最终的位置上。一趟分划把一个记录放在最终的位置上。l原理：原理：交换反序对，交换反序对，非相邻的（与冒泡排序相比）非相邻的（与冒泡排序相比）记录交换使得文件中的记录交换使得文件中的反序对的数目反序对的数目减少的更多。减少的更多。7.3.2 分划交换排序分划交换排序51数据结构国家精品课程2022-5-26快速排序的基本思想快速排序的基本思想:每次将每次将基准记录（分划记录）基准记录（分划记录）直接放在排序的最终位置上直接放在排序的最终位

34、置上基本过程：基本过程：l任取待排序文件中的某个记录任取待排序文件中的某个记录 (例如取第一个记录例如取第一个记录) 作为基作为基准，按照该记录的关键词大小，将整个文件划分为左右两准，按照该记录的关键词大小，将整个文件划分为左右两个子文件：个子文件： 左侧子文件中所有记录的关键词都小于或等于基准记左侧子文件中所有记录的关键词都小于或等于基准记录的关键词录的关键词 右侧子文件中所有记录的关键词都大于或等于基准记右侧子文件中所有记录的关键词都大于或等于基准记录的关键词录的关键词52数据结构国家精品课程2022-5-26l基准记录排在这两个子文件中间（这也是该基准记录排在这两个子文件中间（这也是该记

35、录最终应安放的位置）。记录最终应安放的位置）。l分别对两个子文件重复上述操作，直到所有分别对两个子文件重复上述操作，直到所有的记录都排在正确位置上为止。的记录都排在正确位置上为止。53数据结构国家精品课程2022-5-26(1) (2) (3) (4) (5) (6) (7) (8) (9)70 73 69 23 93 18 11 68 10018 68 69 23 11 70 93 73 10054数据结构国家精品课程2022-5-26算法描述算法描述QuickSort ( R ) if ( R的长度大于的长度大于1) 将文件将文件R划分为两个子文件划分为两个子文件LeftR 和和 Righ

36、tR; QuickSort ( LeftR ); QuickSort ( RightR ); 55数据结构国家精品课程2022-5-26算法算法QSort（R，m，n）QSort1 递归出口递归出口 IF m n THEN （im . jn+1 . KKm . WHILE i j DO （ii+1 WHILE Ki K DO jj1 . IF i j THEN Ri Rj ) Rm Rj . / j指向小于等于指向小于等于Km的元素的元素 QSort ( R，m，j1 ) . QSort ( R，j+1，n ). ) 分划交换排序演示分划交换排序演示56数据结构国家精品课程2022-5-26(

37、1) (2) (3) (4) (5) (6) (7) (8) (9)(1) (2) (3) (4) (5) (6) (7) (8) (9) 7373 69 23 93 18 11 69 23 93 18 11 6868 100100i=2i=2j=8j=8 73 69 23 93 18 11 68 73 69 23 93 18 11 68 100100i=1i=1j=9j=9i=2i=2 6868 69 23 93 18 11 69 23 93 18 11 7373 100100j=8j=8 68 68 6969 23 93 18 11 23 93 18 11 7373 100100i=3i=

38、3j=8j=8 68 68 69 69 2323 93 18 11 93 18 11 7373 100100i=4i=4j=8j=8 68 68 69 23 69 23 93 93 18 11 18 11 73 10073 100i=5i=5j=8j=8 68 68 69 23 69 23 9393 18 18 11 11 73 73 100100i=5i=5j=7j=7 68 68 69 23 69 23 1111 18 18 9393 73 73 100100i=5i=5j=7j=7 68 68 69 23 11 69 23 11 18 18 93 73 93 73 100100i=7i=

39、7j=6j=61818 68 68 69 23 11 69 23 11 93 73 93 73 100100WHILE i j DO （ii+1 WHILE Ki K DO jj1 . IF i j THEN Ri Rj )Rm Rj .一趟快速排序一趟快速排序 过程示例过程示例: :57数据结构国家精品课程2022-5-26 18 68 18 68 69 23 1169 23 11 70 70 93 7393 73 j=6j=6一趟一趟结果结果 1111 18 18 69 23 6869 23 68 70 70 93 7393 73 j=2二趟二趟结果结果 11 18 68 23 11 18

40、 68 23 69 69 70 93 73 70 93 73j=5j=5三趟三趟结果结果11 18 23 68 69 70 73 9311 18 23 68 69 70 73 93最终最终结果结果 11 18 23 11 18 23 6868 69 7069 70 73 93 73 93j=8j=8四趟四趟结果结果j=4j=4算法算法QSort（R，m，n） IF m Kn THEN Rm+1Rn . IF KmKn THEN RmRn . IF Km+1Km THEN Rm+1Rm . Part2 分划开始分划开始 im jn+1 KKm .Part3 用用Km分划文件分划文件( Rm，Rm

41、+1，Rn ) WHILE ij DO ( ii1 WHILE KiK DO ii1 jj1 WHILE KjK DO jj1 . IF ij THEN RiRj ) RmRj 65数据结构国家精品课程2022-5-26算法算法 HSort ( n，R，M ) /* Hoare快速排序的非递归算法，变量快速排序的非递归算法，变量 M已给定，已给定，5M15. 该该算法对文件（算法对文件（R1，R2，Rn）进行排序）进行排序 */HS1 堆栈初始化堆栈初始化 CREATS( S ) HS2 设置栈底元素设置栈底元素 S(0，0) HS3 初始化初始化 f1 t n . Kn+1 + . K0 .

42、66数据结构国家精品课程2022-5-26HS4 对长度大于或等于对长度大于或等于M的记录序列分划排序的记录序列分划排序 WHILE ft DO ( Part ( R，f，t. j )/ 分划文件（分划文件（R1，R2，Rn） CASE DO ( jfM AND tjM : IF NOT(StackEmpty(s) THEN (f，t)S ELSE tf1. jfM AND tjM: fj+1 . jfM AND tjtj THEN ( S(f，j1) . fj+1 ) ELSE (S(j+1，t) . tj1) ) ) . HS5 插入排序插入排序 InsertSortA( R，1，n )

43、. 67数据结构国家精品课程2022-5-26快速排序算法快速排序算法l时间复杂度：时间复杂度：O(n2) /最坏最坏l时间复杂度：时间复杂度：O(nlog2n) /最好和平均最好和平均l空间复杂度：空间复杂度：O(log2n) .l稳定性：快速排序是不稳定的排序方法。稳定性：快速排序是不稳定的排序方法。l快速排序方法是内排序算法中最快的排序方法快速排序方法是内排序算法中最快的排序方法68数据结构国家精品课程2022-5-26思想：思想：对待排序的文件进行对待排序的文件进行n次选择，其中次选择，其中第第 i 次选择第次选择第 i 小（大）的记录放在第小（大）的记录放在第 i（n-i+1）个位置

44、上。）个位置上。 直接选择排序直接选择排序 堆排序堆排序7.4 选择排序选择排序69数据结构国家精品课程2022-5-267.4.1 直接选择排序直接选择排序直接选择排序思想：直接选择排序思想：选择第选择第i大的记录在剩余的大的记录在剩余的n-i+1个记录中进行一个记录中进行一趟比较，确定出第趟比较，确定出第i大记录，放在第大记录，放在第n-i+1个位置上。个位置上。例如第例如第 i 趟比较（趟比较（i = 1, , n-1）在前面）在前面 n-i+1 个待排个待排序记录中选出关键词最大的记录序记录中选出关键词最大的记录, 作为有序记录序列作为有序记录序列的第的第 n-i+1个记录。待到第个记

45、录。待到第 n-1 趟作完，待排序记录趟作完，待排序记录只剩下只剩下1个时，算法结束。个时，算法结束。 17 78 6 54 34 3870数据结构国家精品课程2022-5-26算法算法 SSort（R，n） / 直接选择排序算法，该算法排序文件直接选择排序算法，该算法排序文件(R1, R2, , Rn)SS1 排序排序FOR j=n TO 2 STEP 1 DO ( t1 . FOR i2 TO j DO IF KtKi THEN ti. / 找第找第j小元素的下标小元素的下标 RjRt ) / 将将Rt放到第放到第j个位置上个位置上 71数据结构国家精品课程2022-5-26 (1) (2

46、) (3) (4) (5) (6)(1) (2) (3) (4) (5) (6) i t 2121 25 25 49 25 49 25* * 16 08 16 08 2 1 2 1 初始初始序列序列 算法算法 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 21 2525 4949 25 25* * 16 08 16 08 3 23 2 21 25 21 25 4949 2525* * 16 08 16 08 4 34 3 21 25 21 25 49 49 25 25* *

47、 16 16 08 08 5 3 5 3 21 25 21 25 49 49 25 25* * 16 16 08 08 6 36 3 21 25 08 2521 25 08 25* * 16 16 4949 25 25 08 08 2525* * 16 16 21 25 21 25 49 49 25 25* * 16 16 0808 一趟直接选择排序过程示例一趟直接选择排序过程示例72数据结构国家精品课程2022-5-26多趟直接选择排序过程示例多趟直接选择排序过程示例 (1) (2) (3) (4) (5) (6)(1) (2) (3) (4) (5) (6)i it t 1 1 21 21

48、 25 25 08 08 2525* * 16 16 49 49 2 2 2 2 21 16 21 16 0808 2525* * 25 25 49 49 4 4 3 3 21 16 08 21 16 08 2525* * 25 49 25 49 1 1 5 5 08 08 16 16 2121 2525* * 25 25 4949 21 21 25 25 49 49 2525* * 16 08 16 08 3 3 初始初始序列序列 4 4 08 16 08 16 2121 25 25* * 25 4925 49 2 2 73数据结构国家精品课程2022-5-26 算法分析算法分析l直接选择排

49、序的关键词比较次数与记录的初始排列直接选择排序的关键词比较次数与记录的初始排列无关。无关。假定整个待排序文件有假定整个待排序文件有 n 个记录，第个记录，第 i 趟选趟选择具有最大关键词的记录所需的比较总次数是择具有最大关键词的记录所需的比较总次数是 n-i 次。因此，总的关键词比较次数为次。因此，总的关键词比较次数为 (n-1)+(n-2)+1=l记录交换次数是选择的趟数记录交换次数是选择的趟数: n-1. 121 nn74数据结构国家精品课程2022-5-26 直接选择排序算法直接选择排序算法l时间复杂度时间复杂度:O(n2) （包括最好、最坏和平均）（包括最好、最坏和平均） . l稳定性

50、：不稳定的排序方法。稳定性：不稳定的排序方法。l空间复杂度：空间复杂度： O(1) . l优点：简单、书写容易优点：简单、书写容易75数据结构国家精品课程2022-5-26v 选择排序的选择排序的关键关键 找最大（小）记录的方法找最大（小）记录的方法v 淘汰赛淘汰赛淘汰赛示意图淘汰赛示意图76数据结构国家精品课程2022-5-26 淘汰赛的思想淘汰赛的思想l对于对于 n 个记录的关键词，进行两两比较，得到个记录的关键词，进行两两比较，得到 n/2 个比较的优胜者个比较的优胜者(关键词大者关键词大者)，作为第一步比，作为第一步比较的结果保留下来。然后对这较的结果保留下来。然后对这 n/2 个记录

51、再进行个记录再进行关键词的两两比较，关键词的两两比较，如此重复，直到选出一个，如此重复，直到选出一个关键词最大的记录为止。关键词最大的记录为止。l在图例中，最下面是记录排列的初始状态，相当于在图例中，最下面是记录排列的初始状态，相当于一棵满二叉树的叶结点，它存放的是所有参加排序一棵满二叉树的叶结点，它存放的是所有参加排序的记录的关键词。的记录的关键词。77数据结构国家精品课程2022-5-26l如果如果 n 不是不是2的的 k 次幂，则让叶结点数补足到满足次幂，则让叶结点数补足到满足 2k-1 n 2k 的的2k个。叶结点上面一层的非叶结点是叶结点关键词两两个。叶结点上面一层的非叶结点是叶结点

52、关键词两两比较的结果。最顶层是树的根。比较的结果。最顶层是树的根。63Winner 49631663492521254925*160863tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree1478数据结构国家精品课程2022-5-26比赛树的概念比赛树的概念l每次两两比较的结果是把关键词大者作为优胜者上升到双每次两两比较的结果是把关键词大者作为优胜者上升到双亲结点，称这种树为比赛树。亲结点，称这种树为比赛树。l位于最底层的叶结点叫做比赛树的位于最底层的叶结点叫做比赛树的外结点外结点，非叶结点称为，非叶结点称为比赛树的比赛树的内结点内结点。每个结

53、点除了存放记录的关键词外，还。每个结点除了存放记录的关键词外，还存放了此对象在满二叉树中的序号。存放了此对象在满二叉树中的序号。l比赛树最顶层是树的根，表示最后选择出来的具有最大关比赛树最顶层是树的根，表示最后选择出来的具有最大关键词的记录。键词的记录。79数据结构国家精品课程2022-5-26l形成初始比赛树（最大关键词上升到根）形成初始比赛树（最大关键词上升到根）l关键词比较次数关键词比较次数 : 663Winner 49631663492521254925*160863tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14R780数据结构

54、国家精品课程2022-5-26l输出最大记录后，调整为新的比赛树输出最大记录后，调整为新的比赛树l关键词比较次数关键词比较次数 : 349Winner 491616-492521254925*1608-tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14R681数据结构国家精品课程2022-5-26l输出次大记录后，调整为新的比赛树输出次大记录后，调整为新的比赛树l关键词比较次数关键词比较次数 : 325Winner 251616-25*25212525*1608-tree7 tree8 tree9 tree10 tree11 tree12

55、tree13 tree14R5-82数据结构国家精品课程2022-5-26l输出第输出第3大记录后，调整为新的比赛树大记录后，调整为新的比赛树l关键词比较次数关键词比较次数 : 325*Winner 25*1616-25*212125*1608-tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14R4-83数据结构国家精品课程2022-5-26l输出第输出第4大记录后，调整为新的比赛树大记录后，调整为新的比赛树l关键词比较次数关键词比较次数 : 321Winner 211616-21211608-tree7 tree8 tree9 tree1

56、0 tree11 tree12 tree13 tree14R3-84数据结构国家精品课程2022-5-26l输出第输出第5大记录后，调整为新的比赛树大记录后，调整为新的比赛树l关键词比较次数关键词比较次数 : 316Winner 1616-1608-tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14R3-85数据结构国家精品课程2022-5-26l全部结果输出后，比赛树的状态全部结果输出后，比赛树的状态l关键词比较次数关键词比较次数 : 308Winner 0808-08-tree7 tree8 tree9 tree10 tree11 tr

57、ee12 tree13 tree14R1-86数据结构国家精品课程2022-5-26l除第一次选择具有最大关键词的记录需要进行除第一次选择具有最大关键词的记录需要进行 n-1 次关键词比较外，重构比赛树选择具有次大、再次关键词比较外，重构比赛树选择具有次大、再次大关键词记录所需的关键词比较次数均为次大关键词记录所需的关键词比较次数均为 O(log2n)。l总关键词比较次数为总关键词比较次数为n-1+(n-1)*log2n=O(nlog2n)。87数据结构国家精品课程2022-5-26原理原理 利用淘汰赛的方式寻找当前序列中的最利用淘汰赛的方式寻找当前序列中的最大记录大记录关键关键 找到与当前的

58、最大记录做比较的记录找到与当前的最大记录做比较的记录（其兄弟结点和父结点）（其兄弟结点和父结点）解决解决 利用利用堆堆7.4.2 堆排序堆排序88数据结构国家精品课程2022-5-26完全二叉树完全二叉树中的任意结点的关键词中的任意结点的关键词大于等于大于等于它它的两个儿子结点的关键词。把这样的数据结构的两个儿子结点的关键词。把这样的数据结构称为堆称为堆(大根堆大根堆)。 大根堆，小根堆大根堆，小根堆 大根堆中根结点的关键词最大大根堆中根结点的关键词最大 小根堆中根结点的关键词最小小根堆中根结点的关键词最小89数据结构国家精品课程2022-5-2694937591854451184858103

59、4例例 1 2 3 4 5 6 7 8 9 10 11 12 94 93 75 91 85 44 51 18 48 58 10 3490数据结构国家精品课程2022-5-26堆的定义堆的定义完全二叉树的数组表示完全二叉树的数组表示 Ki K2i & Ki K2i+1完全二叉树的数组表示完全二叉树的数组表示 Ki K2i & Ki K2i+191数据结构国家精品课程2022-5-26l数组数组R存放堆，那么存放堆，那么R1是最大的记录是最大的记录l将将R1和和Rn交换，使得最大记录放在交换，使得最大记录放在Rn的位置。的位置。l对对R1，Rn-1进行调整，使它们重新构成一个堆。进行调整，使它们重

60、新构成一个堆。l调整后，调整后，R1是是R1，R2，Rn-1中最大的。然后再交中最大的。然后再交 换换R1与与Rn-1，使，使Rn-1中放入次最大的记录。中放入次最大的记录。l再对再对R1，R2，Rn-2进行调整，使之成为新堆，再进进行调整，使之成为新堆，再进 行类似的交换和调整，行类似的交换和调整，l l反复进行，直到调整范围只剩下一个记录反复进行，直到调整范围只剩下一个记录R1为止。此时为止。此时R1是是 n个记录中最小的，个记录中最小的，l此时数组此时数组R1.n中的记录已经按从小到大排列了。中的记录已经按从小到大排列了。92数据结构国家精品课程2022-5-26堆排序算法的粗略描述如下