吉林大学数据结构课件第七章排序

1、排 序排序排序：排序指按规定的顺序排列一个给定对象集合排序指按规定的顺序排列一个给定对象集合中的诸元素中的诸元素 。文件文件: : 它是待排序数据对象的有限集合。它是待排序数据对象的有限集合。记录记录：R1，R2，Rn关键词域关键词域( (key):): 通常数据对象有多个属性域，即多通常数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键词域。每个文件象，作为排序依据。该域即为关键词域。每个文件用哪个属性域作为关键词，要视具体的应用需要而用哪个属性域作为关键词，要视具体的应用需要而定。即使是同一个文件

2、表，在解决不同问题的场合定。即使是同一个文件表，在解决不同问题的场合也可能取不同的域做关键码。也可能取不同的域做关键码。概概 述述主关键词主关键词: : 如果在数据表中各个对象的关键码互不相同，如果在数据表中各个对象的关键码互不相同，这种关键码即主关键码。按照主关键码进行排序，排序的这种关键码即主关键码。按照主关键码进行排序，排序的结果是唯一的。结果是唯一的。次关键词次关键词: : 数据表中有些对象的关键码可能相同，这种关数据表中有些对象的关键码可能相同，这种关键码称为次关键码。按照次关键码进行排序，排序的结果键码称为次关键码。按照次关键码进行排序，排序的结果可能不唯一。可能不唯一。概概 述述

3、排序：排序：记录按关键词域递增或递减的顺序排列记录按关键词域递增或递减的顺序排列n个记录相应的关键词个记录相应的关键词:K1，K2，Kn在关键词域上定义一个次序关系在关键词域上定义一个次序关系“” ，使，使得对于任意三个关键词的取值得对于任意三个关键词的取值a、b、c，下，下列条件成立：列条件成立：在在ab，a=b，ba 三个可能性中，有且只有一三个可能性中，有且只有一个可能性成立（三分率）；个可能性成立（三分率）；如果如果ab，并且，并且bc，则有，则有ac（传递性）（传递性）. 这两个性质显示了线性次序的数学性质，也这两个性质显示了线性次序的数学性质，也称作称作全序全序. 概概 述述排序：

4、排序：记录按关键词域递增或递减的顺序排列记录按关键词域递增或递减的顺序排列n个记录相应的关键词个记录相应的关键词:K1，K2，Kn在关键词域上定义一个次序关系在关键词域上定义一个次序关系“Kj，则称（Ki ，Kj）为上述序列的一个反序对. 正好是序列K1，K2，Kn的反序对个数2njjd K(1) ， K(n) K(1) d1=0,p11=1 K(1) ， K(n) K(1) d1=0,p11=1K(1), K(2) d2=0,p21=1/2K(2) ,K(1) d2=1,p22=1/2K(?), K(?) , K(3) d2=0,p1=1/3K(?) , K(3) ,K(?) d2=1,p2

5、=1/3K(3) , K(?) , K(?) d2=2,p3=1/3 平均情况下平均情况下:若待排序文件中记录所有可能的排列的概率若待排序文件中记录所有可能的排列的概率相同，则可取上述最好情况和最坏情况的平相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键词比较次数和均情况。在平均情况下的关键词比较次数和记录移动次数分别为记录移动次数分别为 因此，直接插入排序的时间复杂度为因此，直接插入排序的时间复杂度为 o(n2)。2(1)(4)14njjnnnd 2(1)(8)(1)(1)4njjnnnnd 最好情况最好情况下，排序前记录已经按关键下，排序前记录已经按关键词从小到大有序排列，

6、每趟只需与前词从小到大有序排列，每趟只需与前面的有序部分的最后一个记录的关键面的有序部分的最后一个记录的关键词比较词比较 1 1 次，记录移动次，记录移动 2 2 次，总的次，总的关键词比较次数为关键词比较次数为 n-1，记录移动次，记录移动次数为数为 2(n-1)。最坏情况下最坏情况下:第第 i 趟时第趟时第 i 个记录前面的所有记录的关键个记录前面的所有记录的关键词都比第词都比第 i 个记录的关键词大，即个记录的关键词大，即dj取最大取最大值，因此必须与前面值，因此必须与前面 i-1个记录都做关键词个记录都做关键词比较，并且每做比较，并且每做 1 次比较就要做次比较就要做 1 次记录移次记

