基本數據結構——排序10.10)

1、1 1。函數實現。函數實現( (初始化一個帶表頭結點的鏈表）初始化一個帶表頭結點的鏈表）node node * * initiatesl initiatesl (void) (void) node node * * h; h;h = (node h = (node * * )malloc(sizeof(node )malloc(sizeof(node); ); h-data = NULL;h-data = NULL;h-next = NULL; h-next = NULL; return (h);return (h); hNULLNULL NULLNULLwhile(p!=NULL)next=

2、p-next;p-next=pre;pre=p;p=next;nextpprepprea ai ia ai-1i-1a ai+1i+1a ai-2i-2a ai+2i+2void rev_list(node *h) /*請同學們在此處編制逆轉鏈表的程序段請同學們在此處編制逆轉鏈表的程序段*/node *pre,*next,*p;if(h=NULL) return;if(h-next=NULL) return;pre=h;p=h-next;while(p!=NULL)next=p-next;p-next=pre;pre=p;p=next;h-next-next=NULL;h-next = pre

3、;nexth hpprepprenextpprenextppreh ha a2 2a a1 1a a3 3a a0 0pprenext=nullh ha a2 2a a1 1a a3 3a a0 0P=nullpreh ha a2 2a a1 1a a3 3a a0 01.9 排序一、基本概念一、基本概念二、歸并排序二、歸并排序三、插入排序三、插入排序四、選擇排序四、選擇排序五、交換排序五、交換排序六、各種排序算法的六、各種排序算法的比較比較一、基本概念1. 1. 排序排序設有含設有含n n個記錄的序列為個記錄的序列為 R R1 1,R,R2 2, ,R,Rn n ，其相應的關鍵字序列為，其相

4、應的關鍵字序列為 K K1 1,K,K2 2,.,K,.,Kn n ?，F要求確定一種排序?，F要求確定一種排序p p1 1,p,p2 2,.p,.pn n, , 使其關鍵字使其關鍵字滿足遞增（或遞減）的關系：滿足遞增（或遞減）的關系：K Kp1p1KKp2p2KKpnpn（或（或K Kp1p1KKp2p2 KKpnpn）使原序列成為一個按使原序列成為一個按關鍵字有序的序列關鍵字有序的序列： R Rp1p1,R,Rp2p2, ,R Rpnpn 一、基本概念2.2.排序方法的穩(wěn)定性排序方法的穩(wěn)定性若若K Ki i=K=Kj j(1in ,1jn ,ij)(1in ,1jn ,ij)，在排序前，在排序

5、前R Ri i領先于領先于R Rj j ，排序后排序后R Ri i仍領先于仍領先于R Rj j ，則稱此排序方法是，則稱此排序方法是穩(wěn)定穩(wěn)定的；反之稱為的；反之稱為不不穩(wěn)定穩(wěn)定的。的。3. 3. 排序的分類排序的分類o 若排序時待排序記錄存放在內存中進行排序，則稱為若排序時待排序記錄存放在內存中進行排序，則稱為內部排序內部排序；o 若待排序記錄數量很大，在內存中一次不能容納全部記錄，需若待排序記錄數量很大，在內存中一次不能容納全部記錄，需要在排序過程中對外存進行訪問，則稱為要在排序過程中對外存進行訪問，則稱為外部排序外部排序。一、基本概念4.4.基本操作基本操作1 1）對記錄中關鍵字大小進行比

6、較；）對記錄中關鍵字大小進行比較；2 2）將記錄從一個位置移到另一個位置。）將記錄從一個位置移到另一個位置。5. 5. 排序的時間開銷排序的時間開銷:(:(時間復雜度）時間復雜度） 排序的時間開銷是衡量算法好壞的最重要的標志。排序的時排序的時間開銷是衡量算法好壞的最重要的標志。排序的時間開銷可用算法執(zhí)行中的間開銷可用算法執(zhí)行中的數據比較次數與數據移動次數數據比較次數與數據移動次數來衡來衡量。量。6. 6. 算法執(zhí)行時所需的附加存儲算法執(zhí)行時所需的附加存儲 評價算法好壞的另一標準。評價算法好壞的另一標準。一、基本概念7. 7. 待排序的數據表待排序的數據表o 使用順序存儲結構存儲使用順序存儲結構

7、存儲其數據類型定義如下：其數據類型定義如下：o 記錄結點的類型定義：記錄結點的類型定義：typedef structtypedef struct keywordtypekeywordtype key; key;datatypedatatype data; data;RECORDNODERECORDNODE;o 待排序的數據表是待排序的數據表是RECORDNODE類型的數組類型的數組structstruct RECORDNODE a; RECORDNODE a;二、歸并排序1 1. . 歸并，歸并，是將兩個或兩個以上的有序表合并成一個新的有序表。是將兩個或兩個以上的有序表合并成一個新的有序表。o

8、 兩個有序表兩個有序表aal l aam m 和和aam m+1 +1 aan n 。它們可歸并成一個有序表。它們可歸并成一個有序表, , 存存于另一對象序列于另一對象序列b b的的bbl l bbn n 中。中。 這種歸并方法稱為這種歸并方法稱為兩路歸并兩路歸并 (2-way merging)(2-way merging)。i ik ki ik k1 m m+1 end1 m m+1 endab b08i ij jk k16k ki ij ji ij jk kk kj ji i2125k ki ij j25*k ki ij j37k kj ji i49k ki ij j54k ki i627

9、2 93設變量設變量 i i 和和 j j 分別是表分別是表aal l aam m 和和aam m+1 +1 aan n 的當前檢測指針。的當前檢測指針。變量變量 k k 是存放指針。是存放指針。當當 i i 和和 j j 都在兩個表的表長內變化時都在兩個表的表長內變化時, , 根據對應項的排序碼的大小根據對應項的排序碼的大小, ,依次把排序碼依次把排序碼小的對象排放到新表小的對象排放到新表 k k 所指位置所指位置中；中；當當 i i 與與 j j 中有一個已經超出表長時，將另一個表中的剩余部分照抄到新表中。中有一個已經超出表長時，將另一個表中的剩余部分照抄到新表中。二、歸并排序o 兩路歸并

10、算法的函數實現兩路歸并算法的函數實現void merge(int start,int end,intvoid merge(int start,int end,int m,RECORDNODE a) m,RECORDNODE a)/ /* *將有序表將有序表a(start:start+m-1)a(start:start+m-1)和和a(start+m:end)a(start+m:end)歸并為一個新的有序表歸并為一個新的有序表a(start:end)a(start:end)* */ /RECORDNODE tempMAXSIZE;RECORDNODE tempMAXSIZE;intint i,j

11、,k; i,j,k;i=start;j=start+m;k=start;i=start;j=start+m;k=start;while(i=(start+m-1)&j=end)while(i=(start+m-1)&j=end)if(ai.keyaj.key)tempk=ai;k+;i+;if(ai.keyaj.key)tempk=ai;k+;i+;elsetempk=aj;k+;j+;elsetempk=aj;k+;j+;while(j=end)tempk=aj;k+;j+;while(j=end)tempk=aj;k+;j+;while(i=(start+m-1)tempk

12、=ai;k+;i+;while(i=(start+m-1)tempk=ai;k+;i+;for(i=start;i=end;i+)ai=tempi;for(i=start;i=end;i+)ai=tempi;/ /* *將臨時表的內容存回到將臨時表的內容存回到a a中中* */ / 二、歸并排序二、歸并排序2. 2. 歸并排序歸并排序o 歸并排序算法就是利用兩路歸并過程進行排序的。歸并排序算法就是利用兩路歸并過程進行排序的。其基本思想是：其基本思想是：o 假設初始對象序列有假設初始對象序列有 n n 個對象，首先把它看成是個對象，首先把它看成是 n n 個長度為個長度為 1 1 的有序子序列的

13、有序子序列 ( (歸并項歸并項) )，先做兩兩，先做兩兩歸并，得到歸并，得到 n n / 2/ 2 個長度為個長度為 2 2 的歸并項的歸并項 ( (如果如果 n n 為奇數，則最后一個有序子序列的長度為為奇數，則最后一個有序子序列的長度為1)1)；再；再做兩兩歸并，做兩兩歸并，如此重復，最后得到一個長度為，如此重復，最后得到一個長度為 n n 的有序序列。的有序序列。2125例：給出序列如圖。用歸并排序法排序過程如下例：給出序列如圖。用歸并排序法排序過程如下n=11o 歸并排序的算法Void MergeSort(RECORDNODE a,intVoid MergeSort(RECORDNOD

14、E a,int n) n)/ /* *對長度為對長度為n n的數組的數組a a排序排序* */ /intint length,left,right; length,left,right;left=1;length=1;left=1;length=1;while(lengthn)while(lengthn)right=min(n,left+2right=min(n,left+2* *length-1)length-1)Merge(left,right,length,a);Merge(left,right,length,a);if(right+lengthn) left=right+1;if(ri

15、ght+lengthn) left=right+1;/右邊還有待合并段右邊還有待合并段elselengthelselength* *=2;left=1;=2;left=1;/重新開始下一趟排序重新開始下一趟排序while(lengthn)while(lengthn)right=min(n,left+2right=min(n,left+2* *length-1)length-1)Merge(left,right,length,a);Merge(left,right,length,a);if(right+lengthn) left=right+1;if(right+lengthn) left=ri

16、ght+1;elselengthelselength* *=2;left=1;=2;left=1;o 歸并排序的算法Void MergeSort(RECORDNODE a,intVoid MergeSort(RECORDNODE a,int n) n)/ /* *對長度為對長度為n n的數組的數組a a排序排序* */ /intint length,left,right; length,left,right;left=1;length=1;left=1;length=1;while(lengthn)while(lengthn)right=min(n,left+2right=min(n,left

17、+2* *length-1)length-1)/限制限制rightright的值，使其不越界的值，使其不越界Merge(left,right,length,a);Merge(left,right,length,a);if(right+lengthn) left=right+1;if(right+lengthn) left=right+1;/右邊還有待合并段右邊還有待合并段elselengthelselength* *=2;left=1;=2;left=1;/重新開始下一趟排序重新開始下一趟排序二、歸并排序3. 3. 算法分析算法分析1) 1) 時間復雜度時間復雜度在函數在函數MergeSort

18、MergeSort中中whilewhile循環(huán)將被執(zhí)行循環(huán)將被執(zhí)行l(wèi)oglog2 2n n次次在每個在每個whilewhile循環(huán)中，將調用循環(huán)中，將調用MergeMerge函數函數n/(2length)n/(2length)次次而在每個而在每個MergeMerge函數中，將比較函數中，將比較lengthlength次次, ,故在每個故在每個whilewhile循環(huán)中，將比較循環(huán)中，將比較O(n)O(n)次次因此，此因此，此算法的時間復雜度為算法的時間復雜度為O(nlogO(nlog2 2n)n)2) 2) 空間復雜度空間復雜度o 歸并排序占用附加存儲較多歸并排序占用附加存儲較多, , 需要另

19、外一個與原待排序需要另外一個與原待排序對象對象數組同樣大小的輔助數組數組同樣大小的輔助數組。這是這個算法的缺點。這是這個算法的缺點。3) 3) 歸并排序是一個歸并排序是一個穩(wěn)定穩(wěn)定的排序算法的排序算法三、插入排序三、插入排序o 插入排序插入排序是將當前是將當前無序區(qū)中最前端無序區(qū)中最前端的記錄的記錄插入到有序區(qū)插入到有序區(qū)中，逐漸擴大有中，逐漸擴大有序區(qū)，直到所有記錄都插入到有序區(qū)中為止。序區(qū)，直到所有記錄都插入到有序區(qū)中為止。1. 直接插入排序直接插入排序1)1)基本思想是基本思想是 : : 當插入第當插入第i i ( (i i 1) 1) 個對象時個對象時, , 前面的前面的 a1 , a

