各種經(jīng)典排序算法

1、排排 序序本節(jié)基本內(nèi)容與要求本節(jié)基本內(nèi)容與要求o基本內(nèi)容基本內(nèi)容n順序查找、二分查找、二叉樹查找以及散列表上查找順序查找、二分查找、二叉樹查找以及散列表上查找 及算法思想及算法思想n排序的基本概念以及選擇、插入、交換和歸并四類排排序的基本概念以及選擇、插入、交換和歸并四類排序的基本思想和算法序的基本思想和算法o要求要求n掌握線性表、樹和散列表掌握線性表、樹和散列表(或稱哈希表或稱哈希表)的查找方法及的查找方法及算法實現(xiàn)以及各種查找方法的應用算法實現(xiàn)以及各種查找方法的應用n熟練掌握選擇、插入、交換和歸并四類排序的基本思熟練掌握選擇、插入、交換和歸并四類排序的基本思想和算法想和算法排排 序序1.4

2、 內(nèi)部排序內(nèi)部排序一、基本概念一、基本概念二、插入排序二、插入排序三、交換排序三、交換排序四、選擇排序四、選擇排序五、歸并排序五、歸并排序排排 序序一、基本概念一、基本概念1. 排序的功能排序的功能：將一個數(shù)據(jù)元素（或記錄）：將一個數(shù)據(jù)元素（或記錄）的的任意序列任意序列，重新排成一個按關鍵字，重新排成一個按關鍵字有有序序的序列。的序列。例如例如：下列是一組記錄對應的關鍵字序列下列是一組記錄對應的關鍵字序列(52, 49, 80, 36, 14, 58, 61, 23, 97, 75)調(diào)整為調(diào)整為(14, 23, 36, 49, 52, 58, 61 ,75, 80, 97)排排 序序2. 排序

3、的定義排序的定義假設含假設含n個記錄的序列為個記錄的序列為 R1, R2, ， Rn 其相應的關鍵字序列為其相應的關鍵字序列為 K1, K2, ，Kn 這些關鍵字相互之間可以進行比較，即在這些關鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關系它們之間存在著這樣一個關系 ： Kp1Kp2Kpn按此固有關系將上式記錄序列重新排列為按此固有關系將上式記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作稱作的操作稱作排序排序。排排 序序3、排序的基本操作、排序的基本操作o排序的概念：排序的概念：就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。o排序過程的組成步驟排序過程的組

4、成步驟：首先比較兩個關鍵字的大?。?然后將記錄從一個位置移動到另一個位置。n對記錄的關鍵字大小進行比較n將記錄從一個位置移動到另一個位置o當待排序記錄的關鍵字均不相同時，則排序結果是唯一的，否則排序的結果不一定唯一。排排 序序4、排序的穩(wěn)定性、排序的穩(wěn)定性若有：若有： R1 ,., Ri,.,Rj,.且關鍵字：且關鍵字： Ki=Kj ij排序后：排序后： Ri,Rj,.則稱該排序結果具有穩(wěn)定性。則稱該排序結果具有穩(wěn)定性。在待排序的文件中，若存在在待排序的文件中，若存在多個關鍵字相同的記錄，經(jīng)多個關鍵字相同的記錄，經(jīng)過排序后這些具有相同關鍵過排序后這些具有相同關鍵字的記錄之間的字的記錄之間的相對

5、次序相對次序保保持持不變不變，該排序方法是，該排序方法是穩(wěn)定穩(wěn)定的；的；若具有相同關鍵字的記錄之若具有相同關鍵字的記錄之間的間的相對次序相對次序發(fā)生發(fā)生變化變化，則，則稱這種排序方法是稱這種排序方法是不穩(wěn)定不穩(wěn)定的。的。排排 序序o內(nèi)部排序內(nèi)部排序：是指在排序的整個過程中，：是指在排序的整個過程中，數(shù)據(jù)數(shù)據(jù)全部存放全部存放在計算機的在計算機的內(nèi)存內(nèi)存儲器里，并且在內(nèi)存儲器里調(diào)整數(shù)據(jù)儲器里，并且在內(nèi)存儲器里調(diào)整數(shù)據(jù)的位置；的位置；o當文件很大以致內(nèi)存不足以存放全部數(shù)據(jù)時，在排序當文件很大以致內(nèi)存不足以存放全部數(shù)據(jù)時，在排序過程中需要對過程中需要對外存外存進行存取訪問，稱這種借助于外存進行存取訪問

6、，稱這種借助于外存儲器進行排序的方法為儲器進行排序的方法為外部排序外部排序。o注意：注意：n 內(nèi)排序適用于記錄個數(shù)不很多的小文件內(nèi)排序適用于記錄個數(shù)不很多的小文件n 外排序則適用于記錄個數(shù)太多，不能一次將其外排序則適用于記錄個數(shù)太多，不能一次將其全部記錄放入內(nèi)存的大文件。全部記錄放入內(nèi)存的大文件。5、排序的分類、排序的分類排排 序序 o每次將一個待排序的記錄，按其關鍵字大小插入到前面每次將一個待排序的記錄，按其關鍵字大小插入到前面已經(jīng)排好序的子文件中的適當位置，直到全部記錄插入已經(jīng)排好序的子文件中的適當位置，直到全部記錄插入完成為止。完成為止。o把新元素（未排序的元素的關鍵字）逐個插入正在增長

7、把新元素（未排序的元素的關鍵字）逐個插入正在增長的順序表中。的順序表中。o尋找插入位置的方法尋找插入位置的方法：n線性插入排序線性插入排序n對半插入排序?qū)Π氩迦肱判騨希爾排序希爾排序二、插入排序二、插入排序排排 序序有序序列L.r1.i-1L.ri無序序列 L.ri.n有序序列L.r1.i無序序列 L.ri+1.n1、線性插入排序、線性插入排序o基本思想：基本思想：每步將一個待排序的元素按其大小插入到前每步將一個待排序的元素按其大小插入到前面已排序的數(shù)據(jù)中的適當位置。面已排序的數(shù)據(jù)中的適當位置。重復該工作，直至有序重復該工作，直至有序區(qū)包含所有元素。區(qū)包含所有元素。排排 序序方法方法：o具體方

