软件技术基础第三章2基本排序

《软件技术基础第三章2基本排序》由会员分享，可在线阅读，更多相关《软件技术基础第三章2基本排序（69页珍藏版）》请在金锄头文库上搜索。

1、冒泡排序与快速排序冒泡排序与快速排序( (交换排序法交换排序法) )简单插入排序与希尔排序简单插入排序与希尔排序( (插入排序法插入排序法) )简单选择排序与堆排序简单选择排序与堆排序( (选择排序法选择排序法) )其他排序方法简介其他排序方法简介 排序是数据处理的重要内容排序是数据处理的重要内容,是指将一个无序序列整是指将一个无序序列整理成按值非递减顺序排列的有序序列理成按值非递减顺序排列的有序序列(本章仅介绍内部排本章仅介绍内部排序序:即能够在内存中完成的排序即能够在内存中完成的排序)基本排序基本排序实质上实质上,我们可以对排序定义再抽象我们可以对排序定义再抽象即将无序序列整理成具有逻辑大

2、小即将无序序列整理成具有逻辑大小前驱后继排列的序列前驱后继排列的序列交换排序交换排序交换排序的思想是通过交换元素以达到消除逆序的目的交换排序的思想是通过交换元素以达到消除逆序的目的冒泡排序冒泡排序 (1)(1)从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断称之为消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动地将两相邻元素中的大

3、者往后移动，最后就将线性表中的最大者换，最后就将线性表中的最大者换到了表的最后。到了表的最后。 (2)(2)除去最后已经冒出的元素除去最后已经冒出的元素, ,对剩下的线性表重复上述过程，直到对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时冒出的元素构成的线性表已经变为有剩下的线性表变空为止，此时冒出的元素构成的线性表已经变为有序。序。逆序：在数组An中,存在iAj则称Ai和Aj构成一个逆序5 1 7 3 1 6 9 4 2 8 61 5 3 1 6 7 4 2 8 6 9第一遍1 3 1 5 6 4 2 7 6 8 9第二遍1 1 3 5 4 2 6 6 7 8 9第三遍1 1 3

4、4 2 5 6 6 7 8 9第四.五.六遍1 1 3 2 4 5 6 6 7 8 9第七遍1 1 2 3 4 5 6 6 7 8 9第八遍1 1 2 3 4 5 6 6 7 8 9第九.十.十一遍冒泡排序需要经过(n-1)+(n-2)+(n-3)+1=n(n-1)/2次比较算法复杂度量级为O(n2)双向冒泡排序双向冒泡排序 (1)(1)从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，则将它们互换，称之为消去了

5、一个逆序。显然，在扫描过程中，不称之为消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者，最后就将线性表中的最大者换到了表的最后。换到了表的最后。 (2)(2)从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，元素，则将它们互换，这样就又消去了一个逆序。显然，在扫描过这样就又消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中