20、1 , , , aai i-1-1已經排好序。這時已經排好序。這時, , 用用aai i 的排序碼與的排序碼與aai i-1, a-1, ai i-2, -2, 的關的關鍵碼順序進行比較鍵碼順序進行比較, , 找到插入位置即將找到插入位置即將aai i 插入插入, , 原來位置上的對象向原來位置上的對象向后順移。后順移。在有序區(qū)的前端在有序區(qū)的前端a0a0處設一個處設一個監(jiān)視哨監(jiān)視哨，存放當前要插入的關鍵字。，存放當前要插入的關鍵字。各趟排序結果各趟排序結果1 2 3 4 5 6監(jiān)視監(jiān)視哨哨 0 1 2 3 4 5 6252525 0 1 2 3 4 5 6494949void straigh

21、tinsert(RECORDNODE a,intvoid straightinsert(RECORDNODE a,int n) n)/ /* *使用直接插入排序法對數組使用直接插入排序法對數組a(1:n)a(1:n)排序排序* */ /for (i=2;i=n;i+)for (i=2;i=n;i+)a0=ai; /a0=ai; /* *設置監(jiān)視哨設置監(jiān)視哨* */ / j=i-1; j=i-1;while (a0.keyaj.key)while (a0.keyaj.key)aj+1=aj;aj+1=aj;j-;j-; aj+1=a0; aj+1=a0;252525* * * 0 1 2 3 4