7、录移动。则总的关键词比较次数为动。则总的关键词比较次数为 221 1)1(22 nndndnjnjjj记录移动次数为记录移动次数为 241112 nndnnnjj直接插入排序算法直接插入排序算法优点优点:是算法的执行过程相当清晰，并是算法的执行过程相当清晰，并 且书写容易且书写容易.缺点缺点:期望复杂性为期望复杂性为O(n2) . 稳定性：稳定性：直接插入排序是直接插入排序是稳定的稳定的排序方法。排序方法。最好情况是：最好情况是：当被排序文件初态为正序时，当被排序文件初态为正序时，算法的时间复杂度为算法的时间复杂度为O(n) . 辅助空间：辅助空间： O(1) 一种改进的方法是对半插入法，即在

8、插入第j个元素时，不是像直接插人排序那样顺序寻找插入的位置，而是采用对半（或二分）的方法 1 2 3 4 5 6 temp1 2 3 4 5 6 temp251 2 3 4 5 6 temp2116希尔排序希尔排序 希尔排序（希尔排序（渐减增量排序法）渐减增量排序法）思想：思想： 把记录按下标的一定增量分组，对每组使用直把记录按下标的一定增量分组，对每组使用直接插入排序法，随着增量逐渐减少，所分成的组接插入排序法，随着增量逐渐减少，所分成的组包含的关键词越来越多，到增量值减至包含的关键词越来越多，到增量值减至1 1时，整时，整个文件恰好被分成一个组，算法便告终止个文件恰好被分成一个组，算法便告

9、终止. . 希尔排序希尔排序增量的取法增量的取法(16条记录条记录)： d d1 1= = =8= = =8n/2n/216/216/2d d2 2= = =4= = =4d d1 1/2/2 8/28/2d d3 3= = =2= = =2d d2 2/2/2 4/24/2d d4 4= = =1= = =1d d3 3/2/2 2/22/2 例例 将十个数进行希尔将十个数进行希尔排序的示例。排序的示例。 0 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9 36 25 48 12 65 25* 43 58 76 32下标下标d1=525434858127625*36

10、3265 25* 25 48 12 32 36 43 58 76 65一趟一趟排序结果排序结果 例例 将十个数进行希尔将十个数进行希尔排序的示例。排序的示例。 0 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9下标下标d d2 2=2=2 25* 25 48 12 32 36 43 58 76 6525*48483232434376252512123636585865653243481225 25* 12 32 25 43 36 48 58 76 65二趟二趟排序结果排序结果 12 25* 25 32 36 43 48 58 65 76三趟三趟排序结果排序结果d d3

11、 3=1=1渐减增量排序算法渐减增量排序算法 7.2 交换排序交换排序 反序对反序对对于序列K1，K2，Kn ，如果1ijn，且KiKj，则称（Ki ，Kj）为上述序列的一个反序对. 交换排序的思想：交换文件中存在的反序对交换排序的思想：交换文件中存在的反序对 冒泡排序、分划交换排序（快速排序）冒泡排序、分划交换排序（快速排序）7.2.1 冒泡排序冒泡排序 冒泡排序思想：通过比较相邻记录的关键词，冒泡排序思想：通过比较相邻记录的关键词，交换存在逆序的记录；使关键词较大的记录如交换存在逆序的记录；使关键词较大的记录如气泡一般逐渐往上气泡一般逐渐往上“飘移飘移”直至直至“水面水面”。 1 2 3

12、4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9算法算法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 ) n 关键词的比较次数为关键词的比较次数为 (n-1)+(n-2)+1= = (n-1)n/2经过一趟冒泡，可以把具有最大关键词经过一趟冒泡，可以把具有最大关键词的记录移至最后（第的记录移至最后（第n个位置）。个位置）。第第i趟冒泡，把第趟冒泡，把第i大记录放在第大记录放在第i个位置个位置上。上。做做n

13、-1趟冒泡，就可以对所有记录排序。趟冒泡，就可以对所有记录排序。发生一次记录交换，反序对的个数减少发生一次记录交换，反序对的个数减少一个。一个。v在扫描过程中，可在扫描过程中，可能最后几趟已无任能最后几趟已无任何交换发生，程序何交换发生，程序应能做到，一旦发应能做到，一旦发现某趟扫描中无任现某趟扫描中无任何交换时就会终止何交换时就会终止算法的改进算法的改进/改进的冒泡排序算法改进的冒泡排序算法. 算法算法Bubble ( R，n )Bubble1 终止位置初始化终止位置初始化BOUND n Bubble2 冒泡过程冒泡过程WHILE BOUND0 DO ( t 0 / t用来记录一趟冒泡最后记

14、录交换的位置用来记录一趟冒泡最后记录交换的位置 FOR j1 TO BOUND 1 DO IF Kj Kj+1 THEN ( RjRj+1 . tj ) . BOUND t ) 冒泡排序演示冒泡排序演示 假定记录序列假定记录序列R1，R2，Rn所对应的关键词序列所对应的关键词序列为为A = K1，K2，Kn 令令bj（1 j n）表示）表示A中关键词第中关键词第 j 小的记录小的记录左边左边大于它的关键词的个数，则文件大于它的关键词的个数，则文件 b1，b2，bn 称为称为A的的反序表反序表. 经过一趟冒泡后，记录的位置发生变化，反经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。序表也

