1、1主要內容29.1 9.1 排序的基本概念排序的基本概念9.2 9.2 插入排序插入排序9.3 9.3 交換排序交換排序9.4 9.4 選擇排序選擇排序9.5 9.5 歸并排序歸并排序9.6 9.6 分配排序分配排序9.7 9.7 性能比較性能比較 選擇排序的主要操作是選擇，其主要思想是：每趟排序在當前待排序序列中選出關鍵碼最小的記錄，添加到有序序列中。 有序序列有序序列1 12 2i i-1-1i in nk k無序序列無序序列n ni+i+1 11 12 2i i-1-1i ii i交換交換最小記錄最小記錄9.4 9.4 選擇排序選擇排序常用的選擇排序算法：常用的選擇排序算法： （1 1）

2、直接選擇排序）直接選擇排序 （2 2）堆排序）堆排序39.4.1 9.4.1 直接選擇排序直接選擇排序41 1、基本思想、基本思想 每經過一趟比較就找出一個最小值，與待排序列最前面的每經過一趟比較就找出一個最小值，與待排序列最前面的位置互換位置互換. . 2 2、優點：、優點：實現簡單實現簡單3 3、缺點：、缺點：每趟只能確定一個元素，表長為每趟只能確定一個元素，表長為n n時需要時需要n-1n-1趟趟 4 4、前提：、前提：順序存儲結構順序存儲結構 9.4 9.4 選擇排序選擇排序50 1 2 3 4 5最小者最小者5、直接選擇排序的過程直接選擇排序的過程9.4.1 9.4.1 直接選擇排序

3、直接選擇排序6最小者最小者0 1 2 3 4 5結果結果各趟排序后的結果各趟排序后的結果9.4.1 9.4.1 直接選擇排序直接選擇排序解決方法：解決方法： 設置一個整型變量設置一個整型變量indexindex，用于記錄在一趟比較的用于記錄在一趟比較的過程中關鍵碼最小的記錄位置。過程中關鍵碼最小的記錄位置。 如何在無序區中記錄關鍵碼最小的記錄？如何在無序區中記錄關鍵碼最小的記錄？indexindexindexindex indexindex需解決的關鍵問題需解決的關鍵問題? ?79.4.1 9.4.1 直接選擇排序直接選擇排序解決方法： 第i趟簡單選擇排序的待排序區間是ri rn，則ri是無序

4、區第一個記錄，所以，將index所記載的關鍵碼最小的記錄與ri交換。如何確定最小記錄交換后的最終位置？如何確定最小記錄交換后的最終位置？需解決的關鍵問題需解決的關鍵問題? ?89.4.1 9.4.1 直接選擇排序直接選擇排序97、直接選擇排序的算法直接選擇排序的算法void SelectSort ( elemtype L,int n ) for ( i = 1; i n; i+ ) /*總共進行n-1次排序*/ k = i; for ( j = i+1; j n; j+) /*在剩余記錄序列中選擇最小的記錄*/ if ( rj =1; i-); i=1; i-) HeapAdjust(r, i

5、, n) HeapAdjust(r, i, n) ;/;/將序列將序列rinrin建成堆建成堆 關鍵問題關鍵問題1 1：如何新建堆？如何新建堆？189.4.2 9.4.2 堆排序堆排序關鍵問題關鍵問題2 2：如何處理堆頂記錄？：如何處理堆頂記錄？49 25 21 25* 16 081 2 3 4 5 6對對應應交換交換08 25 21 25* 16 491 2 3 4 5 6對對應應123456123456199.4.2 9.4.2 堆排序堆排序算法描述：算法描述： r1rn-i+1; r1rn-i+1; 解決方法：解決方法： 第第 i i 次處理堆頂是將堆頂記錄次處理堆頂是將堆頂記錄r1r1

6、與序列中第與序列中第n-i+1n-i+1個記錄個記錄rn-i+1rn-i+1交換。交換。關鍵問題關鍵問題2 2：如何處理堆頂記錄？：如何處理堆頂記錄？209.4.2 9.4.2 堆排序堆排序關鍵問題關鍵問題3 3：怎樣將剩余記錄調整成一個新堆？怎樣將剩余記錄調整成一個新堆？21* *算法描述：算法描述：HeapAdjust(r, 1, n-i);解決方法：解決方法： 第第 i 次調整剩余記錄，此時，剩余記錄有次調整剩余記錄，此時，剩余記錄有n-i個，個，調整根結點至第調整根結點至第n-i個記錄。個記錄。9.4.2 9.4.2 堆排序堆排序例:對剛才建好的大根堆進行排序：22交換交換 1號與號與

