數據結構 第10章_內排序

1、交換排序交換排序冒泡排序冒泡排序p 快速排序快速排序p 直接選擇排序直接選擇排序p 堆排序堆排序第十章第十章 內排序內排序插入排序插入排序p 直接插入排序直接插入排序p 二分插入排序二分插入排序p 希爾排序希爾排序 選擇排序選擇排序 歸并排序歸并排序 基數排序基數排序 排序是數據處理過程中經常使用的一種重要的運排序是數據處理過程中經常使用的一種重要的運算，排序的方法有很多種，本章主要討論內排序的各算，排序的方法有很多種，本章主要討論內排序的各種算法，并對每個排序算法的時間和空間復雜性以及種算法，并對每個排序算法的時間和空間復雜性以及算法的穩(wěn)定性等進行了討論。算法的穩(wěn)定性等進行了討論。 10.1

2、 排序的基本概念排序的基本概念 假設一個文件是由假設一個文件是由n個記錄個記錄R1，R2，Rn組成，組成，所謂排序就是以記錄中某個所謂排序就是以記錄中某個(或幾個或幾個)字段值不減字段值不減(或或不增不增)的次序將這的次序將這n個記錄重新排列，稱該字段為排個記錄重新排列，稱該字段為排序碼。能唯一標識一個記錄的字段稱為關鍵碼，關序碼。能唯一標識一個記錄的字段稱為關鍵碼，關鍵碼可以作為排序碼，但排序碼不一定要是關鍵碼。鍵碼可以作為排序碼，但排序碼不一定要是關鍵碼。 按排序過程中使用到的存儲介質來分，可以將排按排序過程中使用到的存儲介質來分，可以將排序分成兩大類序分成兩大類:內排序和外排序內排序和外

3、排序內排序內排序是指在排序過程中所有數據均放在內存中是指在排序過程中所有數據均放在內存中處理，不需要使用外存的排序方法。而對于數據量很處理，不需要使用外存的排序方法。而對于數據量很大的文件，在內存不足的情況下，則還需要使用外存，大的文件，在內存不足的情況下，則還需要使用外存，這種排序方法稱為這種排序方法稱為外排序外排序排序碼相同的記錄，若經過排序后，這些記錄排序碼相同的記錄，若經過排序后，這些記錄仍保持原來的相對次序不變，稱這個排序算法是仍保持原來的相對次序不變，稱這個排序算法是穩(wěn)穩(wěn)定的定的。否則，稱為。否則，稱為不穩(wěn)定的排序算法不穩(wěn)定的排序算法評價排序算法優(yōu)劣的標準評價排序算法優(yōu)劣的標準 ：

4、 首先考慮算法執(zhí)行所需的時間，這主要是用執(zhí)行首先考慮算法執(zhí)行所需的時間，這主要是用執(zhí)行過程中的比較次數和移動次數來度量；過程中的比較次數和移動次數來度量； 其次考慮算法執(zhí)行所需要的附加空間。其次考慮算法執(zhí)行所需要的附加空間。 當然，保證算法的正確性是不言而喻的，可讀性當然，保證算法的正確性是不言而喻的，可讀性等也是要考慮的因素。等也是要考慮的因素。 /*/*常見排序算法的頭文件，文件名常見排序算法的頭文件，文件名table.h */*/#define MAXSIZE 100 /*文件中記錄個數的最大值文件中記錄個數的最大值*/ typedef int keytype;/*定義排序碼類型為整數類