15、会发生变化。 经过一趟冒泡后，记录的位置发生变化，反经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。序表也会发生变化。 经过一趟冒泡后，记录的位置发生变化，反经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。序表也会发生变化。 经过一趟冒泡后，记录的位置发生变化，反经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。序表也会发生变化。 经过一趟冒泡后，记录的位置发生变化，反经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。序表也会发生变化。 经过一趟冒泡后，记录的位置发生变化，反经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。序表也会发生变化。 经过一趟冒泡后，

16、记录的位置发生变化，反经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。序表也会发生变化。 经过一趟冒泡后，记录的位置发生变化，反经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。序表也会发生变化。afterbefore 经过一趟冒泡后，记录的位置发生变化，反经过一趟冒泡后，记录的位置发生变化，反序表也会发生变化。序表也会发生变化。 定理定理7.1 设设K1，K2，Kn是序列是序列1，2，n的一个排列，的一个排列，b1，b2，bn是对应的反是对应的反序表序表. 如果算法如果算法Bubble的一趟冒泡把的一趟冒泡把K1, K2, Kn改变为改变为K1, K2, Kn, 那么从那么从b

17、1, b2, bn中把中把每个非零元素减每个非零元素减1, 就得到了相应的反序就得到了相应的反序表表b1,b2,bn . 冒泡趟数：冒泡趟数：A = 1 + max b1，b2，bn 记录的初始排列是按关键词从小到大记录的初始排列是按关键词从小到大排好序时，此算法只执行一趟起泡，排好序时，此算法只执行一趟起泡，做做 n-1 次关键词比较，次关键词比较，不发生记录交换不发生记录交换；这是最好的情形。这是最好的情形。最坏的情形是算法执行了最坏的情形是算法执行了n-1趟起泡，趟起泡，第第 i 趟趟 (1 i n) 做了做了 n- i 次关键词比较，次关键词比较，执行了执行了n-i 次记录交换。这样在