7、 6 號記錄號記錄 r1 rn492525*21160812345649 25 21 25* 16 08初始最大堆初始最大堆1365429.4.2 9.4.2 堆排序堆排序2316 25* 21 08 25 49交換交換 1號與號與 5 號記錄號記錄從從 1 號到號到 5 號號 重新重新調整為最大堆調整為最大堆082525*21164912345613654225 25* 21 08 16 499.4.2 9.4.2 堆排序堆排序24交換交換 1 號與號與 4 號記錄號記錄從從 1號到號到 4號號 重新重新調整為最大堆調整為最大堆1234561365429.4.2 9.4.2 堆排序堆排序25

8、08 16 21 25* 25 49交換交換 1號與號與3 號記錄號記錄從從 1 號到號到 3號號 重新重新調整為最大堆調整為最大堆1234561365429.4.2 9.4.2 堆排序堆排序2608 16 21 25* 25 49交換交換 1 號與號與2 號記錄號記錄排序完畢。排序完畢。從從 1 號到號到 2 號號 重新重新調整為最大堆調整為最大堆1234561365429.4.2 9.4.2 堆排序堆排序void HeapSort(elemtype h,int n) / /* * 對順序表對順序表* *h h進行堆排序進行堆排序 * */ / for(i=n/2；i=1；i-) Heapa

9、djust(h，i，n)； for(i=n；i=2；i-) temp=h1; h1=hi； hi=temp; /* HeapSort */ 27/ /* *將將hi.nhi.n建成大頂堆建成大頂堆 * */ / /* * 堆頂與堆底元素交換堆頂與堆底元素交換 * */ / /* *對對h1.i-1h1.i-1重新調整為堆重新調整為堆* */ /Heapadjust(h，1，i-1)；堆排序算法堆排序算法9.4.2 9.4.2 堆排序堆排序28void Heapajust(elemtype r，int s，int m) /* 對rs進行調整使其成為大頂堆 */ temp=rs；child=2*s

10、；/*temp暫存rs值，child是其左孩子*/ while(child=m) /*檢查是否到達當前堆尾，未到尾則整理*/ if(childm&rchild=rchild) break;/*根大則不必調整，函數結束*/ else /*否則子女中的大者上移*/ s=child； /*將根下降到子女位置并繼續向下整理！*/ rs=temp； /直到自下而上都滿足堆定義，再放置入口結點針對結點針對結點 s 的堆調整函數的堆調整函數HeapAdjust ： 從結點從結點s開始到開始到當前堆尾當前堆尾m為止，自上向下比較，如果子女的為止，自上向下比較，如果子女的值大于雙親結點的值，則互相交換，

11、即把局部調整為大根堆。值大于雙親結點的值，則互相交換，即把局部調整為大根堆。rs=rchild；child=child*2;9.4.2 9.4.2 堆排序堆排序練習：練習：已知序列503，87，512，61，908，170，897，275，653，462，寫出采用堆排序法對該序列作升序排列的第一趟結果。29第一趟結果：908,653,897,503,462,170,512,275,61,879.4.2 9.4.2 堆排序堆排序305、堆排序算法分析：、堆排序算法分析： 時間效率： O(nlog2n)。因為整個排序過程中需要調用n-1次堆頂點的調整，而每次堆排序算法本身耗時為log2n； 空間效

12、率：O(1)。僅在第二個for循環中交換記錄時用到一個臨時變量temp。 穩定性： 不穩定。 優點：對小文件效果不明顯，但對大文件有效。9.4.2 9.4.2 堆排序堆排序主要內容319.1 9.1 排序的基本概念排序的基本概念9.2 9.2 插入排序插入排序9.3 9.3 交換排序交換排序9.4 9.4 選擇排序選擇排序9.5 9.5 歸并排序歸并排序9.6 9.6 分配排序分配排序9.7 9.7 性能比較性能比較9.5 9.5 歸并排序歸并排序321、基本思想：將若干有序序列逐步歸并，最終得到一個有序序列。 （歸并排序主要是二路歸并排序）2、二路歸并排序：可以把一個長度為n 的無序序列看成

13、是 n 個長度為 1 的有序子序列 ，首先做兩兩歸并，得到 n / 2 個長度為 2 的有序子序列 ；再做兩兩歸并，如此重復，直到最后得到一個長度為 n 的有序序列。需解決的關鍵問題需解決的關鍵問題?如何將兩個有序序列合成一個有序序列？如何將兩個有序序列合成一個有序序列？怎樣完成一趟歸并？怎樣完成一趟歸并？如何控制二路歸并的結束？如何控制二路歸并的結束？33212525* 936272083716544921 2525* 4962 9308 7216 375416 37 5421 25 25* 4908 62 72 9308 21 25 25* 49 62 72 9308 16 21 25 2