22、 5 6161616 0 1 2 3 4 5 6080808 0 1 2 3 4 5 61 2 3 4 5 6完成三、插入排序2) 2) 算法分析算法分析o 設待排序對象個數為設待排序對象個數為n, n, 則該算法的則該算法的whilewhile循環(huán)執(zhí)行循環(huán)執(zhí)行n-1n-1趟。趟。o 關鍵碼比較次數和對象移動次數與對象關鍵碼的初始排列有關。關鍵碼比較次數和對象移動次數與對象關鍵碼的初始排列有關。最好情況下最好情況下( (正序正序),), 總的關鍵碼比較次數為總的關鍵碼比較次數為 n n-1, -1, 對象移動次數為對象移動次數為 2(2(n n-1)-1)。最壞情況下最壞情況下( (逆序逆序)

23、,), 則總關鍵碼比較次數則總關鍵碼比較次數KCNKCN和對象移動次數和對象移動次數RMNRMN分別為分別為nininnniRMNnn2)n1)-(iKCN2222141221/)()( ,/)(22void straightinsert(RECORDNODE a,intvoid straightinsert(RECORDNODE a,int n) n)/ /* *使用直接插入排序法對數組使用直接插入排序法對數組a(1:n)a(1:n)排序排序* */ /for (i=2;i=n;i+)for (i=2;i=n;i+)a0=ai; /a0=ai; /* *設置監(jiān)視哨設置監(jiān)視哨* */ j=i-

24、1;/ j=i-1;while (a0.keyaj.key)while (a0.keyaj.key)aj+1=aj;aj+1=aj;j-;j-; aj+1=a0; aj+1=a0;三、插入排序o 在平均情況下的排序碼比較次數和對象移動次數約為在平均情況下的排序碼比較次數和對象移動次數約為 n n2 2/4/4。因此，直接插。因此，直接插入入排序的時間復雜度為排序的時間復雜度為 o(o(n n2 2) )。o 空間復雜度空間復雜度:o(1):o(1)o 直接插入排序是一種直接插入排序是一種穩(wěn)定穩(wěn)定的排序方法的排序方法。練習：練習：在對一組記錄（在對一組記錄（54，38，96，23，15，72，6

25、0，45，83）進）進行直接插入排序時，當把第行直接插入排序時，當把第7個記錄個記錄60插入到有序表時，為尋插入到有序表時，為尋找插入位置至少需比較找插入位置至少需比較 次。次。 三、插入排序2. 2. 折半插入排序折半插入排序1）與直接插入排序相比，除了采用的是折半查找尋找插入的位置外，其它類似。與直接插入排序相比，除了采用的是折半查找尋找插入的位置外，其它類似。2 2）算法）算法void BinarySort(RECORDNODE a,intvoid BinarySort(RECORDNODE a,int n) n)for (i=2;i=n;i+)for (i=2;i=n;i+)a0=ai

26、; low=1; high=i-1;a0=ai; low=1; high=i-1; while (lowhigh)while (lowhigh) mid=(low+high)/2;mid=(low+high)/2;if (a0.keyamid.key) high=mid-1;if (a0.key=low;j-) aj+1=aj;for (j=i-1;j=low;j-) aj+1=aj;alow=a0;alow=a0; 252525* * * 0 1 2 3 4 5 6161616 0 1 2 3 4 5 6三、插入排序3) 算法分析算法分析它所需的關鍵碼比較次數與待排序對象序列的初始排列無關它