18、最坏情次记录交换。这样在最坏情形下总的关键词比较次数和记录形下总的关键词比较次数和记录交换次交换次数数为：为： (n-1)n/2 推论推论7.1 算法算法Bubble的冒泡的冒泡趟数趟数A = 1 + max b1，b2，bn ；记录交换次数记录交换次数B= bi ；关键词的比较次数关键词的比较次数C= Ci ，其中，其中Ci等等于第于第i趟冒泡时的趟冒泡时的BOUND减减1. 比比较较 交交换换 趟趟数数 最最好好 n1 0 1 平平均均 )()ln(21nOnnn ) 1(41nn ) 1 (2/Onn 最最坏坏 ) 1(21nn ) 1(21nn n 冒泡排序算法冒泡排序算法时间复杂度时

19、间复杂度: :O(n2)（包括最坏和平均）（包括最坏和平均） . . 稳定性：稳定性：冒泡排序是冒泡排序是稳定的稳定的排序方法。排序方法。最好情况是：最好情况是：当被排序文件初态为正序时，当被排序文件初态为正序时，算法的时间复杂度为算法的时间复杂度为O(n) . . 空间复杂度：空间复杂度： O(1) . . 可以采用气泡上浮和下沉交替的方法。可以采用气泡上浮和下沉交替的方法。 第一趟第一趟第二趟第二趟第三趟第三趟第四趟第四趟79799090909090909090565679797979888888 88 909056568888797979794 488885656565656563232

20、4 4323235353535272732322727323232321616272716162727272788881616353516161616353535354 44 44 4交换任意反序对后，D = 的变化? Ki KjK1，Ki-1，Ki，Ki+1 Kj-1，Kj， Kj+1， ，Knd1 ，di-1 ， di，di+1 dj-1， dj， dj+1， ， dn d1 di-1 , dj+1 dn没有发生变化D=D-1+?MAX（ D -D ）2njjd7.2.2 分划交换排序分划交换排序 19621962年年HoareHoare提出了快速排序提出了快速排序 (Quick Sort

21、)(Quick Sort)特点：特点：一趟分划把一个记录放在最终的位置一趟分划把一个记录放在最终的位置 上。上。原理：原理：交换反序对交换反序对，一次记录交换使得文件，一次记录交换使得文件 中的中的反序对的数目反序对的数目减少的更多。减少的更多。快速排序的基本思想快速排序的基本思想: :不断地交换反序对。不断地交换反序对。任取待排序文件中任取待排序文件中的某个记录的某个记录 (例如取第一个记录例如取第一个记录) 作为基作为基准，按照该记录的关键词大小，将整个准，按照该记录的关键词大小，将整个文件划分为左右两个子文件：文件划分为左右两个子文件： 左侧子文件中所有记录的关键词都小左侧子文件中所有记

22、录的关键词都小于或等于基准记录的关键词于或等于基准记录的关键词 右侧子文件中所有记录的关键词都大右侧子文件中所有记录的关键词都大于基准记录的关键词于基准记录的关键词基准记录则排在这两个子文件中间基准记录则排在这两个子文件中间( (这这也是该记录最终应安放的位置也是该记录最终应安放的位置) )。分别对两个子文件重复施行上述方法，分别对两个子文件重复施行上述方法，直到所有的记录都排在相应位置上为止。直到所有的记录都排在相应位置上为止。算法描述算法描述QuickSort ( R ) if ( R的长度大于的长度大于1) 将文件将文件R划分为两个子文件划分为两个子文件 LeftR 和和 RightR;

23、 QuickSort ( LeftR );QuickSort ( RightR ); 将两个子文件将两个子文件 LeftR 和和 RightR 合并为一个文件合并为一个文件R; (1) (2) (3) (4) (5) (6) (7) (8) (9)70 73 69 23 93 18 11 68 100 i(第一个大于第一个大于) (第一个小于第一个小于) j70 6868 69 23 93 18 11 7373 10070 68 69 23 1111 18 9393 73 10070 68 69 23 11 18 93 73 10018 68 69 23 11 70 93 73 100 算法算

24、法QSort（R，m，n） /*对文件（对文件（Rm，Rn）进行排序）进行排序. 我们选择我们选择Km作作为控制分划的关键词，并假定对任意的为控制分划的关键词，并假定对任意的min有有KiKn+1 . */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 . QSort ( R，m，j1 ) . QSort ( R，j+1，n ) ) 分划交换排序分划交换排序演示演示 68 69 23 93 18 11 73 MAX 68

25、 69 23 93 18 11 73 MAXi=5i=5j=8j=8i=1i=1(1) (2) (3) (4) (5) (6) (7) (8) (9)(1) (2) (3) (4) (5) (6) (7) (8) (9) 73 69 23 93 18 11 68 MAX 73 69 23 93 18 11 68 MAXi=2i=2j=8j=8i=2i=2 73 69 23 93 18 11 68 MAX 73 69 23 93 18 11 68 MAX 68 69 23 93 18 11 73 MAX 68 69 23 93 18 11 73 MAXj=8j=8 68 69 23 93 18

26、11 73 MAX 68 69 23 93 18 11 73 MAXi=3i=3j=8j=8 68 69 23 93 18 11 73 MAX 68 69 23 93 18 11 73 MAXi=4i=4j=8j=8 68 69 23 93 18 11 73 MAX 68 69 23 93 18 11 73 MAXi=5i=5j=7j=7 68 69 23 11 18 93 73 MAX 68 69 23 11 18 93 73 MAXi=5i=5j=7j=7 68 69 23 11 18 93 73 MAX 68 69 23 11 18 93 73 MAXi=7i=7j=6j=618 68

27、69 23 11 18 68 69 23 11 93 73 MAX 93 73 MAXim . jn+1 . KKmWHILE i j DO （ii+1 WHILE Ki K DO jj1 . IF i j THEN Ri Rj ) Rm Rj .一趟快速排序一趟快速排序 过程示例过程示例: :j=10j=10 18 68 18 68 69 23 1169 23 11 93 7393 73 j=6j=6一趟一趟结果结果11 11 69 23 68 69 23 68 93 73 93 73j=2j=2二趟二趟结果结果 68 2368 23 93 7393 73 j=5j=5三趟三趟结果结果 最终

28、最终结果结果多趟快速排序过程示例多趟快速排序过程示例 2323 7373 j=8j=8四趟四趟结果结果j=4j=4 18 68 18 68 69 23 1169 23 11 93 7393 73 j=6j=6一趟一趟结果结果 1111 69 23 6869 23 68 93 7393 73 j=2j=2二趟二趟结果结果 68 23 68 23 93 73 93 73j=5j=5三趟三趟结果结果 最终最终结果结果2323 73 73 j=8j=8四趟四趟结果结果j=4j=42 算法算法QSort（R，m，n） IF m Kn THEN Rm+1Rn . IF KmKn THEN RmRn . I