8、法具體方法：先將第一個數(shù)據(jù)看成是一個有序的子序列，：先將第一個數(shù)據(jù)看成是一個有序的子序列，然后從第然后從第2個數(shù)據(jù)起逐個插入到這個有序的子序列中去，個數(shù)據(jù)起逐個插入到這個有序的子序列中去，相應的元素要移動。相應的元素要移動。3將將L.ri 插入插入到到L.rj+1的位置上。的位置上。2將將L.rj+1.i-1中的所有中的所有記錄記錄均均后移后移 一個位置；一個位置；1在在L.r1.i-1中中查找查找L.ri的插入位置，的插入位置， L.r1.j L.ri L.rj+1.i-1；排排 序序該算法適合于該算法適合于n n 較較小的情況，時間復小的情況，時間復雜度為雜度為O(nO(n2 2).).待

9、排元素序列：待排元素序列：5353 27 36 15 69 42 27 36 15 69 42第一次排序：第一次排序： 27 5327 53 36 15 69 42 36 15 69 42第二次排序：第二次排序： 27 36 5327 36 53 15 69 42 15 69 42第三次排序：第三次排序： 15 27 36 5315 27 36 53 69 42 69 42第四次排序：第四次排序： 15 27 36 53 6915 27 36 53 69 42 42第五次排序：第五次排序： 15 27 36 42 53 6915 27 36 42 53 69 線性插入排序示例線性插入排序示例對

10、于有對于有n n個數(shù)個數(shù)據(jù)元素的待排據(jù)元素的待排序列，插入操序列，插入操作要進行作要進行n-1n-1次次例：例：排排 序序void insertSort(RedType L ,int n) int i ,j; for(i=2; i=n; i+) L0=Li; / 作為監(jiān)視哨 for( j=i-1; L0.keyLj.key; j ) Lj+1=Lj; /記錄后移 Lj+1=L0; / 插入 插入算法插入算法o方法:Ki與Ki-1,K i-2,K1依次比較,直到找到應插入的位置。排排 序序哨兵哨兵( (監(jiān)視哨監(jiān)視哨) )o哨兵(監(jiān)視哨)有兩個作用n作為臨時變量存放Ri(當前要進行比較的關鍵字)的

11、副本；n在查找循環(huán)中用來監(jiān)視下標變量j是否越界。R0 R1 R2 R3 R4 R5 6 206157315 62015737 6152073367152033671520直接插入排序的程序：直接插入排序的程序： #include stdio.h #define n 5 int arn; int c,t; void d_insort(a) int an; int i,j; for (i=2;i0) & (taj) aj+1=aj; j=j-1; aj+1=t; main() int i; printf(請輸入數(shù)據(jù)請輸入數(shù)據(jù): ); for (i=1;i=n;i+) scanf(%d,&a

12、mp;ari); d_insort(ar); printf(排序后的序列排序后的序列: ); for (i=1;i=n;i+) printf(%d |,ari); printf(n); 運行結果：運行結果：請輸入數(shù)據(jù)請輸入數(shù)據(jù): 50 60 20 40 80排序后的序列排序后的序列: 20 |40 |50 |60 |80 |排排 序序性能分析性能分析最好情況（原始記錄按關鍵字有序排列）：最好情況（原始記錄按關鍵字有序排列）：O（n）“比較”的次數(shù)：最壞情況（原始記錄按關鍵字逆序排列）：最壞情況（原始記錄按關鍵字逆序排列）：O（n2）“比較”的次數(shù)：112nni02) 1)(4() 1(2nni

13、ni“移動”的次數(shù)：“移動”的次數(shù)：2) 1n)(4n () 1i (n2i結論：適用原始數(shù)據(jù)基本有序或數(shù)據(jù)量不大的情況。排排 序序 希爾排序（希爾排序（Shells method）又稱為）又稱為“縮小增量排序縮小增量排序” ，本質(zhì)上講是插入排序，它是對線性插入排序的改進。本質(zhì)上講是插入排序，它是對線性插入排序的改進。其基本思想是：其基本思想是： 先取一個小于先取一個小于n的整數(shù)的整數(shù)d1并作為第一個增量，并作為第一個增量，將文件將文件的全部記錄分成的全部記錄分成d1個組，所有距離為個組，所有距離為d1倍數(shù)的記錄放在同倍數(shù)的記錄放在同一個組中，在各組內(nèi)進行直接插入排序；一個組中，在各組內(nèi)進行直

14、接插入排序； 然后取第二個增量然后取第二個增量d2d1，重復上述的分組和排序，重復上述的分組和排序，直至所取的增量直至所取的增量dt=1 (dtdt 1d2d1)為止，此時，所為止，此時，所有的記錄放在同一組中進行直接插入排序。有的記錄放在同一組中進行直接插入排序。 2 2 希爾插入排序希爾插入排序算法思想算法思想排排 序序o如何選擇增量序列才能產(chǎn)生最好的排序效果，這個問題如何選擇增量序列才能產(chǎn)生最好的排序效果，這個問題至今沒有得到解決。至今沒有得到解決。o希爾本人最初提出取希爾本人最初提出取nd1=d1= n/2n/2 ，ndi+1=di+1= di/2di/2 ，ndt=1dt=1，t=t

15、= log2nlog2n 。排排 序序希爾插入排序希爾插入排序步驟步驟（1 1）首先選取一個整數(shù)）首先選取一個整數(shù)d d11n n（n n為待排序數(shù)據(jù)的個數(shù)），為待排序數(shù)據(jù)的個數(shù)），作為兩個數(shù)據(jù)之間的作為兩個數(shù)據(jù)之間的距離距離，這樣把全部數(shù)據(jù)分成，這樣把全部數(shù)據(jù)分成d d1 1個組，個組，凡是距離為凡是距離為d d1 1的數(shù)據(jù)放在一個組里，在各組內(nèi)進行內(nèi)部的數(shù)據(jù)放在一個組里，在各組內(nèi)進行內(nèi)部排序，直到各組排好序為止。排序，直到各組排好序為止。（2 2）從上述的結果序列出發(fā)，再選擇）從上述的結果序列出發(fā)，再選擇d d22d d1 1，重復上面的，重復上面的分組與排序工作。分組與排序工作。（3 3

16、）依次?。┮来稳idi+1+1didi，直到，直到dmdm=1=1（設一共需要（設一共需要m m次分組），次分組），即所有數(shù)據(jù)放在一組中排序為止。此時，全部數(shù)據(jù)便按即所有數(shù)據(jù)放在一組中排序為止。此時，全部數(shù)據(jù)便按次序排好了。次序排好了。設待排序共有設待排序共有10個記錄，其關鍵字分別為個記錄，其關鍵字分別為47, 33, 61, 82, 71, 11, 25, 47 , 57, 02，增量序列取值依次為，增量序列取值依次為5, 3, 1。 希爾插入排序希爾插入排序過程過程 排排 序序 希爾排序?qū)嵸|(zhì)上還是一種插入排序，其主要特點是：希爾排序?qū)嵸|(zhì)上還是一種插入排序，其主要特點是：每一趟以不同的增