27、所需的關鍵碼比較次數與待排序對象序列的初始排列無關, , 僅依賴僅依賴于對象個數。將于對象個數。將 n n 個對象個對象( (為推導方便為推導方便, , 設為設為 n n=2=2k k ) )用折半插入排用折半插入排序所進行的排序碼比較次數為：序所進行的排序碼比較次數為：ninni222log1logo其記錄移動的數目與直接插入排序相同其記錄移動的數目與直接插入排序相同因此，因此，此算法的時間復雜度為此算法的時間復雜度為O(n2)o空間復雜度同直接插入排序空間復雜度同直接插入排序:O(1)o折半插入排序是一個折半插入排序是一個穩(wěn)定穩(wěn)定的排序算法的排序算法三、插入排序3. 希爾排序希爾排序1)

28、1) 希爾排序方法又稱為希爾排序方法又稱為縮小增量排序?？s小增量排序。2) 2) 該方法的基本思想是該方法的基本思想是 : : 設待排序對象序列有設待排序對象序列有 n n 個對象個對象, , 首先首先取一個整數取一個整數 gap n gap =1)while(d=1) for(i=d+1;i=n;i+) for(i=d+1;i0& 0& sj.keysj.keys0.key)s0.key) sj+d sj+d=sj=sj sj sj=s0;=s0;d=(d+1)/2;d=(d+1)/2;1 2 3 4 5 6494949252525* * *08080821212149494

29、9252525161616080808494949161616252525* * *0808082121212525251 2 3 4 5 63 3）函數實現）函數實現Void shellsort(RECORDNODE s,intVoid shellsort(RECORDNODE s,int n) n)/ /* *對記錄數組對記錄數組s1:ns1:n進行希爾排序進行希爾排序* */ / /* * d d1 1=n/2,d=n/2,di i=(d=(di-1i-1+1)/2 +1)/2 * */ /intint i,j,d;d=n/2; i,j,d;d=n/2;while(d=1)while(d

30、=1) for(i=d+1;i=n;i+) for(i=d+1;i0& 0& sj.keysj.keys0.key)s0.key) sj+d sj+d=sj=sj sj sj=s0;=s0;d=(d+1)/2;d=(d+1)/2;1 2 3 4 5 6希爾排序是一種希爾排序是一種不穩(wěn)定不穩(wěn)定的排序方法。的排序方法。1 2 3 4 5 6初始序列初始序列3.希爾排序3 3）函數實現）函數實現Void shellsort(RECORDNODE s,intVoid shellsort(RECORDNODE s,int n) n)/ /* *對記錄數組對記錄數組s1:ns1:n進行希爾

31、排序進行希爾排序* */ / /* * d d1 1=n/2,d=n/2,di i=(d=(di-1i-1+1)/2 +1)/2 * */ /intint i,j,d;d=n/2; i,j,d;d=n/2;while(d=1)while(d=1) for(i=d+1;i=n;i+) for(i=d+1;i0& 0& sj.keysj.keys0.key)s0.key) sj+d sj+d=sj=sj sj sj=s0;=s0;d=(d+1)/2;d=(d+1)/2;設待排序的記錄為設待排序的記錄為(20,16,13,14,19)(20,16,13,14,19)，經過下列過程將這