29、F Km+1Km THEN Rm+1Rm . Part2 分划开始分划开始 im jn+1 KKm . Part3 用用Km分划文件分划文件( Rm，Rm+1，Rn ) WHILE ij DO ( ii1 WHILE KiK DO ii1 jj1 WHILE KjK DO jj1 . IF ij THEN RiRj ) RmRj 快速排序算法快速排序算法时间复杂度时间复杂度:O(n:O(n2 2)/)/最坏最坏 . . 时间复杂度时间复杂度:O(nlog:O(nlog2 2n) /n) /最好和平均最好和平均空间复杂度空间复杂度： O(logO(log2 2n) .n) .稳定性稳定性：快速排

30、序是：快速排序是不稳定的不稳定的排序方法。排序方法。快速排序方法是目前内部排序中最好、最快快速排序方法是目前内部排序中最好、最快的排序方法。的排序方法。 7.3 选择排序选择排序 思想：思想：对待排序的文件进行对待排序的文件进行n次次选择选择，其，其中第中第i次次选择选择第第i小（或大）的记录放在第小（或大）的记录放在第i（或（或n-i+1）个位置上。）个位置上。 直接选择排序直接选择排序 堆排序堆排序7.3.1 直接选择排序直接选择排序 1 1 直接选择排序思想：直接选择排序思想： 选择第选择第i大的记录大的记录在剩余的在剩余的n-i+1个记录中进行一趟个记录中进行一趟比较，确定出第比较，确

31、定出第i大大记录记录，放在第，放在第n-i+1个位置上。个位置上。 例如第例如第 i 趟比较（趟比较（i = 0, 1, , n- -2）在前面在前面 n- -i 个待个待排序记录中选出关键码最大的记录排序记录中选出关键码最大的记录, 作为有序记录序列作为有序记录序列的第的第 i 个记录。待到第个记录。待到第 n- -2 趟作完，待排序记录只剩下趟作完，待排序记录只剩下1个时，算法结束。个时，算法结束。算法算法 SSort（R，n） / 直接选择排序算法，该算法排序文件（直接选择排序算法，该算法排序文件（R1，R2，Rn）SS1 排序排序FOR j=n TO 2 STEP 1 DO ( t1

32、. FOR i2 TO j DO IF Kt Ki THEN ti / 找第找第j小元素小元素 / 的下标的下标 RjRt ) / 将将Rt放到第放到第j个位置上个位置上 (1) (2) (3) (4) (5) (6)(1) (2) (3) (4) (5) (6) i t 2121 2525 49 25 49 25* * 16 08 16 08 2 1 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 Ri Rt) 21 21 25 25 4949 25 2

33、5* * 16 08 16 08 3 23 2 21 25 21 25 49 49 2525* * 16 08 16 08 4 34 3 21 25 21 25 49 49 25 25* * 1616 08 08 5 35 3 21 25 21 25 49 49 25 25* * 16 16 0808 6 36 3 21 25 08 2521 25 08 25* * 16 16 4949 25 25 0808 25 25* * 16 16 21 25 21 25 49 49 25 25* * 16 16 0808 一趟选择排序过程示例一趟选择排序过程示例多趟选择排序过程示例多趟选择排序过程示例

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

35、6 2121 25 25* * 25 4925 49 2 2 n记录交换次数是选择的趟数记录交换次数是选择的趟数: n-1.112nn 直接选择排序算法直接选择排序算法时间复杂度时间复杂度:O(n2)（包括最好、最坏和平均）（包括最好、最坏和平均） . 稳定性：稳定性：不稳定的不稳定的排序方法。排序方法。空间复杂度：空间复杂度： O(1) . 优点：优点：简单、书写容易简单、书写容易 淘汰赛的思想淘汰赛的思想对于对于 n 个记录的关键词，进行两两比较，个记录的关键词，进行两两比较，得到得到 n/2 个比较的优胜者个比较的优胜者(关键词大关键词大者者)，作为第一步比较的结果保留下来。，作为第一步

36、比较的结果保留下来。然后对这然后对这 n/2 个记录再进行关键词的个记录再进行关键词的两两比较，两两比较，如此重复，直到选出一，如此重复，直到选出一个关键词最大的记录为止。个关键词最大的记录为止。n-1（15）次）次比较K=94；(16)=64次次比较（14）K=93；(15)=104次次比较（13）K=91；(14)=1 次元素比较次数次元素比较次数: (n1)+(n1)* log2n nlog2n淘汰赛示意图淘汰赛示意图从开始寻找最大元素的过程就是找兄弟结点和父亲结点的过程. 从开始寻找最大元素的过程就是找兄弟结点和父亲结点的过程. 完全二叉树：第i个元素的左、右儿子分别是第2i和第2i1