14、5* 37 49 54 62 72 93len=1len=2len=4len=8len=1616 37 54整個歸并排序僅需整個歸并排序僅需 log2n 趟趟關鍵問題：關鍵問題：如何將兩個有序序列合成一個有序序列？如何將兩個有序序列合成一個有序序列？602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j609.5 9.5 歸并排序歸并排序34kkk在歸并過程中，可能會破壞原在歸并過程中，可能會破壞原來的有序序列，所以，將歸并來的有序序列，所以，將歸并的結果存入另外一個數組中。的結果存入另外一個數組中。 關鍵問題：關鍵問題：如何將

15、兩個有序序列合成一個有序序列？如何將兩個有序序列合成一個有序序列？602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j609.5 9.5 歸并排序歸并排序3536算法思想（以升序為例）：先用兩個指針分別指向兩個序列的第一個數據元素，進行比較，取出較小者，然后將其所在序列的指針后移，重復以上過程，直到指針達到序列的末尾，這時將另一個序列的剩余元素依次順序放到有序序列的后面即可。關鍵問題：關鍵問題：如何將兩個有序序列合成一個有序序列？如何將兩個有序序列合成一個有序序列？s m m+1 t r s t r1 ijk9.5 9.5 歸

16、并排序歸并排序37具體步驟：將兩個有序序列rs.m和rm+1.t歸并為有序序列r1s.t的過程： i=s；j=m+1；k=s； 若im 或 jt，執行(4)； 比較ri和rj關鍵字,將較小的存入r1中: 如果ri rj； r1k=ri；i+； k+；執行； 否則，r1k=rj; j+; k+;執行； 將尚未處理完的子表中元素存入r1； 如果i=m，將rim存入r1kt； 如果j=t，將rjt存入r1kt； 合并結束。9.5 9.5 歸并排序歸并排序void Merge (int r , int r1 , int s, int m, int t ) i=s; j=m+1; k=s; while

17、(i=m & j=t) if (ri=rj) else while (i=m) /收尾處理收尾處理 r1k+=ri+; /前一個子序列前一個子序列 while (j=t) r1k+=rj+; /后一個子序列后一個子序列 算法描述：算法描述：r1k=ri；i+；k+; r1k=rj；j+；k+;9.5 9.5 歸并排序歸并排序38關鍵問題：關鍵問題：如何將兩個有序序列合成一個有序序列？如何將兩個有序序列合成一個有序序列？602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60子序列的長度一定相等嗎子序列的長度一定相等嗎?

18、9.5 9.5 歸并排序歸并排序39關鍵問題：關鍵問題：怎樣完成一趟歸并？怎樣完成一趟歸并？602031544556520 605 3144 556560 20 31 5 44 55 65 5 20 31 60 44 55 65在一趟歸并中，除最后一個有序序列外，其它有序在一趟歸并中，除最后一個有序序列外，其它有序序列中記錄的個數相同，用長度序列中記錄的個數相同，用長度h表示。表示。9.5 9.5 歸并排序歸并排序40關鍵問題：關鍵問題：怎樣完成一趟歸并？怎樣完成一趟歸并？現在的任務是把若干個長度為現在的任務是把若干個長度為h的有序序列和最后一個長的有序序列和最后一個長度有可能小于度有可能小于

19、h的有序序列歸并，設的有序序列歸并，設i指向待歸并序列的指向待歸并序列的第一個記錄，有三種情況：第一個記錄，有三種情況：若若in-2h+1，則相鄰兩個有序表的長度均為則相鄰兩個有序表的長度均為h，執行執行一次歸并，完成后一次歸并，完成后i加加2h，準備進行下一次歸并；準備進行下一次歸并；20 605 3144 5565 70ihi=1n-2h+1=5n-2h+1算法描述：算法描述：while (in-2h+1) Merge (r, r1, i, i+h-1, i+2*h-1); i+=2*h;9.5 9.5 歸并排序歸并排序41若若in-h+1，則表示仍有兩個相鄰有序表，一個長則表示仍有兩個相