32、些記錄排，經過下列過程將這些記錄排序。序。20,16,13,14,1920,16,13,14,1916,20,13,14,1916,20,13,14,1913,16,20,14,1913,16,20,14,1913,14,16,20,1913,14,16,20,1913,14,16,19,2013,14,16,19,20所用的排序方法是所用的排序方法是 。A. A. 直接插入排序直接插入排序B. B. 冒泡排序冒泡排序C. C. 希爾排序希爾排序D. D. 堆排序堆排序四、選擇排序o 選擇排序選擇排序是不斷在待排序序列是不斷在待排序序列（無序區(qū)）中按記錄關鍵（無序區(qū)）中按記錄關鍵字遞增（或遞減

33、）次序選擇記錄字遞增（或遞減）次序選擇記錄，放入，放入有序區(qū)的一端有序區(qū)的一端，逐漸擴大有序區(qū)，直到整個記錄區(qū)為有序區(qū)為止。逐漸擴大有序區(qū)，直到整個記錄區(qū)為有序區(qū)為止。 其基本思想是其基本思想是: : 每一趟每一趟 ( (例如第例如第 i i 趟趟, , i i =1, 2, =1, 2, , , n n-1) -1) 在后面在后面 n-i n-i 個待排序對象中選出排序碼最小的對個待排序對象中選出排序碼最小的對象象, , 作為有序對象序列的第作為有序對象序列的第 i i 個對象。待到第個對象。待到第 n n-1 -1 趟作完趟作完, , 待排序對象只剩下待排序對象只剩下1 1個個, , 就不

34、用再選了。就不用再選了。四、選擇排序1.1. 簡單選擇排序簡單選擇排序 基本步驟：在第基本步驟：在第i i趟趟(i=1(i=1開始開始) )(1)(1)在一組對象在一組對象 aai i aan n 中選擇具有最小關鍵字的對象；中選擇具有最小關鍵字的對象；(2)(2)若它不是這組對象中的第一個對象若它不是這組對象中的第一個對象, , 則將它與這組對象中的第則將它與這組對象中的第一個對象一個對象aiai對調對調; ;(3)(3)在這組對象中剔除這個具有最小關鍵字的對象。在剩下的對象在這組對象中剔除這個具有最小關鍵字的對象。在剩下的對象aai i+1+1aan n 中重復執(zhí)行第中重復執(zhí)行第(1)(1

35、)、(2)(2)步步, , 直到剩余對象只有一直到剩余對象只有一個為止。個為止。251625*4921i = 1結束結束最小者最小者212525*16081 2 3 4 5 6初始初始493 3）算法）算法void SelectSort(RECORDNODE a,intvoid SelectSort(RECORDNODE a,int n) n)/ /* *對記錄數組對記錄數組a1:na1:n進行簡單選擇排序進行簡單選擇排序* */ /intint i,j,min;RECORDNODE t; i,j,min;RECORDNODE t;for (i=1;in;i+)for (i=1;in;i+)m

36、in=i;min=i;/ /* *記下位置記下位置* */ /for(j=i+1;j=n;j+)for(j=i+1;jaj.key) min=j;if (amin.keyaj.key) min=j;if (min!=i)if (min!=i)/ /* *交換交換* */ /t=amin; amin=ai; ai=t;t=amin; amin=ai; ai=t;jminjjj minj mini=12125251608491 2 3 4 5 649i = 2結束結束25*2521251625*4921i = 2最小者最小者3 3）算法）算法void SelectSort(RECORDNODE a

37、,intvoid SelectSort(RECORDNODE a,int n) n)/ /* *對記錄數組對記錄數組a1:na1:n進行簡單選擇排序進行簡單選擇排序* */ /intint i,j,min;RECORDNODE t; i,j,min;RECORDNODE t;for (i=1;in;i+)for (i=1;in;i+)min=i;min=i;/ /* *記下位置記下位置* */ /for(j=i+1;j=n;j+)for(j=i+1;jaj.key) min=j;if (amin.keyaj.key) min=j;if (min!=i)if (min!=i)/ /* *交換交換

38、* */ /t=amin; amin=ai; ai=t;t=amin; amin=ai; ai=t;minjjj minj49結果結果4925*1 2 3 4 5 6i = 425最小者最小者最小者最小者i = 54925各趟排序后的結果各趟排序后的結果49i = 325*2521最小者最小者1. 簡單選擇排序4 4）算法分析）算法分析o 算法由兩層循環(huán)構成，外層循環(huán)表示共需進行算法由兩層循環(huán)構成，外層循環(huán)表示共需進行n-1n-1趟排序趟排序. .每趟內層循每趟內層循環(huán)需進行環(huán)需進行n-in-i次比較次比較. .每趟最好情況不交換每趟最好情況不交換. .最壞情況做一次交換，即最壞情況做一次交換