17、量進行排序。每一趟以不同的增量進行排序。在每趟的插入排序中，記錄在每趟的插入排序中，記錄的關鍵字是和同一組中的前一個關鍵字進行比較，所以關鍵的關鍵字是和同一組中的前一個關鍵字進行比較，所以關鍵字較小的記錄在排序過程中是作跳躍式的移動。字較小的記錄在排序過程中是作跳躍式的移動。 另外，另外，由于開始時增量的取值較大，每組中記錄較少，由于開始時增量的取值較大，每組中記錄較少，故排序比較快，故排序比較快，隨著增量值的逐步變小，每組中的記錄逐漸隨著增量值的逐步變小，每組中的記錄逐漸變多，但由于此時記錄已基本有序了，因次在進行最后一趟變多，但由于此時記錄已基本有序了，因次在進行最后一趟增量為增量為1的插

18、入排序時，只需作少量的比較和移動便可完成的插入排序時，只需作少量的比較和移動便可完成排序，從而提高了排序速度。排序，從而提高了排序速度。 希爾插入排序希爾插入排序特點特點 排排 序序 希爾排序比直接插入排序的平均性能要好：希爾排序比直接插入排序的平均性能要好：l在在最好情況最好情況（原始記錄按關鍵字有序排列）下，（原始記錄按關鍵字有序排列）下，移動次數(shù)為移動次數(shù)為0，比較次數(shù)界于，比較次數(shù)界于n n2 之間。之間。l在在最壞情況最壞情況（原始記錄按關鍵字逆序排列）下，（原始記錄按關鍵字逆序排列）下，移動次數(shù)和比較次數(shù)接近移動次數(shù)和比較次數(shù)接近n2。 l在在平均情況平均情況下下，移動次數(shù)和比較次

19、數(shù)在移動次數(shù)和比較次數(shù)在O（n1.3）左右，好于直接插入排序。左右，好于直接插入排序。希爾插入排序希爾插入排序性能效率性能效率排排 序序例例1.19 希爾排序的程序希爾排序的程序 #include stdio.h #define max 10 int datamax+1; int indexmax+1; int i;排排 序序 void shell_sort(a) int amax+1; int i,j,n,m,skip; int alldone;for (i=1;i1) skip=skip/2; do alldone=1; for (j=1;j=max-skip;j+) i=j+skip;

20、n=indexi; m=indexj; if (anam) indexi=m; indexj=n; alldone=0; while (alldone=0); 排排 序序main() printf(請輸入數(shù)據(jù)請輸入數(shù)據(jù): ); for (i=1;i=max;i+) scanf(%d,&datai); printf(n); for (i=1;i=max;i+) printf(%d ,datai); printf(n); shell_sort(data); for (i=1;ilength;i1;-i) for (j=1;jrj+1rj) Swap(L-rj,L-rj+1); 時間性能分析

21、：時間性能分析：比較次數(shù)比較次數(shù):最壞最壞(n-1)+(n-2)+.+1; 最好：最好： n-1 移動次數(shù)移動次數(shù):最壞：最壞：3(n-1)+(n-2)+.+1)；最好：；最好：0 7.3.1 冒泡排序冒泡排序算法和性能分析算法和性能分析排排 序序523197825531579 89i=7i=6for (j = 1; j rj+1 rj) 13i=27.3.1 冒泡排序冒泡排序改進改進排排 序序void BubbleSort(SqList *L) i=L-length; while (i1) /定位第定位第i個位置的記錄個位置的記錄 lastExchangeIndex=1; for (j=1;

22、jrj+1rj) Swap(L-rj,L-rj+1); lastExchangeIndex=j; i=lastExchangeIndex; 7.3.1 冒泡排序冒泡排序改進算法改進算法排排 序序最好情況（記錄按關鍵字有序排列）：只需進行一趟冒泡最好情況（記錄按關鍵字有序排列）：只需進行一趟冒泡“比較”的次數(shù)：最壞情況（記錄按關鍵字逆序排列）：需進行最壞情況（記錄按關鍵字逆序排列）：需進行n-1趟冒泡趟冒泡“比較”的次數(shù)：0“移動”的次數(shù)：“移動”的次數(shù)：n-12) 1() 1(2nnini2) 1(3) 1(32nnini7.3.1 冒泡排序冒泡排序性能分析性能分析排排 序序 首先對無序的記錄

23、序列進行首先對無序的記錄序列進行“一次劃分一次劃分”，通過一趟排序通過一趟排序?qū)⒋判蛄袑⒋判蛄蟹殖蓛刹糠址殖蓛刹糠郑蛊渲?，使其中一部分記錄一部分記錄的關鍵字均比的關鍵字均比另另一部分小一部分小，再，再分別分別對這兩部分排序，以達到整個序列有序。對這兩部分排序，以達到整個序列有序。無無 序序 的的 記記 錄錄 序序 列列無序記錄子序列無序記錄子序列(1)無序子序列無序子序列(2)樞軸樞軸一次劃分一次劃分分別進行快速排序分別進行快速排序7.3.2 快速排序快速排序基本思想基本思想排排 序序快速排序快速排序 目標目標o找一個記錄，找一個記錄，以它的關鍵字作為以它的關鍵字作為“樞軸樞軸”，凡凡其