20、鄰有序表，一個長度為度為h，另一個長度小于另一個長度小于h，則執行兩個有序表的歸并，則執行兩個有序表的歸并，完成后退出一趟歸并。完成后退出一趟歸并。20 605 3144 5565ihi=5n-2h+1=4n-h+1=6n-2h+1n-h+1=n-h+1) for (k=i; k=n; k+) r1k=rk; 9.5 9.5 歸并排序歸并排序43void MergePass (int r , int r1 , int n, int h)/對r做一趟歸并，結果存入r1 i=1; while (in-2h+1) /長度均為h的區間合并 Merge (r, r1, i, i+h-1, i+2*h-1

21、); i+=2*h; if (in-h+1) /長度不相等的區間合并 Merge (r, r1, i, i+h-1, n); else for (k=i; k=n; k+) /只有一個區間 r1k=rk;一趟歸并排序算法一趟歸并排序算法9.5 9.5 歸并排序歸并排序44解決方法：解決方法： 開始時，有序序列的長度開始時，有序序列的長度h=1，結束時，有序序結束時，有序序列的長度列的長度h=n，用有序序列的長度來控制排序的結束。用有序序列的長度來控制排序的結束。關鍵問題：關鍵問題：如何控制二路歸并的結束？如何控制二路歸并的結束？9.5 9.5 歸并排序歸并排序45算法描述：void Merge

22、Sort (int r , int r1 , int n ) h=1; while (hn) MergePass (r, r1, n, h); /一次合并 h=2*h; /區間擴大 MergePass (r1, r, n, h); /再次合并 h=2*h; 關鍵問題：關鍵問題：如何控制二路歸并的結束？如何控制二路歸并的結束？9.5 9.5 歸并排序歸并排序46二路歸并排序算法的性能分析二路歸并排序算法的性能分析時間性能：時間性能： 二路歸并排序的時間復雜度等于歸并趟數與每一趟時間復雜度的乘積。而歸并趟數為log2n。每一趟歸并就是將兩兩有序子區間合并成一個有序子區間，而每一對有序子區間歸并時，

23、記錄的比較次數均小于等于記錄的移動次數，而記錄的移動次數等于數組中記錄的個數n，即每一趟歸并的時間復雜度為O(n)。因此，二路歸并排序的時間復雜度為O(nlog2n)。空間性能：空間性能： 算法在執行時，需要占用與原始記錄序列同樣數量的存儲空間，因此空間復雜度為O(n)。穩定性：穩定性： 穩定9.5 9.5 歸并排序歸并排序47練習：一組記錄的排序碼為（25，48，16，35，79，82，23，40，36，72）,其中含有5個長度為2的有序表，按歸并排序的方法對該序列進行一趟歸并后的結果為（ ）.48（16 25 35 48 23 40 79 82 36 72）9.5 9.5 歸并排序歸并排序

24、主要內容499.1 9.1 排序的基本概念排序的基本概念9.2 9.2 插入排序插入排序9.3 9.3 交換排序交換排序9.4 9.4 選擇排序選擇排序9.5 9.5 歸并排序歸并排序9.6 9.6 分配排序分配排序9.7 9.7 性能比較性能比較1. 1. 什么是什么是“多關鍵字多關鍵字”排序？實現方法？排序？實現方法？例1：對一副撲克牌該如何排序？ 若規定花色和面值的順序關系為： 花色： 面值：2 3 4 5 6 7 8 9 10 J Q K A 可以先按花色排序，花色相同者再按面值排序； 也可以先按面值排序，面值相同者再按花色排序。多關鍵字排序的實現方法通常有兩種： 最高位優先法MSD

25、(Most Significant Digit first) 最低位優先法LSD (Least Significant Digit first)509.6.1 9.6.1 多關鍵字排序多關鍵字排序51因為有分組，故此算法需遞歸實現。例：初始關鍵字序列T=（32, 13, 27, 32*, 19，33），請分別用MSD和LSD進行排序，并討論其優缺點。法法1（MSD）：）：原始序列：32, 13, 27, 32*, 19， 33 先按高位Ki1 排序：（13, 19）, 27, （32, 32*，33） 再按低位Ki2 排序 ： 13, 19 ， 27, 32, 32*, 33法法2（LSD）：

26、）： 原始序列： 32, 13, 27, 32*, 19 ，33 先按低位Ki2排序： 32, 32*, 13, 33, 27, 19 再按高位Ki1排序： 13, 19 , 27, 32, 32*, 33無需分組，易編程實現！9.6.1 9.6.1 多關鍵字排序多關鍵字排序52 設n 個記錄的序列為：V0, V1, , Vn-1 ，可以把每個記錄Vi 的單關鍵碼 Ki 看成是一個d元組（Ki1, Ki2, , Kid），則其中的每一個分量Kij ( 1 j d ) 也可看成是一個關鍵字。4注1： Ki1最高位，Kid最低位；Ki共有d位，可看成d元組；注2： 每個分量Kij (1 j d )