39、，即記錄移動次數最多為記錄移動次數最多為3 3。o 總的時間性能為總的時間性能為 比較次數：比較次數：n(n-1)/2(n(n-1)/2(所有情況相同所有情況相同) ) 移動次數：移動次數：最好情況為最好情況為0,0,最壞情況下為最壞情況下為3(n-1)3(n-1)o 所以總的時間復雜度為：所以總的時間復雜度為：O(nO(n2 2) )o 空間復雜度為：空間復雜度為：O(1) O(1) 交換記錄時用交換記錄時用3 3）算法）算法void SelectSort(RECORDNODE a,intvoid SelectSort(RECORDNODE a,int n) n)/ /* *對記錄數組對記錄

40、數組a1:na1:n進行簡單選擇排序進行簡單選擇排序* */ /intint i,j,min;RECORDNODE t; i,j,min;RECORDNODE t;for (i=1;in;i+)for (i=1;in;i+)min=i;min=i;/ /* *記下位置記下位置* */ /for(j=i+1;j=n;j+)for(j=i+1;jaj.key) min=j;if (amin.keyaj.key) min=j;if (min!=i)if (min!=i)/ /* *交換交換* */ /t=amin; amin=ai; ai=t;t=amin; amin=ai; ai=t;49i =

41、2結束結束25*2521251625*4921i = 2最小者最小者212525*16081 2 3 4 5 6初始初始4949結果結果o簡單選擇排序是一種簡單選擇排序是一種不穩(wěn)定不穩(wěn)定的排序算法的排序算法簡單選擇排序是否是簡單選擇排序是否是穩(wěn)穩(wěn)定定的排序算法？的排序算法？1 1：設待排序的記錄為：設待排序的記錄為(20,16,13,14,19)(20,16,13,14,19)，經過下列過程將這些記，經過下列過程將這些記錄排序。錄排序。20,16,13,14,1920,16,13,14,1916,20,13,14,1916,20,13,14,1913,16,20,14,1913,16,20,1

42、4,1913,14,16,20,1913,14,16,20,1913,14,16,19,2013,14,16,19,20所用的排序方法是所用的排序方法是 。A. A. 直接插入排序直接插入排序B. B. 簡單選擇排序簡單選擇排序 C. C. 希爾排序希爾排序2 2。設待排序的記錄為。設待排序的記錄為(20,16,13,14,19)(20,16,13,14,19)，經過下列過程將這些記，經過下列過程將這些記錄排序。錄排序。13,16,20,14,1913,16,20,14,1913,14,20,16,1913,14,20,16,1913,14,16,20,1913,14,16,20,1913,1

43、4,16,19,2013,14,16,19,20所用的排序方法是所用的排序方法是 。A. A. 直接插入排序直接插入排序B. B. 簡單選擇排序簡單選擇排序C. C. 希爾排序希爾排序四、選擇排序2. 2. 堆排序堆排序1) 1) 堆堆設有序列設有序列 k k1 1,k,k2 2, ,k,kn n ，若滿足：，若滿足： ），（或212212221niiiiiiiikkkkkkkk則稱該序列構成的則稱該序列構成的完全二叉樹完全二叉樹是一個是一個堆堆。 o 例，將序列：例，將序列： 96，83，27，38，11，9 構成一棵完全二叉樹，構成一棵完全二叉樹，并判斷是否是堆。并判斷是否是堆。96832

44、738119它是一個堆。堆頂元素為所有元素中的它是一個堆。堆頂元素為所有元素中的最大值最大堆最大值最大堆給定序列如何構成完全二叉樹？給定序列如何構成完全二叉樹？滿足堆條件的完全二叉樹有何特點？滿足堆條件的完全二叉樹有何特點？練習：練習：1 1。下列關鍵字序列中，。下列關鍵字序列中， 是堆。是堆。. 16, 72, 31, 23, 94, 53 . 94, 23, 31, 72, 16, 53 . 16, 53, 23, 94，31, 72 . 16, 23, 53, 31, 94, 722. 堆排序2 2）堆的構造：）堆的構造： 由所給序列生成對應的完全二叉樹；由所給序列生成對應的完全二叉樹；

45、983273811序列：序列： 9，83，27，38，11 設完全二叉樹設完全二叉樹a1.na1.n中結點中結點akak的左右子樹均為堆，為的左右子樹均為堆，為構成以構成以akak為根結點的堆，需進行調整。方法是將為根結點的堆，需進行調整。方法是將akak的值的值與其左右子樹的根結點進行比較，若不滿足堆的條件，則與其左右子樹的根結點進行比較，若不滿足堆的條件，則將將akak與其左右子樹中根結點大的交換與其左右子樹中根結點大的交換，繼續(xù)進行比較，直到，繼續(xù)進行比較，直到所有子樹均滿足堆的定義為止。所有子樹均滿足堆的定義為止。2. 堆排序最大堆的向下調整算法最大堆的向下調整算法( (將大關鍵字移向

46、堆頂篩選算法將大關鍵字移向堆頂篩選算法) )Void Sieve(RECORDNODE a,int t,intVoid Sieve(RECORDNODE a,int t,int n) n)/ /* *將將at:nat:n建立為以建立為以atat為根的最大堆為根的最大堆* */ /intint i,j,k; i,j,k;i=t; j=2i=t; j=2* *i;a0=ai;/i;a0=ai;/* *aiai暫存到暫存到a0a0中中* */ /while(j=n)while(j=n)if(jn&aj.keyaj+1.key) j+;/if(jn&aj.keyaj+1.key) j+