37、个元素，父亲结点是第i/2个元素. 7.3.2 堆排序堆排序 原理原理 利用淘汰赛的方式寻找当前序列利用淘汰赛的方式寻找当前序列中的最大记录中的最大记录 关键关键 与与当前的最大记录做比较的记录当前的最大记录做比较的记录 解决解决 堆堆 完全二叉树中的任意非叶结点的关键词完全二叉树中的任意非叶结点的关键词大于等于大于等于它的两个儿子结点的关键词它的两个儿子结点的关键词. 我们我们把这样的数据结构称为堆把这样的数据结构称为堆( (极大堆极大堆) )。 极大极大(大根大根)堆堆 极小极小(小根小根)堆堆949375918544511848581034 例例 1 2 3 4 5 6 7 8 9 10

38、 11 12 94 93 75 91 85 44 51 18 48 58 10 34如果数组如果数组R中存放了堆，那么中存放了堆，那么R1是最大的记录，是最大的记录，将将R1和和Rn交换交换，使得最大记录放在，使得最大记录放在Rn的位的位置。置。949375918544511848581034 例例 1 2 3 4 5 6 7 8 9 10 11 12 94 93 75 91 85 44 51 18 48 58 10 34949375918544511848581034 例例 1 2 3 4 5 6 7 8 9 10 11 12 94 93 75 91 85 44 51 18 48 58 10

39、 34349375918544511848581094 例例 1 2 3 4 5 6 7 8 9 10 11 12 34 93 75 91 85 44 51 18 48 58 10 94然后然后对对R1，Rn-1进行调整，使它们构进行调整，使它们构成一个堆成一个堆。调整后，。调整后，R1是是R1，R2，Rn-1中最大的。然后再交换中最大的。然后再交换R1与与Rn-1 ，使，使R n - 1 中 放 入 次 最 大 的 记 录 。中 放 入 次 最 大 的 记 录 。349375918544511848581094 例例 1 2 3 4 5 6 7 8 9 10 11 12 34 93 75 9

40、1 85 44 51 18 48 58 10 94939175488544511834581094 例例 1 2 3 4 5 6 7 8 9 10 11 12 93 91 75 48 85 44 51 18 34 58 10 94109175488544511834589394 例例 1 2 3 4 5 6 7 8 9 10 11 12 10 91 75 48 85 44 51 18 34 58 93 94109175488544511834589394 例例 1 2 3 4 5 6 7 8 9 10 11 12 10 91 75 48 85 44 51 18 34 58 93 94再对再对R

41、1，R2，Rn-2进行调整，使之进行调整，使之成为新堆，再进行类似的交换和调整，反复进行，成为新堆，再进行类似的交换和调整，反复进行，直到调整范围只剩下一个记录直到调整范围只剩下一个记录R1为止。此时为止。此时R1是是n个记录中最小的，且数组个记录中最小的，且数组Rn中的记录中的记录已经按从小到大排列了。已经按从小到大排列了。堆排序算法的粗略描述如下：堆排序算法的粗略描述如下： （l）建立包含）建立包含Kl，K2，Kn的堆；的堆； （2）FOR in TO 2 STEP 1 DO （RlRi 重建包含重建包含Kl，K2，Ki1的堆）的堆） 堆排序堆排序:若在输出堆顶的最大值之后，使得剩余若在输

42、出堆顶的最大值之后，使得剩余n1个元素的序列重又建成一个堆，则得到个元素的序列重又建成一个堆，则得到n个元个元素中的次大值。如此反复执行，便能得到一个有素中的次大值。如此反复执行，便能得到一个有序序列。序序列。 堆排序需解决的两个问题：堆排序需解决的两个问题： 如何建堆；如何建堆； 输出堆顶元素后，如何调整新堆。输出堆顶元素后，如何调整新堆。重建堆重建堆R1与与Ri交换后，只有交换后，只有R1与其左右儿子不与其左右儿子不满足堆的性质满足堆的性质.如果根结点的儿子存在，则比较根和两个儿如果根结点的儿子存在，则比较根和两个儿子的关键词子的关键词.如果根结点的关键词大，则说明该如果根结点的关键词大，