5、型定義排序碼類型為整數類型*/ typedef struct keytype key; int other;/*此處還可以定義記錄中除排序碼外此處還可以定義記錄中除排序碼外的其他域的其他域*/ recordtype;/*記錄類型的定義記錄類型的定義*/ typedef struct recordtype rMAXSIZE+1; int length;/*待排序文件中記錄的個數待排序文件中記錄的個數*/ table;/*待排序文件類型待排序文件類型*/void init(table *L) /*順序表初始化函數順序表初始化函數*/ int i; srand(time(NULL); L-lengt

6、h=10;for (i=1;iri.key= rand(i)%100;void print(table L) /*順序表輸出函數順序表輸出函數*/ int i,k=0; for (i=1;ilength); for (i=1;ilength;i+) fscanf(fp,%d,&L-ri.key); else L-length=0;1050 30 20 90 10 70 80 40 60 100一個輸入文件的例子一個輸入文件的例子10.2 插入排序插入排序 插入排序的基本方法是插入排序的基本方法是: 將待排序文件中的記錄，將待排序文件中的記錄， 逐個地按其排序碼值的逐個地按其排序碼值的大

7、小插入到目前已經排好序的若干個記錄組成的文件中大小插入到目前已經排好序的若干個記錄組成的文件中的適當位置，并保持新文件有序。的適當位置，并保持新文件有序。10.2.1 直接插入排序直接插入排序 直接插入排序算法的思路是直接插入排序算法的思路是:初始可認為文件中的初始可認為文件中的第第1個記錄己排好序，然后將第個記錄己排好序，然后將第2個到第個到第n個記錄依次個記錄依次插入已排序的記錄組成的文件中。在對第插入已排序的記錄組成的文件中。在對第i個記錄個記錄Ri進進行插入時，行插入時，R1，R2，Ri-1已排序，將記錄已排序，將記錄Ri的排序的排序碼碼keyi與已經排好序的排序碼從右向左依次比較，找

8、與已經排好序的排序碼從右向左依次比較，找到到Ri應插入的位置，將該位置以后直到應插入的位置，將該位置以后直到Ri-1各記錄順序各記錄順序后移，空出該位置讓后移，空出該位置讓Ri插入。插入。 直接插入排序演示直接插入排序演示0 1 2 3 4 5 6 212525*1608i =321254925*16080 1 2 3 4 5 6初態(tài)初態(tài)490 1 2 3 4 5 62525*1608i = 249250 1 2 3 4 5 6i = 6i = 521250 1 2 3 4 5 6214925*16080 1 2 3 4 5 64925*21254925*16i = 425*160825214

9、925*1608完成25習題：給出初始數列習題：給出初始數列47，28，32，15，94，33，14，16在直接插入排序下的狀態(tài)變化過程。在直接插入排序下的狀態(tài)變化過程。472832 15 9433 1416初態(tài)：初態(tài)：i=2i=3i=4i=5i=6i=7284732 15 9433 1416283247 15 9433 1416152832 47 9433 1416152832 47 9433 1416152832 33 4794 1416141528 32 3347 9716141516 28 3233 4797i=8void insertsort(table *L) /*直接插入排序直接

10、插入排序*/int i,j; for (i=2;ilength;i+) j=i-1; L-r0=L-ri; /*放置哨兵放置哨兵*/ while ( L-rj.keyL-r0.key ) L-rj+1=L-rj; j-; L-rj+1=L-r0; 算法算法10.1 直接插入排序算法直接插入排序算法 直接插入排序算法執(zhí)行時間的分析：直接插入排序算法執(zhí)行時間的分析：最好的情況最好的情況 ： 即初始排序碼開始就是有序的情況下，直接插入即初始排序碼開始就是有序的情況下，直接插入排序算法的比較次數為排序算法的比較次數為(n-1)次，移動次數為次，移動次數為2*(n-1)次。次。 最壞情況最壞情況 ： 即

11、初始排序碼開始是逆序的情況下，因為當插即初始排序碼開始是逆序的情況下，因為當插入第入第i個排序碼時，該算法內循環(huán)個排序碼時，該算法內循環(huán)while要執(zhí)行要執(zhí)行i次條件次條件判斷，循環(huán)體要執(zhí)行判斷，循環(huán)體要執(zhí)行i-l次，每次要移動次，每次要移動1個記錄，外個記錄，外循環(huán)共執(zhí)行循環(huán)共執(zhí)行n-1次，其循環(huán)體內不含內循環(huán)每次循環(huán)次，其循環(huán)體內不含內循環(huán)每次循環(huán)要進行要進行2次移動操作，所以在最壞情況下，比較次數次移動操作，所以在最壞情況下，比較次數為為(1+2+n)。 直接插入排序算法的時間復雜度為直接插入排序算法的時間復雜度為O(n2)。 10.2.2 二分法插入排序二分法插入排序 二分法插入排序的

12、思想：二分法插入排序的思想： 根據插入排序的基本思想，在找第根據插入排序的基本思想，在找第i個記錄的插個記錄的插入位置時，前入位置時，前i-l個記錄已排序，將第個記錄已排序，將第i個記錄的排序碼個記錄的排序碼keyi和已排序的前和已排序的前i-1個的中間位置記錄的排序碼進個的中間位置記錄的排序碼進行比較，如果行比較，如果keyi小于中間位置記錄排序碼，則可以小于中間位置記錄排序碼，則可以在前半部繼續(xù)使用二分法查找，否則在后半部繼續(xù)使在前半部繼續(xù)使用二分法查找，否則在后半部繼續(xù)使用二分法查找，直到查找范圍為空，即可確定用二分法查找，直到查找范圍為空，即可確定keyi的的插入位置。插入位置。 vo

13、id binarysort(table *L) /*折半插入排序折半插入排序*/ int left,right,mid,i,j; for(i=2;ilength;i+) L-r0=L-ri; /*保存待插入的元素保存待插入的元素*/ left=1; right=i-1; /*設置查找范圍的左、右設置查找范圍的左、右位置值位置值*/ while (leftri.keyrmid.key) right=mid-1; else left=mid+1; /*插入位置為插入位置為left*/ for(j=i-1;j=left;j-) /*后移留空后移留空*/ L-rj+1=L-rj; L-r left =

14、L-r0; /*插入第插入第i個元素的副本個元素的副本*/ 算法算法10.2 二分法插入排序算法二分法插入排序算法 二分法插入排序算法，在查找第二分法插入排序算法，在查找第i個記錄的插入個記錄的插入位置時，每執(zhí)行一次位置時，每執(zhí)行一次while循環(huán)體，查找范圍縮小一循環(huán)體，查找范圍縮小一半，和直接插入排序的比較次數對比，二分法插入的半，和直接插入排序的比較次數對比，二分法插入的比較次數少于直接插入排序的最多比較次數，而一般比較次數少于直接插入排序的最多比較次數，而一般要多于直接插入排序的最少比較次數?？傮w上講，當要多于直接插入排序的最少比較次數。總體上講，當n較大時，二分法插入排序的比較次數遠

15、少于直接插較大時，二分法插入排序的比較次數遠少于直接插入排序的平均比較次數，但二者所要進行的移動次數入排序的平均比較次數，但二者所要進行的移動次數相等，故二分法插入排序的時間復雜度也是相等，故二分法插入排序的時間復雜度也是O(n2)，所需的附加存儲空間為一個記錄空間。所需的附加存儲空間為一個記錄空間。 10.2.3 表插入排序表插入排序 二分法插入排序比較次數通常比直接插入排序二分法插入排序比較次數通常比直接插入排序的比較次數少，但移動次數相等。表插入排序將在不的比較次數少，但移動次數相等。表插入排序將在不進行記錄移動的情況下，利用存儲結構有關信息的改進行記錄移動的情況下，利用存儲結構有關信息

16、的改變來達到排序的目的。變來達到排序的目的。 給每個記錄附設一個所謂的指針域給每個記錄附設一個所謂的指針域link，它的類，它的類型為整型，表插入排序的思路：在插入第型為整型，表插入排序的思路：在插入第i個記錄個記錄Ri時，時，R1，R2，Ri-1已經通過各自的指針域已經通過各自的指針域link按排序碼按排序碼不減的次序連接成一個（靜態(tài)鏈）表，將記錄不減的次序連接成一個（靜態(tài)鏈）表，將記錄Ri的排的排序碼序碼keyi與表中已經排好序的排序碼從表頭向右、或與表中已經排好序的排序碼從表頭向右、或稱向后依次比較，找到稱向后依次比較，找到Ri應插入的位置，將其插入在應插入的位置，將其插入在表中，使表中

17、各記錄的排序碼仍然有序。表中，使表中各記錄的排序碼仍然有序。 /* 表插入排序定義的頭文件，文件名為：表插入排序定義的頭文件，文件名為：table2.h */#define MAXSIZE 100 /*文件中記錄個數的最大值文件中記錄個數的最大值*/typedef int keytype; /*定義排序碼類型為整數類型定義排序碼類型為整數類型*/typedef struct keytype key; int link;recordtype; /*記錄類型的定義記錄類型的定義*/typedef struct recordtype rMAXSIZE+1; int length; /*待排序文件中記

18、錄的個數待排序文件中記錄的個數*/table2; /*待排序文件類型待排序文件類型*/ 表插入排序算法的示意如圖表插入排序算法的示意如圖10.4所示所示keylink 31212627222628165123 下標下標 0 1 2 3 4 5 6 7（a）初始存儲狀態(tài)）初始存儲狀態(tài)下標下標 0 1 2 3 4 5 6 7（b）由第）由第1個記錄構成的有序表個記錄構成的有序表下標下標 0 1 2 3 4 5 6 7（c）插入第）插入第2個記錄構成的有序表個記錄構成的有序表keylink 31212627222628165123 1 0 keylink 31212627222628165123 2

19、 0 1 表插入排序算法：初始時，表插入排序算法：初始時，r0.Link用于存放表用于存放表中第中第1個記錄的下標，個記錄的下標，r0.Link的值為的值為1，排序結束時，排序結束時，r0.Link中存放的是所有排序碼中值最小的對應記錄中存放的是所有排序碼中值最小的對應記錄的下標，其它的排序碼通過各自的指針域的下標，其它的排序碼通過各自的指針域link按不減的按不減的次序連接成一個（靜態(tài)鏈）表，最大的排序碼對應的次序連接成一個（靜態(tài)鏈）表，最大的排序碼對應的link為為0。keylink 31212627222628165123 5 0 6 1 3 7 4 2 下標下標 0 1 2 3 4 5

20、 6 7（d）所有記錄都插入后的結束狀態(tài)（下標為）所有記錄都插入后的結束狀態(tài)（下標為5的記錄的的記錄的key值最?。┲底钚。﹫D圖10.4 表插入排序算法示意圖表插入排序算法示意圖void tableinsertsort(table2 *tab) int i,p,q; tab-r0.link=1; tab-r1.link=0; /*第第1個元素為有序靜態(tài)表個元素為有序靜態(tài)表*/ for(i=2;ilength;i+) /*依次插入從第依次插入從第2個開始的所有個開始的所有元素元素*/ q=0;p=tab-r0.link; /*p指向表中第指向表中第1個元素，個元素，q指向指向p的前驅元素位置的前

21、驅元素位置*/ while(p!=0&tab-ri.key=tab-rp.key) /*找插入找插入位置位置*/ q=p; p=tab-rp.link; /*繼續(xù)查找繼續(xù)查找*/ tab-ri.link=p;tab-rq.link=i; 算法算法10.3 表插入排序算法表插入排序算法 基本思想：對待排記錄序列先作基本思想：對待排記錄序列先作“宏觀宏觀”調整，調整，再作再作“微觀微觀”調整，它是由調整，它是由D.L.shell在在1959年提出年提出來的。來的。 所謂所謂“宏觀宏觀”調整，指的是，調整，指的是，“跳躍式跳躍式”的插的插入排序。即：將記錄序列分成若干子序列，每個子入排序。即

22、：將記錄序列分成若干子序列，每個子序列分別進行插入排序。關鍵是，這種子序列不是序列分別進行插入排序。關鍵是，這種子序列不是由相鄰的記錄構成的。假設將由相鄰的記錄構成的。假設將n個記錄分成個記錄分成d個子序個子序列，則這列，則這d個子序列分別為：個子序列分別為：10.2.4 Shell插入排序插入排序 R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 10.2.4 Shell插入排序插入排序 21254925*16080 1 2 3 4 5 6i = 1d = 32125*2516084949d = 208162125*

23、25組內排序得：組內排序得：組內排序得：組內排序得：210825164925*jj+d21254925*1608 1 2 3 4 5621254925*16080 1 2 3 4 5d= 1210825164925*開始時開始時d的值較大，子序列中的對象較少，排序速度的值較大，子序列中的對象較少，排序速度較快；隨著排序進展，較快；隨著排序進展，d 值逐漸變小值逐漸變小(一般可以按一般可以按d=d/2的規(guī)律變化的規(guī)律變化)，子序列中對象個數逐漸變多，由，子序列中對象個數逐漸變多，由于前面工作的基礎，大多數對象已基本有序，所以排于前面工作的基礎，大多數對象已基本有序，所以排序速度仍然很快。序速度仍

24、然很快。 設待排序的設待排序的7記錄的排序碼為記錄的排序碼為312，126，272，226，28，165，123，初始讓，初始讓d=7/2=3，以后每次讓以后每次讓d縮小一半，其排序過程如圖所示?？s小一半，其排序過程如圖所示。 31228123126165226272 0 1 2 3 4 5 6 7(c) 完成完成31212328165226126272 0 1 2 3 4 5 6 7(b) d=112331212627222628165 0 1 2 3 4 5 6 7(a) 初始狀態(tài)初始狀態(tài)d=3習題：給出初始數列習題：給出初始數列47，28，32，15，94，33，14，16在在shell

25、排序下的狀態(tài)變化過程。排序下的狀態(tài)變化過程。d=44728321594331416472814159433321614153216472894331415162832334794d=2d=1結果結果void shellsort(table *L) /*希爾排序希爾排序*/ int i,j,d; d=L-length/2; while ( d=1 ) for (i=d+1; ilength; i+) /*從第從第d+1個元素開始個元素開始,將所有元素依次有序插入到相應的分組中將所有元素依次有序插入到相應的分組中*/ L-r0=L-ri; /*保存第保存第i個元素個元素*/ j=i-d; /*向前

26、找插入位置向前找插入位置*/ while(j0 & L-r0.keyrj.key) /*找插入位找插入位置并后移置并后移*/ L-rj+d=L-rj; /*后移后移*/ j=j-d; /*繼續(xù)向前查找繼續(xù)向前查找*/ L-rj+d=L-r0; /*插入第插入第i個元素的副本個元素的副本*/ d=d/2; 算法算法10.4 Shell插入排序算法插入排序算法10.3 選擇排序選擇排序 選擇排序的基本思想是：每次從待排序的文件中選擇排序的基本思想是：每次從待排序的文件中選擇出排序碼最小的記錄，將該記錄放于已排序文件的選擇出排序碼最小的記錄，將該記錄放于已排序文件的最后一個位置，直到已排序文

27、件記錄個數等于初始待排最后一個位置，直到已排序文件記錄個數等于初始待排序文件的記錄個數為止。序文件的記錄個數為止。 10.3.1直接選擇排序直接選擇排序 首先從所有首先從所有n個待排序記錄中選擇排序碼最小的記個待排序記錄中選擇排序碼最小的記錄，將該記錄與第錄，將該記錄與第1個記錄交換，再從剩下的個記錄交換，再從剩下的n-l個記個記錄中選出排序碼最小的記錄和第錄中選出排序碼最小的記錄和第2個記錄交換。重復這個記錄交換。重復這樣的操作直到剩下樣的操作直到剩下2個記錄時，再從中選出排序碼最小個記錄時，再從中選出排序碼最小的記錄和第的記錄和第n-1個記錄交換。剩下的那個記錄交換。剩下的那1個記錄肯定是

28、個記錄肯定是排序碼最大的記錄，這樣排序即告完成。排序碼最大的記錄，這樣排序即告完成。 直接選擇排序演示直接選擇排序演示2125*i = 12516490825160825*4921i = 221254925*1608 1 2 3 4 5 6初始初始最小者最小者 08交換交換21,08最小者最小者 16交換交換25,1625160825*4921結果結果4925*i = 408162521最小者最小者 25*無交換無交換最小者最小者 25無交換無交換25*i = 54925211608 1 2 3 4 5 649i = 3081625*2521最小者最小者 21交換交換49,21void sel

29、ectsort(table *L) /*簡單選擇排序算法簡單選擇排序算法*/ int i,j,k; for (i=1;ilength;i+) k=i; for (j=i+1;jlength; j+) /*找最小元素所在找最小元素所在位置位置*/ if (L-rj.keyrk.key) k=j; if (k!=i) L-r0=L-ri; /*將第將第i次找到的最小元素放次找到的最小元素放到第到第i個位置個位置*/ L-ri=L-rk; L-rk=L-r0; 直接選擇排序算法執(zhí)行過程如圖直接選擇排序算法執(zhí)行過程如圖10.6所示所示 （見書本）（見書本）10.3.3 堆排序堆排序 為了既要保存中間比

30、較結果，減少后面的比較次為了既要保存中間比較結果，減少后面的比較次數，又不占用大量的附加存儲空間，使排序算法具有數，又不占用大量的附加存儲空間，使排序算法具有較好的性能，較好的性能，Willioms和和Floyd在在1964年提出的稱為年提出的稱為堆排序的算法實現了這一想法。堆排序的算法實現了這一想法。 堆是一個序列堆是一個序列k1,k2,kn，它滿足下面的條件：，它滿足下面的條件： kik2i并且并且kik2i+1，當，當i=1,2, n/2 采用順序方式存儲這個序列，就可以將這個序列采用順序方式存儲這個序列，就可以將這個序列的每一個元素的每一個元素ki看成是一顆有看成是一顆有n個結點的完全

31、二叉樹的個結點的完全二叉樹的第第i個結點，其中個結點，其中k1是該二叉樹的根結點。是該二叉樹的根結點。 堆形：元素序列堆形：元素序列a1,a2,an的如下層次關系：的如下層次關系：a1a2a4a3a5a6123456堆關系堆關系：若：若j=2i或或j=2i+1則則稱稱有堆關系，這時稱有堆關系，這時稱ai為此堆關系的頂，為此堆關系的頂，aj為此堆為此堆關系的基。關系的基。堆堆：滿足以下條件的堆形：滿足以下條件的堆形：對堆形中的所有堆關系：對堆形中的所有堆關系均有均有ai=aj 。 把堆對應的一維數組把堆對應的一維數組(即該序列的順序存儲結構即該序列的順序存儲結構)看作一棵完全二叉樹的順序存儲，那

32、么堆的特征可看作一棵完全二叉樹的順序存儲，那么堆的特征可解釋為，完全二叉樹中任一分支結點的值都小于或解釋為，完全二叉樹中任一分支結點的值都小于或等于它的左、右兒子結點的值。堆的元素序列中的等于它的左、右兒子結點的值。堆的元素序列中的第一個元素第一個元素k1，即對應的完全二叉樹根結點的值，即對應的完全二叉樹根結點的值是所有元素中值最小的。堆排序方法就是利用這一是所有元素中值最小的。堆排序方法就是利用這一點來選擇最小元素。點來選擇最小元素。 在堆中結點序號在堆中結點序號n/2的結點沒有基，實際上的結點沒有基，實際上堆關系滿足完全二叉樹的結構特征。堆關系滿足完全二叉樹的結構特征。3475201212

33、3456152778（a）一個最小堆的例子）一個最小堆的例子91882342241612345651378（b）一個最大堆的例子）一個最大堆的例子一個序列和相應的完全二叉樹一個序列和相應的完全二叉樹 ：312272272 165 123 126 28 226226 8 12 12812316528226272126312下標下標 0 1 2 3 4 5 6 7 8 9123456789以下我們討論最大堆：以下我們討論最大堆：最大堆的重要性質：最大堆的重要性質：1）堆頂元為堆中最大元）堆頂元為堆中最大元2）堆具有部分有序性。即具有存儲比較結果的）堆具有部分有序性。即具有存儲比較結果的功能，遭受破

34、壞時易于調整成新的堆。功能，遭受破壞時易于調整成新的堆。堆的存儲實現堆的存儲實現 一維數組。一維數組。 91 88 42 23 24 16 5 13 1 2 3 4 5 6 7 8a0層1層2層3層堆排序的堆排序的基本思想基本思想：基本操作基本操作1）建堆（將待排序部分調整成堆）建堆（將待排序部分調整成堆）2）取最大元（堆頂元）取最大元（堆頂元）3）并入（將最大元并入已排序部分）并入（將最大元并入已排序部分）建堆算法（建堆算法（R.W.Floyd）1964年提出年提出-篩選法篩選法1）將待排序的數組隨意地組成一個堆形）將待排序的數組隨意地組成一個堆形2）沿堆形自下向上，自右向左依次進行篩選。設

35、）沿堆形自下向上，自右向左依次進行篩選。設當前要篩選當前要篩選ai，這時：，這時：若若ai=max(a2i,a2i+1)，即滿足堆條件，則對，即滿足堆條件，則對ai的篩選結束；的篩選結束；若若ai16不調整不調整42138891241612345652378(c) i=2, 13 下沉兩級下沉兩級42882391241612345651378(d) i=1, 42篩下一層篩下一層91882342241612345651378 91 88 42 23 24 16 5 13 1 2 3 4 5 6 7 8a（e）建成的堆）建成的堆最大元在堆頂最大元在堆頂建堆的關鍵一步：篩選建堆的關鍵一步：篩選Lk

36、若若rlow的右孩子存在且的右孩子存在且大于左兄弟，則令大于左兄弟，則令j指向它指向它，讓它沿大基下沉，讓它沿大基下沉void sift(table *L, int k, int m) int i,j,finished; /*初始化初始化*/ i=k;j=2*i; L-r0=L-rk; finished=0; /*確定下沉位置確定下沉位置*/ while(j=m)&(!finished) if (jrj+1.keyL-rj.key) j+; if(L-r0=L-rj) finished=1; else L-ri=L-rj; i=j; j=2*j; /* 被篩數下沉被篩數下沉*/ L-r

37、i=L-r0; 建堆總體控制：建堆總體控制： for(i= L-length/2 ;i=1;i-) sift (L, i, L-length); /*對所有元素建堆對所有元素建堆*/堆排序過程：堆排序過程：1）建初始堆（大根堆）建初始堆（大根堆）2）重復以下工作，一直到排序結束）重復以下工作，一直到排序結束交換截尾交換截尾重新建堆重新建堆 for(i=L-length;i=2;i-) void heapsort(table *L) int i; for(i=L-length/2;i=1;i-) sift(L,i,L-length); /*對所有元素建堆對所有元素建堆*/for(i=L-leng

38、th;i=2;i-) /* i表示當前堆的大小，表示當前堆的大小，即等待排序的元素的個數即等待排序的元素的個數*/ L-r0=L-ri; L-ri=L-r1; L-r1=L-r0; /*上述上述3條語句為將堆中最條語句為將堆中最小元素和最后一個元素交換小元素和最后一個元素交換*/ sift(L,1,i-1);n若設堆中有若設堆中有 n 個結點，且個結點，且 2k-1 n 2k，則對應，則對應的完全二叉樹有的完全二叉樹有 k 層。在第層。在第 i 層上的結點數層上的結點數 2i (i = 0, 1, , k-1)。在第一個形成初始堆的。在第一個形成初始堆的for循環(huán)中對每一個非葉結點調用了一次堆

39、調整算法循環(huán)中對每一個非葉結點調用了一次堆調整算法 sift( )，因此該循環(huán)所用的計算時間為：，因此該循環(huán)所用的計算時間為：2022kiiik1 1算法分析：算法分析：n其中，其中，i 是層序號，是層序號，2i 是第是第 i 層的最大結點數，層的最大結點數，(k-i-1)是第是第 i 層結點能夠移動的最大距離。層結點能夠移動的最大距離。在第二個在第二個for循環(huán)中，調用了循環(huán)中，調用了n-1次次sift()算法，該算法，該循環(huán)的計算時間為循環(huán)的計算時間為O(nlog2n)。因此，堆排序的時間。因此，堆排序的時間復雜性為復雜性為O(nlog2n)。該算法的附加存儲主要是在第二個該算法的附加存儲

40、主要是在第二個for循環(huán)中用來執(zhí)循環(huán)中用來執(zhí)行對象交換時所用的一個臨時對象。因此，該算法行對象交換時所用的一個臨時對象。因此，該算法的空間復雜性為的空間復雜性為O(1)。堆排序是一個不穩(wěn)定的排序方法。堆排序是一個不穩(wěn)定的排序方法。njnjjikkjkjjjkkjjkkii4 411111111202222222122)(練習：練習：1、給出初始數列、給出初始數列 47、28、32、15、94、33、14、16在堆排序下的建堆過程及示意圖。在堆排序下的建堆過程及示意圖。2、下列四個選項中，哪一個序列組成一個最小堆？、下列四個選項中，哪一個序列組成一個最小堆？a）20、76、35、23、80、54

41、b）20、54、23、80、35、76c）80、23、35、76、20、54d）20、35、23、80、54、76答案：答案：d算法設計題：算法設計題：1、寫一個、寫一個Heapinsert(r,key)算法，將關鍵字算法，將關鍵字插入到堆插入到堆r中，并保證插入后中，并保證插入后r后仍是堆。后仍是堆。2、寫一個建堆算法：從空堆開始，依次讀入元、寫一個建堆算法：從空堆開始，依次讀入元素調用上題中堆插入算法將其插入堆中。素調用上題中堆插入算法將其插入堆中。3、寫一個堆刪除算法、寫一個堆刪除算法heapdelete(r,i)，將，將ri從堆從堆r中刪去。中刪去。10.4交換排序交換排序 交換排序的

42、基本思路：交換排序的基本思路： 對待排序記錄兩兩進行排序碼比較，若不滿足排對待排序記錄兩兩進行排序碼比較，若不滿足排序順序則交換這對記錄，直到任何兩個記錄的排序碼序順序則交換這對記錄，直到任何兩個記錄的排序碼都滿足排序要求為止。都滿足排序要求為止。 快速排序快速排序冒泡排序冒泡排序 第第1趟，對所有記錄從左到右每相鄰兩個記錄的趟，對所有記錄從左到右每相鄰兩個記錄的排序碼進行比較，如果這兩個記錄的排序碼不符合排排序碼進行比較，如果這兩個記錄的排序碼不符合排序要求，則進行交換，這樣一趟做完，將排序碼最大序要求，則進行交換，這樣一趟做完，將排序碼最大者放在最后一個位置；者放在最后一個位置； 第第2趟

43、對剩下的趟對剩下的n-l個待排序記錄重復上述過程，個待排序記錄重復上述過程，又將一個排序碼放于最終位置，反復進行又將一個排序碼放于最終位置，反復進行n-l次，可將次，可將n-l個排序碼對應的記錄放至最終位置，剩下的即為排個排序碼對應的記錄放至最終位置，剩下的即為排序碼最小的記錄，它在第序碼最小的記錄，它在第1的位置處。的位置處。 如果在某一趟中，沒有發(fā)生交換，則說明此時所如果在某一趟中，沒有發(fā)生交換，則說明此時所有記錄已經按排序要求排列完畢，排序結束。有記錄已經按排序要求排列完畢，排序結束。 10.4.1 冒泡排序冒泡排序 一趟冒泡：對數列中指定的起點到終點間的數據一趟冒泡：對數列中指定的起點

44、到終點間的數據進行連續(xù)冒泡。進行連續(xù)冒泡。4728321594331416例：例：2847321594331416324728159433141615472832943314161547283294331416339415472832141614941547283233161694154728323314void bubblesort(table *L) /*冒泡排序冒泡排序*/ int i,j,flag; i=L-length; /*變量變量i記錄參與冒泡排序的元素個數記錄參與冒泡排序的元素個數/ while (i1) flag=0; for (j=0;jrj.keyL-rj+1.key)

45、/逆序則交換逆序則交換 L-r0=L-rj; L-rj=L-rj+1; L-rj+1=L-r0; flag=1; if (flag=0) break; i-;/元素個數減元素個數減/ /*算法算法10.8 冒泡排序算法冒泡排序算法*/ 二、快速排序二、快速排序基本思想：基本思想：1）找一個記錄，以它的關鍵字作為）找一個記錄，以它的關鍵字作為“樞軸樞軸”，（通常為第一個數（通常為第一個數t）2）劃分）劃分其關鍵字小于樞軸的記錄均移動至該其關鍵字小于樞軸的記錄均移動至該記錄之前，反之，凡關鍵字大于樞軸的記錄均移記錄之前，反之，凡關鍵字大于樞軸的記錄均移動至該記錄之后。動至該記錄之后。3）對上步分成

46、的兩個無序數組段重復）對上步分成的兩個無序數組段重復1）、）、2）操作直到段長為操作直到段長為1。t=tpivot2125*i = 125164908pivot21254925*16080 1 2 3 4 5 6pivot例：例：211608i = 225*pivot4925i = 3081621254925*關鍵問題：關鍵問題：如何劃分？如何劃分？事實：劃分過程也是當前選出數事實：劃分過程也是當前選出數t的最后定位過程。的最后定位過程。方法：從外向內來回比較法。方法：從外向內來回比較法。1）將當前選擇的數保存到）將當前選擇的數保存到t中，以空出左端。中，以空出左端。2）從右向左依次比較，放過

47、那些大于）從右向左依次比較，放過那些大于t的數，一的數，一直找到第一個小于等于直找到第一個小于等于t的數；將此數放入空左端的數；將此數放入空左端，并令其空出的位置為新右端，原左端的右鄰為，并令其空出的位置為新右端，原左端的右鄰為新左端。新左端。3）從左向右依次地放過那些）從左向右依次地放過那些=t的數；將此數放入空右端，并令其空的數；將此數放入空右端，并令其空出的位置為新左端，原右端的左鄰為新右端。出的位置為新左端，原右端的左鄰為新右端。4）重復）重復2）3）步，直至）步，直至t進入最終位置。進入最終位置。例：例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：21254925*

48、1608從右向左找第從右向左找第一個小于一個小于t的數的數21rightleft例：例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608rightleft例：例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608rightleft21例：例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608rightleft從左向右找第一從左向右找第一個大于個大于 t 的數的數例：例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608rightleft例：例： 1 2 3

49、4 5 6t =a1初始序列如下：初始序列如下：254925*1608rightleft21從右向從右向左掃描左掃描例：例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608leftright21例：例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608leftright例：例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608leftright從左向從左向右掃描右掃描21例例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608rightleft例：例： 1

50、2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608rightleft一次劃分結束條件：一次劃分結束條件：left=right21 快速排序就是不斷地對原始數據段及劃分中快速排序就是不斷地對原始數據段及劃分中分出的新數據段作劃分。分出的新數據段作劃分。關鍵一步：對關鍵一步：對 L-rleft.right作一次來回比較。作一次來回比較。1）從右向左找第一個不大于）從右向左找第一個不大于t的數。的數。 while (leftright & t.keyrright.key) right-; 2）將）將rright填入空左端，并設置新左端。填入空左端，并設置新左端。

51、if (leftright) 3）從左向右找第一個大于）從左向右找第一個大于t的數。的數。 while ( ) left+; 4）將）將rleft填入空右端，并設置新右端。填入空右端，并設置新右端。if (leftrright=L-rleft;right-; L-rleft=L-rright;left+;leftL-rleft.keyright快速排序的總體控制：快速排序的總體控制：quicksort(&L, low, high )1）初始化：）初始化： left=low; right=high; t=rleft;2）對當前數據段作劃分：）對當前數據段作劃分： do 一次來回比較；一次

52、來回比較； while (left!=right);3）將）將t填入最終位置填入最終位置:L-r =t; 4）遞歸地對）遞歸地對Llow.left-1，Lleft+1.high 作快作快速排序。速排序。 quicksort( ); leftquicksort( );L,low,left-1L,left+1,highvoid quicksort(table *L,int low, int high) int left,right; recordtype t; if (lowrleft; do while (leftright & t.keyrright.key) right-; /*從右

53、往左找第一個小于等于從右往左找第一個小于等于t的元素的元素*/ if (leftrleft=L-rright; left+; /*將將rright的值填入左端，并設新左端的值填入左端，并設新左端*/ while (leftL-rleft.key) left+; /*從左往右找第一個大于從左往右找第一個大于t的元素的元素*/快速排序遞歸快速排序遞歸出口條件出口條件一次劃分一次劃分初始化工作初始化工作來回比較進行來回比較進行一次劃分一次劃分 if (leftrright=L-rleft; right-; /*將將rleft的值填入右端，并設新右端的值填入右端，并設新右端*/ while (left

54、!=right); L-rleft=t; /*t存入相應位置存入相應位置*/ /*遞歸對左段和右段進行快速排序遞歸對左段和右段進行快速排序*/ quicksort( L,low,left-1); quicksort( L,left+1,high); 算法分析：算法分析： 快速排序被認為是在所有同數量級快速排序被認為是在所有同數量級O(nlogn)的的排序方法中，其平均性能是最好的。排序方法中，其平均性能是最好的。例例 但是，若待排記錄的初始狀態(tài)為按關鍵字有序但是，若待排記錄的初始狀態(tài)為按關鍵字有序時，快速排序將蛻化為冒泡排序，其時間復雜度為時，快速排序將蛻化為冒泡排序，其時間復雜度為O(n2)

55、。初始序列：初始序列：20 30 40 50 60 70 80 90 100什么樣的初始什么樣的初始序列具有最佳的序列具有最佳的快速排序時間效率？快速排序時間效率？ 練習：練習：1、給定初始序列、給定初始序列31，68，45，90，23，39，54，12、87、76，請寫出以，請寫出以31為樞軸的劃分為樞軸的劃分結果結果。2、試設計一個算法，使得在、試設計一個算法，使得在O(n)的時間內重排數組，的時間內重排數組，將所有取負值的關鍵字放在所有取非負值的關鍵字將所有取負值的關鍵字放在所有取非負值的關鍵字之前。之前。思考題：思考題：采用鏈式存儲的線性表采用鏈式存儲的線性表如何進行快速排序。如何進行

56、快速排序。 （一）雙鏈表一）雙鏈表head4010608020（二）單鏈表（帶頭結點）（二）單鏈表（帶頭結點） head 4010806030tail=NULLpqpresp指示當前用于劃分的樞軸指示當前用于劃分的樞軸q指示當前與指示當前與p結點進行比較的結點；結點進行比較的結點；pre 指示指示q的前驅結點；的前驅結點；s用于指示被移動的結點。用于指示被移動的結點。（二）單鏈表（帶頭結點）（二）單鏈表（帶頭結點） head 4010806030tail=NULLpqpres將將s指示的結點取下插入到當前的鏈首由以下步驟完成：指示的結點取下插入到當前的鏈首由以下步驟完成：pre-next=q;

57、（二）單鏈表（帶頭結點）（二）單鏈表（帶頭結點） head 4010806030tail=NULLpqpres將將s指示的結點取下插入到當前的鏈首由以下步驟完成：指示的結點取下插入到當前的鏈首由以下步驟完成：pre-next=q;s-next=head-next;（二）單鏈表（帶頭結點）（二）單鏈表（帶頭結點） head 4010806030tail=NULLpqpres將將s指示的結點取下插入到當前的鏈首由以下步驟完成：指示的結點取下插入到當前的鏈首由以下步驟完成：pre-next=q;s-next=head-next;head-next=s;（二）單鏈表（帶頭結點）（二）單鏈表（帶頭結點）

58、 head 4010806030tail=NULLpqpres將將s指示的結點取下插入到當前的鏈首由以下步驟完成：指示的結點取下插入到當前的鏈首由以下步驟完成：pre-next=q;s-next=head-next;head-next=s;（二）單鏈表（帶頭結點）（二）單鏈表（帶頭結點）將將s指示的結點取下插入到當前的鏈首由以下步驟完成：指示的結點取下插入到當前的鏈首由以下步驟完成：pre-next=q;s-next=head-next;head-next=s; head 1040806030tail=NULLpqpres（二）單鏈表（帶頭結點）（二）單鏈表（帶頭結點）若若q指示的結點值比指示

59、的結點值比p指示的結點值大，則該結點的位指示的結點值大，則該結點的位置保留不動，處理下一個結點。即：置保留不動，處理下一個結點。即： head 1040806030tail=NULLpqprespre=q;q=q-next;（二）單鏈表（帶頭結點）（二）單鏈表（帶頭結點）若若q指示的結點值比指示的結點值比p指示的結點值大，則該結點的位指示的結點值大，則該結點的位置保留不動，處理下一個結點。即：置保留不動，處理下一個結點。即： head 1040806030tail=NULLpqprespre=q;q=q-next;（二）單鏈表（帶頭結點）（二）單鏈表（帶頭結點）若若q指示的結點值比指示的結點值

60、比p指示的結點值大，則該結點的位指示的結點值大，則該結點的位置保留不動，處理下一個結點。即：置保留不動，處理下一個結點。即： head 1040806030tail=NULLpqprespre=q;q=q-next;（二）單鏈表（帶頭結點）（二）單鏈表（帶頭結點） head 1040806030tail=NULLpqpres（二）單鏈表（帶頭結點）（二）單鏈表（帶頭結點） head 3010804060tail=NULLpqpres（二）單鏈表（帶頭結點）（二）單鏈表（帶頭結點） head 3010804060tail=NULLpq=NULLpres劃分結束條件：劃分結束條件：q=tail;遞歸地對前半部分和后半部分進行快速鏈式排序：遞歸地對前半部分和后半部分進行快速鏈式