47、;/* *選兩選兩子女的較大者子女的較大者* */ /if(a0.keyaj.key)if(a0.key=1;i-)for (i=p;i=1;i-)Sieve(a,i,n);Sieve(a,i,n);212525*4916081234564212525*16490813652例：序列：例：序列： 21，25，49，25*，16, 08，n=6,建建立初始的最大堆立初始的最大堆Sieve(a,3,6);Sieve(a,3,6);Sieve(a,2,6);Sieve(a,2,6);4212525*491608123564492525*210813652Sieve(a,1,6);Sieve(a,1,

48、6);練習：若一組記錄的排序碼為（練習：若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利），則利用堆排序的方法建立的初始堆為用堆排序的方法建立的初始堆為. 79, 46, 56, 38, 40, 84 . 84, 79, 56, 38, 40, 46 . 84, 79, 56, 46, 40, 38 . 84, 56, 79, 40, 46, 38 2. 堆排序3 3）堆排序）堆排序o 由以下兩個步驟進行：由以下兩個步驟進行： 由給定的無序序列構造最大堆；由給定的無序序列構造最大堆；最大堆堆頂最大堆堆頂a1a1具有最大的關鍵字具有最大的關鍵字, ,將將a1a1與與aa

49、n n 對調對調, ,把具有最大關鍵字的對象交換到最后把具有最大關鍵字的對象交換到最后, ,再對前面的再對前面的n n-1-1個對象個對象, ,使用堆的調整算法使用堆的調整算法Sieve(a,1,Sieve(a,1,n n-1),-1),重新建立最大堆重新建立最大堆, ,具有次具有次最大關鍵字的對象又上浮到最大關鍵字的對象又上浮到a1a1位置。位置。o 再對調再對調a1a1和和aan-1n-1,調用調用Sieve(a,1,Sieve(a,1,n n-2),-2),對前對前n n-2-2個對象個對象重新調整，重新調整，。o 如此反復執(zhí)行，最后得到全部排序好的對象序列。這個算法如此反復執(zhí)行，最后得

50、到全部排序好的對象序列。這個算法即堆排序算法。即堆排序算法。4925211608123456082525*162149136542例：序列：例：序列： 21，25，49，25*，16, 08，建立初始，建立初始的最大堆，并進行堆排序。的最大堆，并進行堆排序。2525*0821161234564081625*252113652 21，25，49，25*，16, 0825*1608211234564081625*211365221160812345608162113654231608124561365422. 堆排序堆排序的算法堆排序的算法Void HeapSort(RECORDNODE a,in

51、tVoid HeapSort(RECORDNODE a,int n) n)/ /* *使用堆排序算法對記錄數組使用堆排序算法對記錄數組a1:na1:n按關鍵字遞增排序按關鍵字遞增排序* */ /intint i; i;for(i=n/2;i=1;i-) Sieve(a,i,n);for(i=n/2;i=1;i-) Sieve(a,i,n);/ /* *建立初始最大堆建立初始最大堆* */ /for(i=n;i=2;i-)for(i=n;i=2;i-)a0=a1; a1=ai;ai=a0;a0=a1; a1=ai;ai=a0;/ /* *交換交換a1a1和和aiai* */ /Sieve(a,1

52、,i-1);Sieve(a,1,i-1);/ /* *重建最大堆重建最大堆* */ / 練習：給定序列練習：給定序列19,01,23,68,35,19*,84,27,14.給出堆排序給出堆排序的各次過程。的各次過程。19012368 35 19* 8427 1419012368 35 19* 8427 1484682327 35 19* 1901 1414682327 35 19* 190168352327 14 19* 190101352327 14 19* 1935272301 14 19* 1919272301 14 19*27192301 14 19*19*192301 1423191

53、9*01 14141919*0119*19140101191419011414011401結束。結束。排序結果排序結果01,14,19,19*,23,27,35,68,84初始序列初始序列19,01,23,68,35,19*,84,27,142. 堆排序4) 4) 算法分析算法分析o 若設堆中有若設堆中有 n n 個結點個結點, , 且且 2 2k k-1-1 n n 2 2k k, , 則對應的完全二叉樹則對應的完全二叉樹有有 k k 層。在第層。在第 i i 層上的結點數層上的結點數 2 2i-1 i-1 ( (i i = 1, 2, = 1, 2, , , k k) )。o 在第一個形成