6、的小者往前移动，程中，不断地将两相邻元素中的小者往前移动，最后就将剩下线性最后就将剩下线性表中的最小者换到了表的最前面表中的最小者换到了表的最前面 (3)(3)对剩下的线性表重复上述过程，直到剩下的线性表变空为止，对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。此时的线性表已经变为有序。 bubsort(pbubsort(p，n)n)intint n n； ET pET p； intint m m，k k，j j，i i； ET dET d； k k0 0； m mn n1 1； while (kwhile (km) /*m) /*子表未空子表未空* */ /

7、j jm m1 1； m m0 0； for(ifor(ik k；i ij j；i i) /*) /*从前往后扫描从前往后扫描* */ / if (pi if (pipipi1) /*1) /*发现逆序进行交换发现逆序进行交换* */ / d dpipi；pipipi+1pi+1；pi+1pi+1d d；m mi i； j jk k1 1； k k0 0； for (ifor (im m；i ij j；i i) /*) /*从后往前扫描从后往前扫描* */ / if (pi if (pi1 1 pi) /*pi) /*发现逆序进行交换发现逆序进行交换* */ / d dpipi；pipipi-

8、1pi-1；pi-1pi-1d d；k ki i； return return； 输入：无序序列输入：无序序列P(1：n)。输出：有序序列输出：有序序列P(1：n)。虽然从算法上优化了冒泡法虽然从算法上优化了冒泡法排序排序, ,但是其最坏算法复但是其最坏算法复杂度量级依然是杂度量级依然是O(nO(n2 2) ) 快速排序快速排序:解决冒泡排序中一次仅通过交换两个相邻元素完成一个解决冒泡排序中一次仅通过交换两个相邻元素完成一个逆序的消除的效率不高的问题逆序的消除的效率不高的问题快速排序的思想为快速排序的思想为:从线性表中取一个元素从线性表中取一个元素,设为设为T,小于小于T的元素移到的元素移到T

9、前前,大于大于T的元素移到的元素移到T后从而将线性表后从而将线性表以以T为分界分成两个子表为分界分成两个子表.关键是对线性表的分割关键是对线性表的分割.首首先先，在在表表的的第第一一个个、中中间间一一个个与与最最后后一一个个元元素素中中选选取取其其中中一一项项作为枢纽，作为枢纽，设为设为P(k)P(k)，并将并将P(k)P(k)赋给赋给T T，再将表中的第一个元素移到再将表中的第一个元素移到P(k)P(k)的位置上。的位置上。然后设置两个指针然后设置两个指针i i和和j j分别指向表的起始与最后的位置。反分别指向表的起始与最后的位置。反复作以下两步：复作以下两步：(1)(1)将将j j逐渐减小

10、，并逐次比较逐渐减小，并逐次比较P(j)P(j)与与T T，直到发现一个直到发现一个 P(j)P(j)T T为止，将为止，将P(j)P(j)移到移到P(i)P(i)的位置上。的位置上。(2)(2)将将i i逐渐增大，并逐次比较逐渐增大，并逐次比较P(i)P(i)与与T T，直到发现一个直到发现一个 P(i)P(i)T T为止，将为止，将P(i)P(i)移到移到P(j)P(j)的位置上。的位置上。上述两个操作交替进行，直到指针上述两个操作交替进行，直到指针i i与与j j指向同一个位置指向同一个位置（即（即i ij j）为止，为止，此时将此时将T T移到移到P(i)P(i)的位置上的位置上。算法

11、描述算法描述例例: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8493838656597977676131327274949ji49界点界点9e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8493838656597977676131327274949ji49界点界点10e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的

12、方法进行排序。0 1 2 3 4 5 6 7 8493838656597977676131327274949ji49界点界点11e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8493838656597977676131327274949ji49界点界点12e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8493838656597977676131327274949ji49界点

13、界点13e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8493838656597977676131327274949ji49界点界点14e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8493838656597977676131327274949ji49界点界点15e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的

14、方法进行排序。0 1 2 3 4 5 6 7 8493838656597977676131327274949ji49界点界点16e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8493838656597977676131327274949ji49界点界点17e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8493838656597977676131327274949ji49界点

15、界点18e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8493838656597977676131327274949ji49界点界点19e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8493838656597977676131327274949ji49界点界点20e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的

16、方法进行排序。0 1 2 3 4 5 6 7 8493838656597977676131327274949ji49界点界点21e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8273838136597497676139765274949ji49界点界点22e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8273838136597497676139765274949ji49界点

17、界点23e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8273838136597497676139765274949ji49界点界点24e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8273838136597497676139765274949ji49界点界点25e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的

18、方法进行排序。0 1 2 3 4 5 6 7 8273838136597497676139765274949ji49界点界点26e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8133827386597497676139765274949i49界点界点j27e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8133827386597497676139765274949ji49界点

19、界点28e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8133827386597497676139765274949ji49界点界点29e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8133827386597497676139765274949i49界点界点j30e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的

20、方法进行排序。0 1 2 3 4 5 6 7 8133827386597497676139765274949ji49界点界点31e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8133827386597497676139765274949ji49界点界点32e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8133827386597497676139765274949ji49界点

21、界点33e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8133827386597497676139765274949ji49界点界点34e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8133827386597494976136576274997ji49界点界点35e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的

22、方法进行排序。0 1 2 3 4 5 6 7 8133827386597494976136576274997ji49界点界点36e.g: 将序列将序列 49、38、65、97、76、13、27、49 用用 快速排序的方法进行排序。快速排序的方法进行排序。0 1 2 3 4 5 6 7 8133827386597494976136576274997ji49界点界点快速快速排序结束排序结束37void quicksort (element list , int left, int right) /* sort listleft, ., listright into non-decreasing l

23、ist. listleft.key is the pivot key and listleft.key listright+1.key. The function call is quicksort( list, 0, n 1 ) */ int pivot, i, j ;element temp; if ( left right ) i = left ; j = right + 1; pivot = list left .key ; do do i +; while (list i .key pivot); /* find out-of-order key from right */ if (

24、 i j ) SWAP( list i , list j , temp ); while ( i j ); SWAP( list left , list j , temp ); /* put pivot at right position */ quicksort( list, left, j 1); quicksort( list, j+1, right); /* end if */ 最坏情况最坏情况: Tp = O( ? )n2出现在原序列已经有序出现在原序列已经有序. 幸运情况幸运情况: . . . . 平均情况平均情况: T ( n ) = O( n ) + 2 T ( n / 2 )

25、 = O( n ) + 2 O( n / 2 ) + 2 T ( n / 22 ) = 2 O( n ) + 22 T ( n / 22 ) = . . = k O( n ) + 2k T ( n / 2k )n / 2k = 1 k = log2 n= O( n log2 n ) + n T ( 1 )= O( n log2 n )快速排序的非递归算法快速排序的非递归算法输入：待排序的子表输入：待排序的子表P(mP(m：n)n)。输出：有序子表输出：有序子表P(mP(m：n)n)。PROCEDURE QKSORT2(PPROCEDURE QKSORT2(P，m m，n)n)建立一个栈，并初始

26、化建立一个栈，并初始化 栈中每一个元素有两个数据项：子表第一个元素下栈中每一个元素有两个数据项：子表第一个元素下标与最后一个元素下标标与最后一个元素下标 将下标将下标m m与与n n进栈进栈 子表进栈子表进栈 WHILE WHILE 栈非空栈非空 DO DO 还有子表需要分割还有子表需要分割 从栈中退出两个下标从栈中退出两个下标m m与与n n 从栈中退出一个子表进行分割从栈中退出一个子表进行分割 WHILE (n WHILE (nm) DO m) DO 子表不空子表不空 SPLIT(P SPLIT(P，m m，n n，i) i) 进行分割进行分割 将下标将下标i i1 1与与n n进栈进栈

27、将分割出的后一个子表进栈将分割出的后一个子表进栈 n ni i1 1 对分割出前一个子表继续进行分割对分割出前一个子表继续进行分割 RETURNRETURN前面是通过前面是通过交换交换来消除逆序来消除逆序,下面采用下面采用插入插入简单插入排序简单插入排序(插入类排序插入类排序) 将将无序序列无序序列中的各元素依次插入中的各元素依次插入已有序已有序的线性表中的线性表中 输入：待排序序列输入：待排序序列P(1P(1：n)n)。 输出：有序序列输出：有序序列P(1P(1：n)n)。PROCEDURE INSORT(PPROCEDURE INSORT(P，n)n) FOR j FOR j2 TO n

28、DO2 TO n DO T TP(j)P(j)；k kj j1 1 WHILE (k WHILE (k0)and(P(k)0)and(P(k)T) DOT) DO P(k P(k1)1)P(k)P(k)；k kk k1 1 P(k P(k1)1)T T RETURN RETURN5 1 7 3 1 6 9 4 2 8 65 1 7 3 1 6 9 4 2 8 6 j j2 21 1 5 7 3 1 6 9 4 2 8 6 5 7 3 1 6 9 4 2 8 6 j j3 31 5 1 5 7 7 3 1 6 9 4 2 8 6 3 1 6 9 4 2 8 6 j j4 41 1 3 3 5 7

29、 1 6 9 4 2 8 6 5 7 1 6 9 4 2 8 6 j j5 51 1 1 1 3 5 7 6 9 4 2 8 6 3 5 7 6 9 4 2 8 6 j j6 61 1 3 5 1 1 3 5 6 6 7 9 4 2 8 6 7 9 4 2 8 6 j j7 71 1 3 5 6 7 1 1 3 5 6 7 9 9 4 2 8 6 4 2 8 6 j j8 81 1 3 1 1 3 4 4 5 6 7 9 2 8 6 5 6 7 9 2 8 6 j j9 91 1 1 1 2 2 3 4 5 6 7 9 8 6 3 4 5 6 7 9 8 6 j j10101 1 2 3 4

30、5 6 7 1 1 2 3 4 5 6 7 8 8 9 6 9 6 j j11111 1 2 3 4 5 6 1 1 2 3 4 5 6 6 6 7 8 9 7 8 9 简单插入排序在最坏情况下需要比较简单插入排序在最坏情况下需要比较简单插入排序在最坏情况下需要比较简单插入排序在最坏情况下需要比较n(n-1)/2n(n-1)/2n(n-1)/2n(n-1)/2次次次次 insort(pinsort(p，n)n) intint n n； ET pET p； intint j j，k k； ET tET t； for (jfor (j1 1； j jn n； j j) ) t tpjpj； k k

31、j j1 1； while (kwhile (k0)&(pk0)&(pkt)t) pk pk11pkpk； k kk k1 1； pk pk11t t； return return； 基本思想基本思想: :将整个无序序列将整个无序序列分割分割成若干成若干小子序列小子序列分别进行分别进行插入排序插入排序子序列的分割方法如下：子序列的分割方法如下： 将相隔将相隔某个增量某个增量h h的元素构成一个子序列。在排序过程中，的元素构成一个子序列。在排序过程中，逐次减小逐次减小这个增量这个增量，最后当，最后当h h减到减到1 1时时，进行一次插入排序，排序就完成。，进行一次插入排序，排序就完成。 增量序列

32、一般取增量序列一般取 h ht tn/2n/2k k(k(k1 1，2 2，loglog2 2n)n)， 其中其中n n为待排序序列的长度。为待排序序列的长度。希尔排序希尔排序(插入类排序插入类排序) shlsort(pshlsort(p，n)n)intint n n； ET pET p； intint h h，j j，i i； ET tET t； h hn/2n/2； while (hwhile (h0)0) for (j for (jh h； j jn n1 1； j j) ) t tpjpj； i ij jh h； while (iwhile (i0)&(pi0)&(pit)t) pi

33、pihhpipi； i ii ih h； pi pihht t； h hh/2h/2； return return； 输入：待排序序列输入：待排序序列P(1P(1：n)n)。 输出：有序序列输出：有序序列P(1P(1：n)n)。代码比较代码比较insort(pinsort(p，n)n)intint n n； ET pET p intint j j，k k； ET tET t； for (jfor (j1 1； j jn n； j j) ) t tpjpj ； k kj j1 1； while (kwhile (k0)&(pk0)&(pkt) t) pkpk11pkpk ； k kk k1 1；

34、 pkpk11t t； return return shlsort(pshlsort(p，n)n)intint n n； ET pET p； intint h h，j j，i i； ET tET t； h hn/2n/2； while (hwhile (h0) 0) for (j for (jh h； j jn n1 1； j j) t tpjpj ； i ij jh h； while (iwhile (i0)&(pi0)&(pit)t) pipihhpipi ； i ii ih h； pipihht t； h hh/2h/2； return return； 选择排序选择排序1.简单选择排序简

35、单选择排序 基基本本思思想想: :扫扫描描线线性性表表,选选出出最最小小的的元元素素,交交换换到到最最前前,然然后后对对剩剩余余的的元元素素采采用用相相同同的的方方法法,直直到到表表空空.对对长长度为度为n的序列的序列,选择排序需要扫描选择排序需要扫描n-1次次注意,这里的方法和冒泡法排序有区别选择vs冒泡冒泡:目的在于减少逆序,通过遇到相邻构成逆序就交换的的方式,逐步将最小(大)元素冒到最前选择:目的在于选取最小(大)元素,通过扫描寻找方式,直接和最前(后)元素进行一次交换.简单选择排序在最坏情况下需要比较简单选择排序在最坏情况下需要比较简单选择排序在最坏情况下需要比较简单选择排序在最坏情况

36、下需要比较n(n-1)/2n(n-1)/2n(n-1)/2n(n-1)/2次次次次 selesort(pselesort(p，n)n)intint n n； ET pET p； intint i i，j j，k k； ET dET d； for (ifor (i0 0； i in n2 2； i ii i1)1) k ki i； for (jfor (ji i1 1； j jn n1 1； j jj j1)1) if (pj if (pjpk) kpk) kj j； if (k!if (k!i) di) dpipi；pipipkpk；kkd d； return return； 输入：无序序列输

37、入：无序序列P(1P(1：n)n)。输出：有序序列输出：有序序列P(1P(1：n)n)。前面介绍过的一个数据结构用于前面介绍过的一个数据结构用于选择排序将会很方便选择排序将会很方便?谁能说出是谁能说出是哪种数据结构哪种数据结构?堆排序堆排序(选择排序的一种选择排序的一种)复习复习:堆的定义：堆的定义：具有具有n n个元素的序列个元素的序列(h(h1 1，h h2 2，h hn n) )，当且仅当满足当且仅当满足 或或 (i(i1 1，2 2，n/2)n/2)时称之为堆。时称之为堆。序序 列列 (91(91， 8585， 5353， 3636， 4747， 3030， 2424， 12)12)是

38、是 一一 个个 堆堆如何调整建堆如何调整建堆 在一棵具有在一棵具有n n个结点的完全二叉树（用一维数组个结点的完全二叉树（用一维数组H(1H(1：n)n) 表示）中，假设结点表示）中，假设结点H(m)H(m)的左右子树均为堆，现要将以的左右子树均为堆，现要将以 H(m)H(m)为根结点的子树也调整为堆。为根结点的子树也调整为堆。具体的步骤具体的步骤: : 将将根结点值与左右子树的根结点值进行比较根结点值与左右子树的根结点值进行比较, ,若不满足堆的条件若不满足堆的条件, ,则将则将左右子树的根结点值中的大者与根结点值进行左右子树的根结点值中的大者与根结点值进行交换交换. .此调整过程此调整过程

39、一直一直做到所有子树均为堆为止做到所有子树均为堆为止调整建堆调整建堆已知已知H.rsH.rsmm中记录的关键字除中记录的关键字除H.rs.keyH.rs.key之外均满足堆的定义，本汉之外均满足堆的定义，本汉书调整书调整H.rsH.rs 的关键字，使的关键字，使H.rsH.rsmm成为一个大顶堆（对其中记录的关成为一个大顶堆（对其中记录的关键字而言）键字而言） Void Void HeapAdjust(HeapTypeHeapAdjust(HeapType & &H,intH,int s, s, intint m) m) rcrc = = H.rsH.rs;for (j=2*s; j=m; j

40、*=2)for (j=2*s; j=m; j*=2)if ( jm & if ( jm & H.rj.keyH.rj.keyH.rj+1.key) +j;= = H.rj.keyH.rj.key) break;) break;H.rsH.rs = = H.rjH.rj; ; s = j;s = j; H.rsH.rs = = rcrc; ; 由堆的定义由堆的定义, ,可得堆排序的方法为可得堆排序的方法为: :(1)(1)首先将一个无序序列建成堆。首先将一个无序序列建成堆。(2)(2)然后将堆顶元素（序列中的最大项）与堆中最后一个然后将堆顶元素（序列中的最大项）与堆中最后一个 元素交换（最大项应

41、该在序列的最后）。元素交换（最大项应该在序列的最后）。 不考虑已经换到最后的那个元素，只考虑前不考虑已经换到最后的那个元素，只考虑前n n1 1个元个元 素构成的子序列，显然，该子序列已不是堆，但左、素构成的子序列，显然，该子序列已不是堆，但左、 右子树仍为堆，可以将该子序列调整为堆。右子树仍为堆，可以将该子序列调整为堆。 反复做第反复做第(2)(2)步，直到剩下的子序列为空为止。步，直到剩下的子序列为空为止。堆排序堆排序输入：无序序列输入：无序序列H(1H(1：n)n)。输出：无序序列输出：无序序列H(1H(1：n)n)。heapsort(HeapTypeheapsort(HeapType

42、&H &H，intint n) n) intint i i；HeapTypeHeapType temp; temp;for (i=n/2; i0; -i)for (i=n/2; i0; -i)HeapAdjustHeapAdjust( H, i, n);( H, i, n);for (i = n; i1; -i)for (i = n; i1; -i)temp = H.r1;temp = H.r1;H.r1 = H.r1 = H.riH.ri;H.riH.ri = temp; = temp;HeapAdjustHeapAdjust( H, 1, i-1);( H, 1, i-1); 平均时间复杂

43、度是平均时间复杂度是O(nlogn)最坏情况下的时间复杂度是最坏情况下的时间复杂度是O(nlogn)Good!堆排序方法对于记录数较少的文件并不值得提倡,但对n较大的文件还是很有效的.因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复”筛选”上.对深度为k的堆,筛选算法中进行的关键字比较次数至多为2(k-1)次,则建含n个元素,深度为h的堆时,总共进行的关键字比较次数不超过4n.又,n个结点的完全二叉树的深度为logn+1,则调整建立新堆时调用HeapAdjust过程n-1次,总共进行的比较次数不超过下式的值:2(log(n-1)+log(n-2)+log2)2nlogn所谓归并是将两个

44、或两个以上的有序表合并成一个新的有序表所谓归并是将两个或两个以上的有序表合并成一个新的有序表 设线性表设线性表L(1：n)中的某段中的某段L(low：high)已经部分有序，即它的两个已经部分有序，即它的两个子表子表L(low：mid)与与L(mid1：high)（其中其中lowmidhigh）已经有序，已经有序，现要将这两个有序子表归并成一个有序子表现要将这两个有序子表归并成一个有序子表L(low：high)。归并排序归并排序请翻到p106见2.7,2.11我们已经学会将两个有序序列合并成一个有序序列的方法实现上述两个子表归并的基本做法如下：实现上述两个子表归并的基本做法如下：(1)(1)开

45、辟一个与线性表开辟一个与线性表L L同样大小的表空间同样大小的表空间A A。(2)(2)设置三个指针设置三个指针i i，j j，k k，其初始状态分别指向两个有序子其初始状态分别指向两个有序子 表的首部及表空间表的首部及表空间A A中与中与L L中需要进行排序段相对应空间中需要进行排序段相对应空间 的首部。即的首部。即i ilowlow，j jmidmid1 1，k klowlow。(3)(3)沿两个有序子表扫描：沿两个有序子表扫描： 若若L(i)L(j)L(i)L(j)，则，则A(k)A(k)L(i)L(i)，且，且i i与与k k指针均加指针均加1 1； 否则否则A(k)A(k)L(j)L

46、(j)，且，且j j与与k k指针均加指针均加1 1。 如此反复，直到有一个子表的指针已经指到末端（即子如此反复，直到有一个子表的指针已经指到末端（即子 表内的元素已经取空）为止。表内的元素已经取空）为止。(4)(4)将未取空的子表中的剩余元素依次放入表空间将未取空的子表中的剩余元素依次放入表空间A A中。中。(5)(5)将将A A中的对应段复制到中的对应段复制到L L中。中。复习复习两个相邻有序子表的合并两个相邻有序子表的合并输入：两个相邻有序子表输入：两个相邻有序子表L(lowL(low：mid)mid)与与L(midL(mid1 1：high)high) （其中其中lowmidhighl

47、owmidhigh）；）；工作数组工作数组A(lowA(low：high)high)。输出：有序子表输出：有序子表L(lowL(low：high)high)。static static merge(pmerge(p，lowlow，midmid，highhigh，a)a)intint low low，midmid，high;EThigh;ET p p，aa； intint I I，j j，k k； i ilowlow； j jmidmid1 1； k klowlow； while (iwhile (imid)&(jmid)&(jhigh)high) if ( if (pipi11pjpj1) 1

48、) akak11pipi11； i ii i1 1； else else akak11pjpj11； j jj j1 1； k kk k1 1； if (i if (imid)mid) for(jfor(ji i； j jmidmid； j j) akak11pjpj11； k kk k1 1； else else if (j if (jhigh)high) for(ifor(ij j； i ihighhigh； i i) akak11pipi11； k kk k1 1； for(ifor(ilowlow；iihighhigh；i i) ) pipi11aiai11； returnreturn

49、； 归并排序是指把归并排序是指把一个长度为一个长度为N的线性表看成是由的线性表看成是由N个长度个长度为为1的有序表组成的的有序表组成的,然后进行两两归并然后进行两两归并,最后得到长度为最后得到长度为N的的有序线性表有序线性表,由于归并是两两进行的由于归并是两两进行的,因此也称为因此也称为2路归并排序路归并排序一趟一趟归并之后归并之后两趟归并之后两趟归并之后归并排序的非递归算法归并排序的非递归算法输入：无序序列输入：无序序列P(1P(1：n)n)。输出：有序序列输出：有序序列P(1P(1：n)n)。 #include #include stdlib.hstdlib.h mergsort(pmer

50、gsort(p，n)n)intint n n；ET pET p； intint m m，k k，j j，lowlow，highhigh，midmid； ET *aET *a； a amalloc(nmalloc(n* *sizeof(ETsizeof(ET)； m m1 1； while (mwhile (mn)n) k k2*m2*m； for(jfor(j1 1； j jn n； j jj jk)k) low lowj j； highhighj jk k1 1； midmidj jm m1 1； if (highif (highn) highn) highn n； if (highif (

51、highmid) mid) merge(p,low,mid,high,amerge(p,low,mid,high,a) )； m mk k； free(afree(a) )； returnreturn； 基数排序基数排序:分别依次对有效数字进行排序分别依次对有效数字进行排序l基数排序的最低位优先法基数排序的最低位优先法（LSDLeast Significant Digit first） 从有效数字的最低位开始直到最高位，对于每一位有效数字对线从有效数字的最低位开始直到最高位，对于每一位有效数字对线性表进行重新排列，其调整的原则为：性表进行重新排列，其调整的原则为： (1)(1)将线性表依当前位

52、的有效数字为序排列；将线性表依当前位的有效数字为序排列； (2)(2)当前位的有效数字相同时，按原次序排列。当前位的有效数字相同时，按原次序排列。l基数排序的最高位优先法基数排序的最高位优先法（MSDMost Significant Digit first）。）。在这种方法中，是从有效数字的最高位开始直到最低位在这种方法中，是从有效数字的最高位开始直到最低位行调整。在这种情况下，必须将线性表按有效位从高到低逐层分行调整。在这种情况下，必须将线性表按有效位从高到低逐层分割成若干子表，然后对各子表独立进行排序。割成若干子表，然后对各子表独立进行排序。1. MSD ( Most Significan

53、t Digit ) Sort(高位优先法高位优先法) Sort on K 0: 扑克牌有四种花色扑克牌有四种花色3 3 5 5 A A 4 4 先按照每种花色进行排序先按照每种花色进行排序 (using insertion sort)按大小依次放入堆栈按大小依次放入堆栈 2. LSD ( Least Significant Digit ) Sort(低位优先法低位优先法) Sort on K 1: 按值分成按值分成13类类2 2 3 3 4 4 5 5 A A . 重新组合重新组合A A 3 3 2 2 分花色分花色 按按末位末位排序排序: 01 ,31 ,11, 21, 02, 13, 05

54、, 26, 16, 27, 19 ,09按按首位排序首位排序: 01, 02 ,05, 09 , 11, 13, 16, 19, 21, 26, 27, 31冒泡排序冒泡排序 n(nn(n1)/2 1)/2 快速排序快速排序 n(nn(n1)/21)/2简单插入排序简单插入排序 n(nn(n1)/2 1)/2 希尔排序希尔排序 O(nO(n1.51.5) )简单选择排序简单选择排序 n(nn(n1)/2 1)/2 堆排序堆排序 O(nlogO(nlog2 2n)n)归并排序归并排序 O(nlogO(nlog2 2n)n)相关结论相关结论: : (1)(1)从平均时间上看从平均时间上看, ,快速

55、排序时间最省快速排序时间最省, ,但快速排序在最坏情况下时间但快速排序在最坏情况下时间性能不如堆排序和归并排序性能不如堆排序和归并排序; ;堆排序和归并排序两者比较堆排序和归并排序两者比较, ,在在N N较大时较大时归并排序时间省归并排序时间省, ,但需辅助存储量最多但需辅助存储量最多. . (2) (2)从方法稳定性来比较从方法稳定性来比较, ,快速排序快速排序, ,堆排序和希尔排序等时间性能较好堆排序和希尔排序等时间性能较好的排序方法稳定性不好的排序方法稳定性不好, ,即排序过程中的即排序过程中的“比较比较”在相邻记录间是稳在相邻记录间是稳定的定的, ,排序方法稳定性是由方法本身决定的排序方法稳定性是由方法本身决定的, ,对不稳定排序方法对不稳定排序方法, ,无论无论如何描述如何描述, ,都总能找到一种不稳定的实例都总能找到一种不稳定的实例排序方法小结排序方法小结本章内容本章内容l查找:顺序查找,有序查找,分块查找,二叉排序树查找,hash查找l排序:交换类排序(冒泡排序和快速排序),插入类排序(插入排序和希尔排序),选择类排序(选择排序和堆排序),归并排序,基数排序,拓扑排序这章是考试重点这章是考试重点,做点题目熟悉一下做点题目熟悉一下