24、其關鍵字小于樞軸關鍵字小于樞軸的記錄的記錄移至該記錄之前，移至該記錄之前，反反之，之，移至該記錄之后。移至該記錄之后。o一趟排序一趟排序之后，無序序列之后，無序序列L.r low.high將被將被分割成兩個部分分割成兩個部分：L.rlow.i-1和和L.r i+1.high 且且 L.r j L.r i L.r j (lowji-1) 樞軸樞軸 (i+1jhigh)。排排 序序快速排序快速排序 方法方法o關鍵字通常取第一個記錄的值為基準值。關鍵字通常取第一個記錄的值為基準值。o方法：附設兩個指針方法：附設兩個指針i i和和j j ，初值分別指向，初值分別指向第一第一個記錄個記錄和和最后一個記錄

25、最后一個記錄，設關鍵字為，設關鍵字為 keykey ，首，首先從先從 j j所指位置起所指位置起向前向前搜索，找到第一個搜索，找到第一個小于小于基準值的記錄與基準記錄交換，然后從基準值的記錄與基準記錄交換，然后從i i 所指所指位置起位置起向后向后搜索，找到第一個搜索，找到第一個大于大于基準值的記基準值的記錄與基準記錄交換，重復這兩步直至錄與基準記錄交換，重復這兩步直至i=ji=j為止。為止。初始值初始值 46 55 13 42 94 5 17 70快速排序一趟算法快速排序一趟算法初始值初始值 46 55 13 42 94 5 17 70ij17 55 13 42 94 5 17 7017 5

26、5 13 42 94 5 55 70基準X=4617 5 13 42 94 5 55 70移動jij移動ij移動jiii17 5 13 42 94 94 55 7017 5 13 42 94 94 55 7046i jiiii排排 序序第一趟第一趟 13 5 17 42 46 94 55 70快速排序例快速排序例初始值初始值 46 55 13 42 94 5 17 70第二趟第二趟 5 13 17 42 46 70 55 94第三趟第三趟 5 13 17 42 46 55 70 94第四趟第四趟 5 13 17 42 46 55 70 94快速排序快速排序步驟步驟(1)(1)令指針令指針L L

27、1 1 ，R Rn n ，即分別指向，即分別指向A A1 1和和AnAn；(2)(2)自尾端開始進行比較：將自尾端開始進行比較：將ARAR與與ALAL比較，若比較，若ALALARAR，則數(shù)，則數(shù)據(jù)就不交換，此時固定據(jù)就不交換，此時固定L L（即（即L L指針不動），調(diào)整尾指針，指針不動），調(diào)整尾指針，使使R RR R-1-1。繼續(xù)比較，直至。繼續(xù)比較，直至ALALARAR時為止，將時為止，將ARAR與與ALAL交換位置，并修改左指針，使交換位置，并修改左指針，使L LL L+1+1；(3)(3)將將ALAL與與ARAR比較，若比較，若ALALARAR，則調(diào)整左指針，使，則調(diào)整左指針，使L LL

28、 L+1+1，R R指針不動。繼續(xù)比較，直至指針不動。繼續(xù)比較，直至ALALARAR時為止，將時為止，將ALAL與與ARAR交換位置，并修改右指針交換位置，并修改右指針R R，使，使R RR R-1-1；(4)(4)重復重復(2)(3)(2)(3)步驟，直到從兩邊開始的掃描在中間相遇，步驟，直到從兩邊開始的掃描在中間相遇，即即L L、R R指針重合于中間某一個元素，此時該元素即在排指針重合于中間某一個元素，此時該元素即在排序的序列中找到了自己合適的位置，并且此元素將原序序的序列中找到了自己合適的位置，并且此元素將原序列分成了前后兩個子集。雖然此時這兩個子集還是無序列分成了前后兩個子集。雖然此時

29、這兩個子集還是無序的，但前一個子集的所有元素均小于后一個子集的所有的，但前一個子集的所有元素均小于后一個子集的所有元素。這稱為一趟。元素。這稱為一趟。排排 序序設設 L.rlow=46為樞軸為樞軸，在調(diào)整過程中，設立兩個指針：在調(diào)整過程中，設立兩個指針： low 和和high，之后，之后逐漸減小逐漸減小 high或或增加增加 low，并保證：，并保證：將將 L.rhigh和樞軸的關鍵字進行比較，要求和樞軸的關鍵字進行比較，要求L.rhigh樞樞軸的關鍵字軸的關鍵字將將 L.rlow和樞軸的關鍵字進行比較，要求和樞軸的關鍵字進行比較，要求L.rlow樞軸樞軸的關鍵字的關鍵字 L.rhigh樞軸樞

30、軸且且L.rlow樞軸樞軸, ,否則進行記錄的否則進行記錄的“交換交換”?？焖倥判蛩惴焖倥判蛩惴╲oid quicksort(int r ,int left,int right)int i=left, j=right;int x=ri;while (i=x) & (ji) ) j=j-1; /向前比較向前比較 ri=rj; /比比x小的元素左移小的元素左移 while ( (rii) ) i=i+1; /向后比較向后比較 rj=ri; /比比x大的元素右移大的元素右移ri=x; /基準值基準值x歸位歸位quicksort(r,left,i-1); /遞歸調(diào)用左子區(qū)間遞歸調(diào)用左子區(qū)間q