43、则说明该结构已经是堆，终止重建过程结构已经是堆，终止重建过程. 如果根结点的关键词小，则它和关键词大如果根结点的关键词小，则它和关键词大的儿子进行交换，并以这个儿子为根结点的儿子进行交换，并以这个儿子为根结点继续重建下去继续重建下去. 10917548854451183458939410917548854451183458939410917548854451183458939491107548854451183458939491107548854451183458939491107548854451183458939491857548104451183458939491857548584451

44、1834109394算法算法Restore（R，f，e）/重重 建堆建堆R1 初始化初始化 jf R2 建堆建堆 WHILE j e/2 DO (IF(2j e)AND(K2j Kj THEN（RmRj . jm ） ELSE je ）重建堆演示重建堆演示 2 2 初始建堆初始建堆: :将序号为将序号为 n/2 , n/2-1 ,1的结点的结点作为根的子树都调整为堆即可。作为根的子树都调整为堆即可。 例例 关键字序列关键字序列（42,13,91,23,24,16,05,88)42,13,91,23,24,16,05,88)。42139123241605884213912324160588421

45、3918824160523421391882416052342889113241605234288911324160523428891232416051342889123241605139188422324160513初始建堆过程：初始建堆过程：91884223241605134213918824160523堆排序过程：堆排序过程：4288912324160513918842232416051342889123241605139188422324160513428891232416051313884223241605914288912324160513138842232416059142889

46、123241605138813422324160591428891232416051388134223241605914288912324160513882442231316059142889123241605138824422313160591428891232416051388244223131605914288912324160513052442231316889142889123241605134224162313058891堆排序过程：堆排序过程：4288912324160513052416231342889142889123241605132423160513428891堆排序过程

47、：堆排序过程：42889123241605134224162313058891堆排序过程：堆排序过程：428891232416051324231605134288914288912324160513132316052442889142889123241605132313160524428891堆排序过程：堆排序过程：428891232416051323131605244288914288912324160513051316232442889142889123241605131613052324428891堆排序过程：堆排序过程：428891232416051316130523244288914

48、288912324160513051316232442889142889123241605131305162324428891堆排序过程：堆排序过程：42889123241605131305162324428891428891232416051305131623244288914288912324160513051316232442889105 13 16 23 24 42 88 91算法算法HeapSort ( R，n ) / 堆排序算法堆排序算法 HS1 初始建堆初始建堆 FOR i n2 TO 1 STEP 1 DO Restore（R，i，n） HS2 排序排序 FOR in TO 2

49、 STEP 1 DO ( R1Ri . Restore ( R，1，i1 ) ) 堆排序演示堆排序演示堆排序算法堆排序算法时间复杂度时间复杂度: :O(nlogO(nlog2 2n)n)（包括最好、最坏和平（包括最好、最坏和平均）均） . . 稳定性：堆排序是稳定性：堆排序是不稳定的不稳定的排序方法。排序方法。空间复杂度：空间复杂度： O(1) . O(1) . 7.4 7.4 合并排序合并排序合并：合并：把两个或多个有序文件组成一个单一的把两个或多个有序文件组成一个单一的 有序文件。有序文件。两个文件的合并。两个文件的合并。 3 合并排序。合并排序。开始开始25574837129286332

50、5,5737,4812,9233,86第一次第一次合并合并25,37,48,5712,33,86,92第二次第二次合并合并12,25,33,37,48,57,86,92第三次第三次合并合并合并排序过程示例合并排序过程示例 假定文件（假定文件（Rt，Rt1，Rm）和文件）和文件（Rm1，Rn）都已经排序，如何合并这两）都已经排序，如何合并这两个文件，得到排序好的大文件（个文件，得到排序好的大文件（Xt，Xt1，Xn）；）； 执行合并过程，将文件执行合并过程，将文件R中长度为中长度为length的的所有子文件合并到文件所有子文件合并到文件X中；中；两个有序文件合并成一个大的有序文件两个有序文件合并

51、成一个大的有序文件 算法算法Merge (R，t，m，n . X)算法算法Merge()演示演示 M1 初始化给每个文件一个头指针初始化给每个文件一个头指针 it jm1 k1 M2 比较比较 i和和 j所指记录所指记录 WHILE（im） AND（jn） DO （IF KiKjTHEN（XkRi ii1）ELSE（XkRj jj1）. kk+1）. M3 复制余留记录项复制余留记录项 WHILE (im) Xk =Ri . ii1. kk+1. WHILE (jn) Xk =Rj . jj1. kk+1. t mm+1 nijXk两个有序文件合并成一个大的有序文件两个有序文件合并成一个大的有