54、初始堆的在第一個形成初始堆的 for for 循環(huán)中對每一個非葉結點調用了一次堆循環(huán)中對每一個非葉結點調用了一次堆調整算法調整算法Sieve( ),Sieve( ),因此該循環(huán)所用的計算時間為：因此該循環(huán)所用的計算時間為：112ki1- iik其中其中, , i i 是層序號是層序號, 2, 2i-1 i-1 是第是第 i i 層的最大結點數層的最大結點數, (, (k-ik-i) )是第是第 i i 層結點能夠移動的最大距離。層結點能夠移動的最大距離。njnjjikkjkjjjkkjjkki1- i2 2111111111122222)(Void HeapSort(RECORDNODE a,

55、intVoid HeapSort(RECORDNODE a,int n) n)intint i; i;for(i=n/2;i=1;i-) Sieve(a,i,n);for(i=n/2;i=1;i-) Sieve(a,i,n);for(i=n;i=2;i-)for(i=n;i=2;i-)a0=a1; a1=ai;ai=a0;a0=a1; a1=ai;ai=a0;Sieve(a,1,i-1);Sieve(a,1,i-1);因此形成初始堆的時間復雜度為因此形成初始堆的時間復雜度為O(n)2. 堆排序o 第二個第二個forfor循環(huán)中調用了循環(huán)中調用了n n-1-1次次Sieve( )Sieve( )

56、算法算法, , 該循環(huán)的該循環(huán)的計算時間為計算時間為O(O(n nloglog2 2n n) )。因此。因此, , 堆排序的時間復雜性堆排序的時間復雜性為為O(O(n nloglog2 2n n) )。o 該算法的附加存儲主要是在第二個該算法的附加存儲主要是在第二個forfor循環(huán)中用來執(zhí)行循環(huán)中用來執(zhí)行對象交換時所用的一個臨時對象。因此，該對象交換時所用的一個臨時對象。因此，該算法的空間算法的空間復雜性復雜性為為O(1)O(1)。o 堆排序是一個堆排序是一個不穩(wěn)定不穩(wěn)定的排序方法。的排序方法。Void HeapSort(RECORDNODE a,intVoid HeapSort(RECORD

57、NODE a,int n) n)intint i; i;for(i=n/2;i=1;i-) Sieve(a,i,n);for(i=n/2;i=1;i-) Sieve(a,i,n);for(i=n;i=2;i-)for(i=n;i=2;i-)a0=a1; a1=ai;ai=a0;a0=a1; a1=ai;ai=a0;Sieve(a,1,i-1);Sieve(a,1,i-1);1.1.從未排序序列中依次取出元素與已排序序列（初始時為空）從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，中的元素進行比較，將其放入已排序序列的正確位置上的方法，

58、稱為稱為. 希爾排序希爾排序 . 冒泡排序冒泡排序 . 插入排序插入排序 . 選擇排序選擇排序2從未排序序列中挑選元素，并將其依次插入已排序序列從未排序序列中挑選元素，并將其依次插入已排序序列（初始時為空）的一端的方法，稱為（初始時為空）的一端的方法，稱為. 希爾排序希爾排序 . 歸并排序歸并排序 . 插入排序插入排序 . 選擇排序選擇排序課堂練習：課堂練習：五、交換排序o 交換排序交換排序是根據序列中兩個結點關鍵字的比較結果，來對換是根據序列中兩個結點關鍵字的比較結果，來對換在序列中的位置。在序列中的位置?；舅枷牖舅枷胧莾蓛杀容^待排序對象的排序碼是兩兩比較待排序對象的排序碼, ,如發(fā)生逆

59、序如發(fā)生逆序( (即排列順序與排序后的次序正好相反即排列順序與排序后的次序正好相反) )，則交換，則交換之。直到所有對象都排好序為止。之。直到所有對象都排好序為止。o 算法的特點算法的特點是將關鍵字較大的結點向序列的尾部移動，關鍵是將關鍵字較大的結點向序列的尾部移動，關鍵字較小的結點向序列的前部移動字較小的結點向序列的前部移動五、交換排序1.1.冒泡排序冒泡排序1 1）過程：對無序表進行掃描，當發(fā)現相鄰兩個記錄關鍵字逆序時就進）過程：對無序表進行掃描，當發(fā)現相鄰兩個記錄關鍵字逆序時就進行交換，第一次掃描后就將最小關鍵字記錄像氣泡一樣逐漸上浮行交換，第一次掃描后就將最小關鍵字記錄像氣泡一樣逐漸上

60、浮頂部。然后對剩下的記錄再進行掃描，直到某次掃描時不發(fā)生交頂部。然后對剩下的記錄再進行掃描，直到某次掃描時不發(fā)生交換，則排序完成換，則排序完成。2)2)算法算法void BubbleSort(RECORDNODE a,intvoid BubbleSort(RECORDNODE a,int n) n)/ /* *使用冒泡排序算法，對記錄數組使用冒泡排序算法，對記錄數組a1:na1:n排序排序* */ /int i,j;intint i,j;int exchange = 1; exchange = 1; for(i=1;in & exchange;i+)for(i=1;ii;j-)for(j=n;ji;j-)if(aj-1.keyaj.key)if(aj-1.keyaj.ke