31、uicksort(r,i+1,right); /遞歸調(diào)用右子區(qū)間遞歸調(diào)用右子區(qū)間leftrighti排排 序序快速排序的時間主要耗費在劃分操作上，對長度為快速排序的時間主要耗費在劃分操作上，對長度為k k的區(qū)的區(qū)間進行劃分，共需間進行劃分，共需k-1k-1次關鍵字的比較。次關鍵字的比較。最壞情況最壞情況是每次劃分選取的基準都是當前無序區(qū)中是每次劃分選取的基準都是當前無序區(qū)中關鍵字關鍵字最小最小( (或最大或最大) )的記錄的記錄，劃分的結果是基準左邊的子區(qū)間為，劃分的結果是基準左邊的子區(qū)間為空空( (或右邊的子區(qū)間為空或右邊的子區(qū)間為空) )，而劃分所得的另一個非空的子，而劃分所得的另一個非空

32、的子區(qū)間中記錄數(shù)目，僅僅比劃分前的無序區(qū)中記錄個數(shù)減少區(qū)間中記錄數(shù)目，僅僅比劃分前的無序區(qū)中記錄個數(shù)減少一個。因此，快速排序必須做一個。因此，快速排序必須做n-1n-1次劃分，第次劃分，第i i次劃分開始次劃分開始時區(qū)間長度為時區(qū)間長度為n-i+1n-i+1，所需的比較次數(shù)為，所需的比較次數(shù)為n-in-i(1in-1)(1in-1)，故總的比較次數(shù)達到最大值：故總的比較次數(shù)達到最大值： n(n-1)/2=O(nn(n-1)/2=O(n2 2) )快速排序快速排序時間分析時間分析排排 序序在在最好情況最好情況下，每次劃分所取的基準都是當前無序區(qū)的下，每次劃分所取的基準都是當前無序區(qū)的“中值中值”

33、記錄記錄，劃分的結果是基準的左、右兩個無序子區(qū)，劃分的結果是基準的左、右兩個無序子區(qū)間的長度大致相等?？偟年P鍵字比較次數(shù)：間的長度大致相等。總的關鍵字比較次數(shù)： O(nlogn)因為快速排序的因為快速排序的記錄移動次數(shù)不大于比較的次數(shù)記錄移動次數(shù)不大于比較的次數(shù)，所以快，所以快速排序：速排序： 最壞最壞時間復雜度應為時間復雜度應為O (n2) 最好最好時間復雜度為時間復雜度為O(nlogn) 平均平均時間復雜度為時間復雜度為O(nlogn)快速排序快速排序時間分析時間分析排排 序序 快速排序在系統(tǒng)內(nèi)部需要一個棧來實現(xiàn)遞歸。若每次劃分快速排序在系統(tǒng)內(nèi)部需要一個棧來實現(xiàn)遞歸。若每次劃分較為均勻，則

34、其遞歸樹的高度為較為均勻，則其遞歸樹的高度為O(logn)，故遞歸后需棧空，故遞歸后需?？臻g為間為O(logn)。最壞情況下，遞歸樹的高度為。最壞情況下，遞歸樹的高度為O(n)，所需的，所需的?？臻g為?？臻g為O(n)。因為快速排序的因為快速排序的劃分次數(shù)在劃分次數(shù)在lognn之間之間，所以快速排序的：，所以快速排序的： 最壞最壞空間復雜度應為空間復雜度應為O (n) 最好最好空間復雜度為空間復雜度為O(logn) 平均平均空間復雜度為空間復雜度為O(logn)快速排序快速排序空間分析空間分析排排 序序若待排記錄的初始狀態(tài)為按關鍵字有序時，快速排序若待排記錄的初始狀態(tài)為按關鍵字有序時，快速排序?qū)?/p>

35、退化為冒泡排序?qū)⑼嘶癁槊芭菖判?，其時間復雜度為，其時間復雜度為O(n2)。因此，快速排序適用于原始數(shù)據(jù)雜亂無章的傾向。因此，快速排序適用于原始數(shù)據(jù)雜亂無章的傾向。輔助空間數(shù)量為遞歸調(diào)用所開辟的?？臻g。輔助空間數(shù)量為遞歸調(diào)用所開辟的?？臻g。7.3.2 快速排序快速排序適用范圍適用范圍結論結論: 快速排序的時間復雜度為快速排序的時間復雜度為O(nlogn)且適用于且適用于原始數(shù)據(jù)雜亂無章的情況?？焖倥判蚴欠欠€(wěn)定的。原始數(shù)據(jù)雜亂無章的情況?？焖倥判蚴欠欠€(wěn)定的。 快速排序的程序：快速排序的程序： #include stdio.h #define n 10 int arn+1; int i,l1; in

36、t quick1(a,l,r) int an+1; int l,r; /* 指針指針 */ int l1; int r1,w; l1=l; r1=r; w=al1; do while (ar1=w) & (l1r1) r1=r1-1; if (l1r1) al1=ar1; l1=l1+1; while (al1=w) & (l1r1) l1=l1+1; if (l1r1) ar1=al1; r1=r1-1; while(l1!=r1); al1=w; return(l1); 排排 序序void q_sort(a,l,r) int an+1; int l,r;int l1; if

37、 (lr) l1=quick1(a,l,r); q_sort(a,l,l1-1); q_sort(a,l1+1,r); main() printf(請輸入數(shù)據(jù)請輸入數(shù)據(jù): n); for (i=1;i=n;i+) scanf(%d,&ari); q_sort(ar,1,n); printf(排序后的序列排序后的序列:n); for (i=1;i=n;i+) printf(%d ,ari); if (i % 5=0) printf(n); 運行結果：運行結果：請輸入數(shù)據(jù)請輸入數(shù)據(jù): 42 23 74 11 65 58 94 36 99 87排序后的序列排序后的序列:11 23 36 42

38、 58 65 74 87 94 99 排排 序序完成一趟排序：初始關鍵詞：排排 序序完成二趟排序：排排 序序完成三趟排序：完成四趟排序：排排 序序23, 10, 20, 36, 40, 13, 27, 1111, 10, 20, 13, 23, 40, 27, 3610, 11, 20, 13, 23, 40, 27, 3610, 11, 13, 20, 23, 40, 27, 3610, 11, 13, 20, 23, 36, 27, 4010, 11, 13, 20, 23, 27, 36, 4010, 11, 20, 13, 23, 40, 27, 3610, 11, 13, 20, 2