52、序文件 算法算法Merge (R，t，m，n . X)算法算法Merge()演示演示 M1 初始化给每个文件一个头指针初始化给每个文件一个头指针 it jm1 k1 M2 比较比较 i和和 j所指记录所指记录 WHILE（im） AND（jn） DO （IF KiKjTHEN（XkRi ii1）ELSE（XkRj jj1）. kk+1）. M3 复制余留记录项复制余留记录项 WHILE (im) Xk =Ri . ii1. kk+1. WHILE (jn) Xk =Rj . jj1. kk+1. it mm+1 njXk 算法算法Merge (R，t，m，n. X) ： 假定文件假定文件（Rt

53、，Rt1，Rm）和文件（）和文件（Rm1，Rn）都已经排序，该算法合并这两个文件后得）都已经排序，该算法合并这两个文件后得到排序好的大文件（到排序好的大文件（Xt，Xt1，Xn）；）；算法算法MPass（R，n，1engthX） /* 一趟合并算法，该算法执行一趟合并过程，将文一趟合并算法，该算法执行一趟合并过程，将文件件R中长度为中长度为length的所有子文件合并到文件的所有子文件合并到文件X中，中，n是是R的记录个数的记录个数 */MP1 初始化初始化 i1 MP2 合并相邻的两个长度为合并相邻的两个长度为length的子文件的子文件 WHILE i n 2*length + 1 DO

54、（Merge（R，i，ilengthl，i2*length1X）. ii2*length ） MP3 处理余留的长度小于处理余留的长度小于2*length的子文件的子文件 IF i+length1 n THEN Merge（R，i，i+length1，n. X） ELSE FOR j = i TO n DO XjRj 1 . 1+length-11+length 1+2length-1i算法算法MPass（R，n，1engthX） /* 一趟合并算法，该算法执行一趟合并过程，将文一趟合并算法，该算法执行一趟合并过程，将文件件R中长度为中长度为length的所有子文件合并到文件的所有子文件合并到

55、文件X中，中，n是是R的记录个数的记录个数 */MP1 初始化初始化 i1 MP2 合并相邻的两个长度为合并相邻的两个长度为length的子文件的子文件 WHILE i n 2*length + 1 DO （Merge（R，i，ilengthl，i2*length1X）. ii2*length ） MP3 处理余留的长度小于处理余留的长度小于2*length的子文件的子文件 IF i+length1 n THEN Merge（R，i，i+length1，n. X） ELSE FOR j = i TO n DO XjRj 1 . 1+length-11+length 1+2length-1i 算

56、法算法MPass（R，n，lengthX）：一趟合并）：一趟合并算法，该算法执行一趟合并过程，将文件算法，该算法执行一趟合并过程，将文件R中长中长度为度为length的所有子文件合并到文件的所有子文件合并到文件X中，中，n是是R的记录个数，该函数调用的记录个数，该函数调用Merge()函数；函数；算法算法MSort(R，n) / 直接两路合并排序算法，X是辅助文件，其记录结构与R相同MS1 初始化 length1 MS2 交替合并 WHILE length n DO （MPass（R，n，lengthX）. length2*length MPass（X，n，lengthR）. length2*

57、length） 算法算法Merge (R，t，m，n. X) ： 假定文件假定文件（Rt，Rt1，Rm）和文件（）和文件（Rm1，Rn）都已经排序，该算法合并这两个文件后得）都已经排序，该算法合并这两个文件后得到排序好的大文件（到排序好的大文件（Xt，Xt1，Xn）；）； 算法算法Merge()演示演示 算法算法MPass（R，n，lengthX）：一趟合并）：一趟合并算法，该算法执行一趟合并过程，将文件算法，该算法执行一趟合并过程，将文件R中长中长度为度为length的所有子文件合并到文件的所有子文件合并到文件X中，中，n是是R的记录个数，该函数调用的记录个数，该函数调用Merge()函数；

58、函数；算法算法MPass()演示演示 算法算法MSort(R，n) ：该函数调用函数该函数调用函数Mpass(),Mpass(),直接两路合并排序，直接两路合并排序，X是辅助文件；是辅助文件；合并排序合并排序MSort(R，n) 演示演示 合并排序。合并排序。开始开始255748371292863325,5737,4812,9233,86第一次第一次合并合并25,37,48,5712,33,86,92第二次第二次合并合并12,25,33,37,48,57,86,92第三次第三次合并合并合并排序过程示例合并排序过程示例合并趟数：第一趟，合并长度为1的n个文件；第二趟，合并长度小于等于2的个文件；第 i 趟，合并长度小于等于2i-1的文件，得到的文件长度大于2i-1 ，且小于等于2i. 如果存在正整数k，使得2kn2k+1，合并排序共需要k+1趟合并(log