27、 有radix種取值，則稱radix為基數。26(9, 8, 4)(0, 1, , 9)（a, b, , z）(d, i, a, n)310例1：關鍵碼984可以看成是 元組；基數radix 為 。例2：關鍵碼dian可以看成是 元組；基數radix 為 。u相關概念：9.6.1 9.6.1 多關鍵字排序多關鍵字排序53例：T=（02，77，70，54，64，21，55，11），用LSD排序。分析：各關鍵字可視為2元組；每位的取值范圍是：0-9；即基數radix 10 。因此，特設置10個隊列，并編號為0-9。1155216454707702原始序列12345678先對低位掃描出隊012345

28、678910個隊列1、計算機怎樣實現LSD算法？分配過程收集過程下一步775564540211217012345678出隊后序列775554，64217002，119.6.2 基數排序540123456789再次入隊再次出隊再對高位掃描小結：小結：排序時經過了反復的“分配”和“收集”過程。當對關鍵字所有的位進行掃描排序后，整個序列便從無序變為有序了。775564540211217012345678出隊后序列706454211102再次分配再次收集7770645554211102再次出隊后序列這種LSD排序方法稱為：基數排序基數排序，77，55 基數排序不需要進行排序碼的比較，它采用“分配”與“

29、收集”的辦法，是一種借助多關鍵碼排序的思想實現單關鍵字排序的方法。即：用關鍵字不同的位值進行排序。552、基數排序的基本思想9.6.2 基數排序563、基數排序算法的實現思路 設待排序的數據元素關鍵字是m位d進制整數（不足 m位的關鍵字在高位補0），設置d個隊列，令其編號分別為0,1,2,d-1。（1）按關鍵字最低位的數值依次把各數據元素放到相應的隊列中；（2）按照隊列號從小到大和進入隊列中數據元素的先后次序收集分配在各隊列中的數據元素；這樣，就形成了數據元素集合的一個新的排列，稱這樣的一次排序過程為一次基數排序。（3）再對得到的數據元素序列按關鍵字次低位的數值依次把各數據元素放到相應的隊列中

30、，重復收集過程，當完成了第m次基數排序后，就得到了排好序的數據元素序列。9.6.2 基數排序57用鏈隊列來實現基數排序鏈式基數排序實現思路：實現思路： 針對 d 元組中的每一位分量，把原始鏈表中的所有記錄, 按Kij的取值， j = d, d-1, , 1， 先“分配”到radix個鏈隊列中去； 然后再按各鏈隊列的順序，依次把記錄從鏈隊列中“收集”起來； 分別用這種“分配”、“收集”的運算逐趟進行排序； 在最后一趟“分配”、“收集” 完成后，所有記錄就按其關鍵碼的值從小到大排好序了。3、基數排序算法的實現思路9.6.2 基數排序 例：請實現以下關鍵字序列的鏈式基數排序：T=（614，738，9

31、21，485，637， 101，215，530，790，306）614921485637738101215530790306第一趟分配第一趟分配e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9原始序列靜態鏈表：r0（從最低位 i = 3開始排序，f 是隊首指針，e 為隊尾指針）第一趟收集第一趟收集（讓隊尾指針ei 鏈接到下一非空隊首指針fi+1 即可）530790921101614485215306637738r05859第一趟收集的結果：第一趟收集的結果：e0 e1

32、 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9第二趟分配第二趟分配（按次低位 i = 2 ）530790921101614485215306637738第二趟收集第二趟收集（讓隊尾指針ei 鏈接到下一非空隊首指針fi+1 ）530790921101614485215306637738r0r060第二趟收集的結果：第二趟收集的結果：530790921101614485215306637738e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637

33、101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9第三趟分配（按最高位第三趟分配（按最高位 i = 1 ）第三趟收集第三趟收集（讓隊尾指針ei 鏈接到下一非空隊首指針fi+1 ）530790921101614485215306637738r0r0排序結束！時間復雜度：時間復雜度：若每個關鍵碼有d 位，需要重復執行d 趟“分配”與“收集”。每趟對 n 個對象進行“分配”，對radix個隊列進行“收集”。總時間復雜度為O(d*n)。空間復雜度：空間復雜度：算法中需要d次使用n個結點臨時存放n個數據元素，所以空間復雜度為O（n）。穩定性：穩定性：基數排序是穩定的排序方法。9.6.3 基數排序算法分析61主要內容629.1 9.1 排序的基本概念排序的基本概念9.2 9.2 插入排序插入排序9.3 9.