39、3, 40, 27, 367.3.2 快速排序快速排序過程過程排排 序序7.4 選擇選擇 排排 序序簡單選擇排序簡單選擇排序堆堆 排排 序序排排 序序假設排序過程中，待排記錄序列的狀態(tài)為：假設排序過程中，待排記錄序列的狀態(tài)為：有序序列有序序列L.r 1.i-1無序序列無序序列 L.r i.n 第第 i 趟趟簡單選擇排序簡單選擇排序從中選出從中選出關鍵字最小的記錄關鍵字最小的記錄有序序列有序序列L.r1.i無序序列無序序列 L.ri+1.n7.4.1 簡單選擇排序簡單選擇排序基本思想和過程基本思想和過程排排 序序四、選擇排序四、選擇排序o直接選擇排序直接選擇排序n又稱為簡單選擇排序，是一種簡單直

40、觀的排序方法。n從待排序的所有記錄中，選取關鍵字最小的記錄，并將它與原始序列中的第一個記錄交換，然后從去掉了關鍵字最小記錄的剩余記錄中選擇關鍵字最小的記錄將它與原始記錄序列的第二個記錄交換位置，以此類推，直到序列中全部記錄排序完畢。排排 序序排排 序序o算法：算法：/對記錄序列對記錄序列x0 xn-1進行直接選擇排序進行直接選擇排序void selectsort(elemtype x,int n) int i,j,small;elemtype swap;for(i=0;in-1;i+) small=i; for(j=i+1;jn;j+) if(xj.keyxsmall.key) small=j

41、; if(small!=i) swap=xi; Xi=xsmall; Xsmall=swap; 排排 序序?qū)?n 個記錄進行簡單選擇排序，所需進行的個記錄進行簡單選擇排序，所需進行的 關鍵字間的比較次數(shù)關鍵字間的比較次數(shù) 總計為：總計為：移動記錄的次數(shù)移動記錄的次數(shù)，最小值為最小值為 0, 最大值為最大值為3(n-1) 。2) 1()(11nninni7.4.1 簡單選擇排序簡單選擇排序算法時間性能分析算法時間性能分析排排 序序o堆就是一個關鍵字序列堆就是一個關鍵字序列：并且這并且這n個關鍵字的序個關鍵字的序列列K1,K2.Kn要滿足以下性質(zhì)要滿足以下性質(zhì)(堆性質(zhì)堆性質(zhì))，就是，就是: Ki

42、K2i且且KiK2i+1 或者或者 KiK2i且且KiK2i+1 2、堆排序、堆排序堆的定義堆的定義(正堆正堆)(逆堆逆堆)12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49 是正堆是正堆12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49 不是堆不是堆1 2 3 4 5 6 7 8 9 10 11排排 序序o當把這個序列存入一個向量并把它看作是一棵完全二當把這個序列存入一個向量并把它看作是一棵完全二叉樹的存儲結構時，堆就是這樣一棵二叉樹：叉樹的存儲結構時，堆就是這樣一棵二叉樹：任一非任一非葉結點的關鍵字均不小于葉結點的關鍵字均

43、不小于( (或不大于或不大于) )其左右孩子結點其左右孩子結點的關鍵字。的關鍵字。2、堆排序、堆排序1236276549817355403498是堆是堆14不不排排 序序1 2 3 4 5 6 7 89470174642550513堆堆最大值排排 序序897624331510112536497856a) 堆頂元素取最大值堆頂元素取最大值大根堆大根堆b) 堆頂元素取最小值堆頂元素取最小值小根堆小根堆排排 序序堆排序基本思想堆排序基本思想o因為堆頂是最大的數(shù)，所以當把一個關鍵字序列排成一個大根堆時，就很容易地找到最大的數(shù)，它就在序列的第一個位置上o然后把這個最大的數(shù)與最后一個記錄交換，這時，最后一

44、個記錄就是關鍵字最大的記錄了。o對于剩下的關鍵字序列，我們?nèi)匀话阉懦梢粋€大根堆，然后再把第一個記錄(當前堆中的堆頂)與當前堆的最后一個記錄交換。這時，在整個序列后面就有了兩個有序的關鍵字(從小到大)。o重復這樣的過程，就可以把有序區(qū)不斷擴大直到全部關鍵字都進入有序區(qū)。直到排序完成。947017464255 0513初始堆初始堆427017469455 0513135517469442 0570排排 序序堆的構造堆的構造o無序序列無序序列r1：n構成的完全二叉樹。構成的完全二叉樹。o從它最后一個非葉子結點（第從它最后一個非葉子結點（第n/2個元素）開始直到根個元素）開始直到根結點為止，逐步進行

45、結點為止，逐步進行調(diào)整調(diào)整即可將此完全二叉樹構成堆。即可將此完全二叉樹構成堆。o調(diào)整：調(diào)整：與其左右子樹根結點值比較，取其中大的進行交與其左右子樹根結點值比較，取其中大的進行交換。換。排排 序序堆的構造例堆的構造例465513427094 051746 55 13 42 94 05 17 707017594421355461 2 3 4 5 6 7 81 2 3 4 5 6 7 8排排 序序465513704294 0517465513427094 05177017594421355461 2 3 4 5 6 7 8對調(diào)對調(diào)4217594701355461 2 3 4 5 6 7 8對調(diào)對調(diào)1

46、313堆的構造例堆的構造例46 55 13 42 94 05 17 70排排 序序465517704294 05134213594701755461 2 3 4 5 6 7 8對調(diào)5555對調(diào)469417704255 05134213555701794461 2 3 4 5 6 7 8對調(diào)4646對調(diào)堆的構造例堆的構造例46 55 13 42 94 05 17 70排排 序序944617704255 05134213555701746941 2 3 4 5 6 7 8對調(diào)4646對調(diào)947017464255 05134213555461770941 2 3 4 5 6 7 8成堆成堆!堆的構造

47、例堆的構造例46 55 13 42 94 05 17 70排排 序序465513427094 0517初始無序結點,從42開始調(diào)整465513704294 0517將以13為根的子樹調(diào)整成堆465517704294 0513將以55為根的子樹調(diào)整成堆堆的構造例堆的構造例46 55 13 42 94 05 17 70排排 序序469417704255 0513將以46為根的子樹調(diào)整成堆947017464255 0513成堆排排 序序調(diào)整成堆算法調(diào)整成堆算法void SIFT(int r,int i,int n) /調(diào)整調(diào)整r1:n中結點中結點ri,使成為一個堆使成為一個堆int j;int T;

48、T=ri; j=2*i; /j為為i結點的左孩子序號結點的左孩子序號while(jn) if ( (jn) & ( rj rj+1 ) ) j+; /找出找出i的大孩子的大孩子 if (T=0;i-) /將將r調(diào)整成堆調(diào)整成堆SIFT(r,i,n);for(i=n-1;i=0;i-) t=r0;r0=ri;ri=t; SIFT(r,0,i-1); i0堆排序的程序：堆排序的程序： #include stdio.h #define mm 8 int amm+1; int k; void shift(a,l,m) void heapsort(a) int amm+1; int i,x; f

49、or (i=mm/2;i=1;i-) shift(a,i,mm); /* 從第開始進行篩選建堆 */ for (i=mm;i=2;i-) x=a1; a1=ai; ai=x; /* 將堆頂元素和堆中最后一個元素交換 */ shift(a,1,i-1); /* 調(diào)整第一個元素使之重又成為堆 */ main() printf(請輸入數(shù)據(jù)請輸入數(shù)據(jù): n); for (k=1;k=mm;k+) scanf(%d,&ak); printf(初始數(shù)據(jù)初始數(shù)據(jù):n); for (k=1;k=mm;k+) printf( a%d=%d ,k,ak); printf(n); heapsort(a);

50、printf(排序后的數(shù)據(jù)排序后的數(shù)據(jù):n ); for (k=1;k=mm;k+) printf( |a%d=%d| ,k,ak); printf(n);排排 序序五、五、 基數(shù)排序基數(shù)排序l 前面介紹的幾種排序方法都是按數(shù)據(jù)元素（或記錄關鍵字）前面介紹的幾種排序方法都是按數(shù)據(jù)元素（或記錄關鍵字）值的大小進行排序的值的大小進行排序的l 而而多關鍵字排序多關鍵字排序是一種是一種按組成數(shù)據(jù)元素或關鍵字的各位值按組成數(shù)據(jù)元素或關鍵字的各位值進行排序進行排序的方法，基數(shù)排序借助的就是這種思想，它的方法，基數(shù)排序借助的就是這種思想，它屬于屬于分分布式排序布式排序，也稱，也稱口袋排序口袋排序。l 基數(shù)排

51、序是把邏輯基數(shù)排序是把邏輯關鍵字關鍵字看成由看成由若干個子關鍵字復合若干個子關鍵字復合而成而成的的 假設有假設有n個關鍵字個關鍵字r1，r2，rn需進行排序需進行排序 每個關鍵字由每個關鍵字由d元組（元組（k1k2k3kd）子關鍵字組成，）子關鍵字組成，k1是是關鍵字值的最高位，關鍵字值的最高位，kd是關鍵字值的最低位，其基數(shù)為是關鍵字值的最低位，其基數(shù)為rd排排 序序五、五、 基數(shù)排序基數(shù)排序l 前面介紹的幾種排序方法都是按數(shù)據(jù)元素（或記錄關鍵字）前面介紹的幾種排序方法都是按數(shù)據(jù)元素（或記錄關鍵字）值的大小進行排序的值的大小進行排序的l 多關鍵字排序多關鍵字排序是一種是一種按組成數(shù)據(jù)元素或關

52、鍵字的各位值進按組成數(shù)據(jù)元素或關鍵字的各位值進行排序行排序的方法，基數(shù)排序借助的就是這種思想的方法，基數(shù)排序借助的就是這種思想。l基數(shù)排序基數(shù)排序?qū)儆趯儆诜植际脚判蚍植际脚判?，也稱口袋排序，也稱口袋排序、“桶子法桶子法” 。l基數(shù)排序法是屬于基數(shù)排序法是屬于穩(wěn)定性穩(wěn)定性的排序的排序l時間復雜度為時間復雜度為O (nlog(r)m)，其中，其中r為所采取的基數(shù)，而為所采取的基數(shù)，而m為堆數(shù)，在某些時候，基數(shù)排序法的效率高于其它的比較性為堆數(shù)，在某些時候，基數(shù)排序法的效率高于其它的比較性排序法。排序法。 排排 序序o基數(shù)排序的方式可以采用：基數(shù)排序的方式可以采用：nLSD（Least signif

53、icant digital）的排序方式由鍵的排序方式由鍵值的值的最右邊最右邊開始開始nMSD（Most significant digital）由鍵值的由鍵值的最左邊最左邊開始。開始。 o以以LSD為例，假設原來有一串數(shù)值如下所示：為例，假設原來有一串數(shù)值如下所示： 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 排排 序序73, 22, 93, 43, 55, 14, 28, 65, 39, 81o首先根據(jù)首先根據(jù)個位數(shù)個位數(shù)的數(shù)值，的數(shù)值，在走訪數(shù)值時將它們分在走訪數(shù)值時將它們分配至編號配至編號0到到9的桶子的桶子中；中；o接下來將這些桶子中的接下來將這些桶子

54、中的數(shù)值重新串接起來，成數(shù)值重新串接起來，成為以下的數(shù)列：為以下的數(shù)列： 81, 22, 73, 93, 43, 14, 55, 65, 28, 39 排排 序序81, 22, 73, 93, 43, 14, 55, 65, 28, 39o接著再進行一次分配，這次接著再進行一次分配，這次是根據(jù)十位數(shù)來分配：是根據(jù)十位數(shù)來分配：o接下來將這些桶子中的數(shù)值接下來將這些桶子中的數(shù)值重新串接起來，成為以下的重新串接起來，成為以下的數(shù)列：數(shù)列： o整個數(shù)列已經(jīng)排序完畢整個數(shù)列已經(jīng)排序完畢。14, 22, 28, 39, 43, 55, 65, 73, 81, 93 排排 序序o如果排序的對象有三位數(shù)以上

55、，則持續(xù)進行以上的動作如果排序的對象有三位數(shù)以上，則持續(xù)進行以上的動作直至最高位數(shù)為止。直至最高位數(shù)為止。 oLSD的基數(shù)排序適用于位數(shù)小的數(shù)列，如果位數(shù)多的話，的基數(shù)排序適用于位數(shù)小的數(shù)列，如果位數(shù)多的話，使用使用MSD的效率會比較好；的效率會比較好；oMSD的方式恰與的方式恰與LSD相反，是由高位數(shù)為基底開始進相反，是由高位數(shù)為基底開始進行分配，其他的演算方式則都相同。行分配，其他的演算方式則都相同。 排排 序序基數(shù)排序基數(shù)排序排序前先將待排序元素置于一數(shù)組排序前先將待排序元素置于一數(shù)組 r1rn中存儲，每中存儲，每個結點除存放排序碼的值外，還有一個指向下一個結點的指個結點除存放排序碼的值

56、外，還有一個指向下一個結點的指針（即下一個結點的下標值）針（即下一個結點的下標值）排序時從最低位排序時從最低位kd開始，直到最高位開始，直到最高位k1，把關鍵字依其子，把關鍵字依其子關鍵字的值分配到關鍵字的值分配到rd個隊列中去，同一隊列中的元素用指針個隊列中去，同一隊列中的元素用指針鏈接，同時隊頭和隊尾各用一個指針指示，該頭、尾指針分鏈接，同時隊頭和隊尾各用一個指針指示，該頭、尾指針分別存放在兩個數(shù)組別存放在兩個數(shù)組 fra1fra2和和era1era2中（中（ra1和和ra2為為子關鍵字子關鍵字ki的取值范圍）的取值范圍）每經(jīng)過一次分配后，都將各隊列中的元素按次序收集在一每經(jīng)過一次分配后，

57、都將各隊列中的元素按次序收集在一起，經(jīng)過起，經(jīng)過d次的分配和收集后即得到了按序排列的序列次的分配和收集后即得到了按序排列的序列排排 序序基數(shù)排序基數(shù)排序例如，若關鍵字是十進制數(shù)值，將全部數(shù)據(jù)放在數(shù)組例如，若關鍵字是十進制數(shù)值，將全部數(shù)據(jù)放在數(shù)組r中，中，然后按下列步驟進行：然后按下列步驟進行：（1）初態(tài)初態(tài)：設置：設置10個隊列，并且使其均為空。個隊列，并且使其均為空。（2）分配分配：依次從數(shù)組：依次從數(shù)組r中取出每個關鍵字，第中取出每個關鍵字，第i遍處理時，遍處理時，考察該關鍵字右起第考察該關鍵字右起第i位數(shù)字（即第位數(shù)字（即第i個子關鍵字），設其值個子關鍵字），設其值位位k，則把該關鍵字插

58、入第，則把該關鍵字插入第k個隊列。數(shù)組個隊列。數(shù)組r全部處理完后，全部處理完后，全部數(shù)據(jù)被分配到隊列全部數(shù)據(jù)被分配到隊列0隊列隊列9。（3）收集收集：從隊列：從隊列0開始，依隊列開始，依隊列0隊列隊列9的頭、尾指針，的頭、尾指針，修改數(shù)組修改數(shù)組r中各關鍵字的指針，即將這次分配完的關鍵字依中各關鍵字的指針，即將這次分配完的關鍵字依邏輯次序再鏈接起來。邏輯次序再鏈接起來。（4）循環(huán)循環(huán)：重復以上（：重復以上（1）（）（3）步，若關鍵字有）步，若關鍵字有d位數(shù)字，位數(shù)字，就需要執(zhí)行就需要執(zhí)行d遍。遍。排排 序序基數(shù)排序基數(shù)排序考察由考察由3位十進制數(shù)字組成的關鍵字，則其值在位十進制數(shù)字組成的關鍵字

59、，則其值在0k999范范圍內(nèi)。圍內(nèi)。 可把每一個十進制數(shù)看成一個邏輯關鍵字可把每一個十進制數(shù)看成一個邏輯關鍵字k， k由三個子關鍵字（由三個子關鍵字（k1、k2、k3）組成，其中）組成，其中k1是百位數(shù)，是百位數(shù)，k2是十位數(shù)，是十位數(shù)，k3是個位數(shù)，由此分解得到的每個關鍵字是個位數(shù)，由此分解得到的每個關鍵字ki都都在相同的范圍內(nèi)（在相同的范圍內(nèi)（0ki9）。）。 排序是先從最低位排序是先從最低位k3開始，按開始，按k3的大小分成若干組，每的大小分成若干組，每組中組中k3值相同，然后將各組數(shù)據(jù)收集在一起；值相同，然后將各組數(shù)據(jù)收集在一起； 下次再按下次再按k2大小排序，大小排序， 如此重復，直

60、到對如此重復，直到對k1排序后，整個數(shù)據(jù)集即成為有序序排序后，整個數(shù)據(jù)集即成為有序序列。列。排排 序序基數(shù)排序基數(shù)排序例例1.22 基數(shù)排序過程的程序基數(shù)排序過程的程序l 設有設有10個十進制數(shù)：個十進制數(shù)：179、208、234、056、800、178、651、245、006、958，l 該數(shù)列數(shù)值范圍在該數(shù)列數(shù)值范圍在0999之間，因此子關鍵字位數(shù)之間，因此子關鍵字位數(shù)d3，個位數(shù)為低關鍵字位，百位數(shù)為高關鍵字位，關鍵字值得范個位數(shù)為低關鍵字位，百位數(shù)為高關鍵字位，關鍵字值得范圍為圍為09，基數(shù)為，基數(shù)為10。l 進行基數(shù)排序過程如圖進行基數(shù)排序過程如圖1.61所示。所示。 r1 r2 r3 r4 r5 r6 r7 r8 r9 r1017920823405680017