1、第 2 頁l排序排序(Sorting)：將一個數(shù)據元素（記錄）的將一個數(shù)據元素（記錄）的任意序列，重新排列成一個任意序列，重新排列成一個按關鍵字有序按關鍵字有序的的序列。序列。 設：設：R1，R2，R3，Rn 是是n個記錄，個記錄，k1，k2，k3，kn 為它們的關鍵字，排序就是為它們的關鍵字，排序就是將記錄按關鍵字將記錄按關鍵字遞增遞增（或（或遞減遞減）的次序排列）的次序排列起來。起來。l常見的排序結果常見的排序結果 遞遞 增：增：k ki i k ki+1i+1 遞遞 減：減：k ki i k ki+1i+1 非遞減：非遞減：k ki i k ki+1i+1 非遞增：非遞增：k ki i

2、k ki+1i+110.110.1 排序概述排序概述第 3 頁l排序的分類排序的分類按照排序記錄所在的位置劃分按照排序記錄所在的位置劃分 內部排序：內部排序：待排序記錄存放在計算機待排序記錄存放在計算機隨隨機存儲器中（內存）機存儲器中（內存）進行排序過程。進行排序過程。 外部排序：外部排序：待排序記錄數(shù)量很大，內存待排序記錄數(shù)量很大，內存無法一次容納全部記錄，在排序過程中無法一次容納全部記錄，在排序過程中尚需尚需對外存進行訪問對外存進行訪問的排序過程。的排序過程。10.110.1 排序概述排序概述第 4 頁無序序列區(qū)無序序列區(qū)l內部排序的分類：內部排序的分類：內部排序的過程就是一個內部排序的過

3、程就是一個逐步擴大逐步擴大記錄的記錄的有序序列長度的過程。有序序列長度的過程。10.110.1 排序概述排序概述按照逐步擴大的方式劃分：按照逐步擴大的方式劃分：插入排序插入排序：直接插入排序直接插入排序、折半插入排序、希爾、折半插入排序、希爾排序排序交換排序交換排序：冒泡排序冒泡排序、快速排序、快速排序選擇排序選擇排序：簡單選擇排序簡單選擇排序、堆排序、堆排序歸并排序歸并排序：2-路歸并排序路歸并排序基數(shù)排序基數(shù)排序：有序序列區(qū)有序序列區(qū)無序序列區(qū)無序序列區(qū)有序序列區(qū)有序序列區(qū)第 5 頁l內部排序的分類：內部排序的分類：按排序所需工作量劃分按排序所需工作量劃分 簡單的排序方法簡單的排序方法：T

4、(n)=O(n) 先進的排序方法先進的排序方法：T(n)=O(logn) 基數(shù)排序基數(shù)排序：T(n)=O(d.n)l排序排序的的基本操作基本操作：比較兩個關鍵字大小。比較兩個關鍵字大小。將記錄從一個位置移動到另一個位置。將記錄從一個位置移動到另一個位置。10.110.1 排序概述排序概述第 6 頁l待排序記錄的存儲方式：待排序記錄的存儲方式：1.地址連續(xù)的存儲單元地址連續(xù)的存儲單元：記錄的次序關系由：記錄的次序關系由其存儲位置決定（排序必須移動記錄）。其存儲位置決定（排序必須移動記錄）。2.靜態(tài)鏈表靜態(tài)鏈表：記錄的次序關系由指針指示：記錄的次序關系由指針指示（排序不必移動記錄）。（排序不必移動

5、記錄）。3.地址連續(xù)的存儲單元地址連續(xù)的存儲單元+指示位置的地址向指示位置的地址向量量：排序不移動記錄，排序后調整記錄。：排序不移動記錄，排序后調整記錄。10.110.1 排序概述排序概述第 7 頁#define MAXSIZE 20/ 順序表的最大長度順序表的最大長度typedef int KeyType； / 定義關鍵字類型定義關鍵字類型typedef struct KeyType key; / 關鍵字關鍵字 InfoType otherinfo; / 其他數(shù)據項其他數(shù)據項 RedType;/ 記錄類型記錄類型10.110.1 排序概述排序概述typedef struct typedef

6、struct RedType r MAXSIZE + 1 ; RedType r MAXSIZE + 1 ; / r0 / r0閑置或作哨兵閑置或作哨兵 int length;int length; SqList; SqList;第 8 頁l評價排序的性能評價排序的性能穩(wěn)定性穩(wěn)定性穩(wěn)定的排序方法：穩(wěn)定的排序方法：設在排序前的序列中記錄設在排序前的序列中記錄 Ri 領先于領先于 Rj（即（即 ij ），且），且 Ri、Rj 對應的對應的關鍵字為關鍵字為 Ki、Kj，如果，如果 KiKj 并且在排序并且在排序后的序列中后的序列中 Ri 仍領先于仍領先于 Rj，稱所用方法是，稱所用方法是穩(wěn)定的穩(wěn)定的

7、。不穩(wěn)定的排序方法：不穩(wěn)定的排序方法：排序后的序列中排序后的序列中Rj領先領先于于Ri。10.110.1 排序概述排序概述待排序列：待排序列：49,38,65,97,76,13,27,49 排序后排序后: 13,27,38,49,49,65,76,97 穩(wěn)定穩(wěn)定排序后排序后: 13,27,38,49,49,65,76,97 不穩(wěn)定不穩(wěn)定第 9 頁l直接插入排序直接插入排序是一種最簡單的排序方法。是一種最簡單的排序方法?；舅枷牖舅枷耄簩⒁粋€記錄插入到已排好序的：將一個記錄插入到已排好序的有序有序表表中，得到一個新的、記錄數(shù)增中，得到一個新的、記錄數(shù)增 1 的有序表。的有序表。整個排序過程為整

8、個排序過程為 n-1 趟插入趟插入排序：排序：即先將序列即先將序列中第中第 1 個記錄看成是一個個記錄看成是一個有序子序列有序子序列，然后，然后從第從第 2 個記錄開始，逐個進行插入，直至整個記錄開始，逐個進行插入，直至整個序列有序個序列有序。其中，一趟插入排序包括其中，一趟插入排序包括三個步驟三個步驟：10.2 10.2 插入排序插入排序直接插入排序直接插入排序第 10 頁l一趟插入排序過程：一趟插入排序過程：10.2 10.2 插入排序插入排序直接插入排序直接插入排序 前提：在插入第前提：在插入第 i（i1）個記錄時，前面的）個記錄時，前面的 i-1個記錄個記錄已經排好序已經排好序(非遞減

9、的序列非遞減的序列)。 1.查找插入位；查找插入位；2.后移插入位后的有序記錄；后移插入位后的有序記錄；3.插入。插入。 有序序列有序序列無序序列無序序列12i-1ini+112i-1ini+1第 11 頁 算法的實現(xiàn)算法的實現(xiàn)10.2 10.2 插入排序插入排序直接插入排序直接插入排序Status InsertSort ( SqList &L ) Status InsertSort ( SqList &L ) for( i=2; i=L.length; +i ) for( i=2; i=L.length; +i ) ifif ( ( LTLT( L.ri.key, L.ri-

10、1.key ) )( L.ri.key, L.ri-1.key ) ) L.r0.key = L.ri.key; L.r0.key = L.ri.key; /設置哨兵設置哨兵 for(j=i-1; for(j=i-1; LTLT(L.r0.key,L.rj.key); -j)(L.r0.key,L.rj.key); -j) L.rj+1 = L.rj; L.rj+1 = L.rj; /記錄后移記錄后移 L.rj+1 = L.r0; L.rj+1 = L.r0; /插入到正確位置插入到正確位置 /InsertSort/InsertSort第 12 頁l直接插入排序過程：直接插入排序過程：10.2

11、 10.2 插入排序插入排序直接插入排序直接插入排序L.r0L.r0 初始關鍵字初始關鍵字 ： （4949）38 65 97 76 13 27 4938 65 97 76 13 27 49i=2i=2： （3838）（）（38 4938 49）65 97 76 13 27 4965 97 76 13 27 49i=3i=3： （6565）（）（38 49 6538 49 65）97 76 13 27 4997 76 13 27 49i=4i=4： （9797）（）（38 49 65 9738 49 65 97）76 13 27 4976 13 27 49i=5i=5： （7676）（）（38

12、49 65 76 9738 49 65 76 97）13 27 4913 27 49i=6i=6： （1313）（）（13 38 49 65 76 9713 38 49 65 76 97）27 4927 49i=7i=7： （2727）（）（13 27 38 49 65 76 9713 27 38 49 65 76 97）4949i=8i=8： （4949）（）（13 27 48 49 49 65 76 9713 27 48 49 49 65 76 97）第 13 頁10.2 10.2 插入排序插入排序直接插入排序直接插入排序 直接插入排序算法性能分析直接插入排序算法性能分析 “移動移動”次數(shù)

13、次數(shù)= 0 “比較比較”次數(shù)次數(shù)= u最好的情況（正序序列）最好的情況（正序序列） “比較比較”次數(shù)次數(shù)= u最壞的情況（逆序序列）最壞的情況（逆序序列） u平均平均復雜度復雜度 O(n2) “移動移動”次數(shù)次數(shù)= n-11 ni=2i ni=22) 1)(2(-+=nn2+( i-1) ni=22(n+4)(n-1)=( i+1) ni=2第 14 頁 直接插入排序的特點直接插入排序的特點10.2 10.2 插入排序插入排序直接插入排序直接插入排序（1）若待排序記錄按關鍵碼）若待排序記錄按關鍵碼基本有序基本有序時，直時，直接插入排序的效率可以大大提高。接插入排序的效率可以大大提高。（2）由于

14、直接插入排序算法簡單，則在待排）由于直接插入排序算法簡單，則在待排序記錄數(shù)量序記錄數(shù)量n較小較小時效率也很高。時效率也很高。 第 15 頁如何改進直接插入排序如何改進直接插入排序?10.2 10.2 插入排序插入排序折半插入排序折半插入排序 在插入第在插入第 i（i1）個記錄時，前面的）個記錄時，前面的 i-1 個記錄已經排好序，在尋找插入位置時，可個記錄已經排好序，在尋找插入位置時，可以用以用折半查找來代替順序查找折半查找來代替順序查找，從而減少比，從而減少比較次數(shù)。較次數(shù)。折半插入排序基本思想折半插入排序基本思想： 用折半查找方法確定插入位置的排序。用折半查找方法確定插入位置的排序。第 1

15、6 頁10.2 10.2 插入排序插入排序折半插入排序折半插入排序例例i=1 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85 ) 20i=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20i=8 20 (6 13 30 39 42 70 85 ) 20i=8 20 (6 13 30 39 42 70 85 ) 20i=8 20 (6 13 20 30 39 42 70 85 )sjmjsmsj第 17

16、 頁l希爾排序基本思想：希爾排序基本思想： 將整個待排記錄序列分割成為若干將整個待排記錄序列分割成為若干子序列子序列分分別進行別進行直接插入排序直接插入排序，待整個序列中的記錄，待整個序列中的記錄“基本有序基本有序”時，再對全體記錄進行一次直接時，再對全體記錄進行一次直接插入排序。插入排序。 子序列子序列的構成不是簡單的的構成不是簡單的“逐段分割逐段分割”，而，而是將是將相隔某個相隔某個“增量增量”的記錄組成一個子序列。的記錄組成一個子序列。l分割待排序記錄的目的：分割待排序記錄的目的：減少待排序記錄個數(shù)；減少待排序記錄個數(shù)；使整個序列向基本有序發(fā)展。使整個序列向基本有序發(fā)展。10.2 10.

17、2 插入排序插入排序希爾排序希爾排序第 18 頁l例如，將例如，將n個記錄分割為個記錄分割為d個子序列。個子序列。R1, R1+d, R1+2d,R1+kdR2, R2+d, R2+2d,R2+kdRd, R2d, R3d,Rkd,R(k+1)d其中，增量其中，增量d的值在排序過程中的值在排序過程中從大到小逐從大到小逐漸減少漸減少，直到最后一次排序減為，直到最后一次排序減為1。10.2 10.2 插入排序插入排序希爾排序希爾排序第 19 頁l具體實現(xiàn)辦法具體實現(xiàn)辦法先取一個正整數(shù)先取一個正整數(shù) d1n，把所有相隔把所有相隔d1 的記錄放的記錄放一組，一組，組內進行直接插入排序組內進行直接插入排

18、序； 然后取然后取 d2=1; d=d/2) 以以d為增量，進行組內直接插入排序；為增量，進行組內直接插入排序；第 20 頁l希爾排序實例：希爾排序實例：假設：假設：d1=5，d2=3，d3=1。10.2 10.2 插入排序插入排序希爾排序希爾排序 初始關鍵字初始關鍵字 ： 49 38 65 97 76 13 27 49 38 65 97 76 13 27 4949 55 04 55 04 49 13 49 13 38 2738 27 65 65 4949 97 5597 55 76 0476 04一趟排序結果：一趟排序結果： 13 13 2727 4949 55 55 0404 49 49

19、3838 65 9765 97 76 76 13 13 5555 3838 7676 27 04 6527 04 65 4949 49 97 49 97二趟排序結果：二趟排序結果： 13 13 0404 4949 38 38 2727 4949 55 55 65 65 97 97 76 76三趟排序結果三趟排序結果: : 04 13 27 38 04 13 27 38 4949 49 55 65 76 97 49 55 65 76 97第 21 頁 由于在前兩趟的插入排序中，記錄的關由于在前兩趟的插入排序中，記錄的關鍵字是與同一子序列中的前一個記錄的關鍵鍵字是與同一子序列中的前一個記錄的關鍵字

20、進行比較，因此關鍵字較小的記錄不是一字進行比較，因此關鍵字較小的記錄不是一步一步的往前挪動，而是步一步的往前挪動，而是跳躍式跳躍式的往前移。的往前移。 在進行最后一趟增量為在進行最后一趟增量為 1 1 的插入排序的插入排序時，序列已基本有序，只要作記錄的少量比時，序列已基本有序，只要作記錄的少量比較和移動即可完成排序。因此較和移動即可完成排序。因此比直接插入排比直接插入排序快序快。 希爾排序算法是希爾排序算法是不穩(wěn)定不穩(wěn)定的排序算法。的排序算法。10.2 10.2 插入排序插入排序希爾排序希爾排序第 22 頁l交換排序的基本思想交換排序的基本思想 交換排序的主要操作是交換排序的主要操作是交換交

21、換。 在待排序列中選在待排序列中選兩個兩個記錄，將它們的關鍵記錄，將它們的關鍵字值相比較，如果字值相比較，如果反序反序（即排列順序與排序（即排列順序與排序后的次序正好相反），則后的次序正好相反），則交換交換它們的存儲位它們的存儲位置。置。10.3 10.3 交換排序交換排序起泡排序起泡排序反序則反序則 交換交換第 23 頁l起泡排序起泡排序兩兩比較兩兩比較相鄰相鄰記錄的關鍵碼，如果反序則交換，記錄的關鍵碼，如果反序則交換，直到沒有反序的記錄為止。直到沒有反序的記錄為止。 10.3 10.3 交換排序交換排序起泡排序起泡排序一趟起泡排序一趟起泡排序 無序序列無序序列R1.i有序序列有序序列 Ri

22、+1.n 例：例： 49 38 65 97 76 13 27 49 38 49 65 76 13 27 49 97第 24 頁l起泡排序起泡排序 兩兩比較兩兩比較相鄰相鄰記錄的關鍵碼，如果反序則記錄的關鍵碼，如果反序則交換，直到沒有反序的記錄為止。交換，直到沒有反序的記錄為止。 10.3 10.3 交換排序交換排序起泡排序起泡排序rj rj+1 ri+1 rn- -1 rn 無序區(qū)無序區(qū) 有序區(qū)有序區(qū) 1ji- -1 已經位于最終位置已經位于最終位置反序則交換反序則交換第 25 頁 將第將第1個記錄的關鍵字與第個記錄的關鍵字與第2個記錄的關鍵字進個記錄的關鍵字進行比較，若為逆序行比較，若為逆序

23、r1.keyr2.key，則交換；則交換； 然后比較第然后比較第2個記錄與第個記錄與第3個記錄；依次類推，個記錄；依次類推，直至第直至第 n-1 個記錄和第個記錄和第 n 個記錄比較為止個記錄比較為止第第一趟冒泡排序一趟冒泡排序，結果關鍵字，結果關鍵字最大最大的記錄被安置在的記錄被安置在最后一個最后一個（第（第n個）個）記錄上記錄上。 對前對前 n-1 個記錄進行個記錄進行第二趟冒泡排序第二趟冒泡排序，結果，結果使關鍵字次大的記錄被安置在第使關鍵字次大的記錄被安置在第n-1個記錄位置個記錄位置。 重復上述過程，直到重復上述過程，直到“在一趟排序過程中沒有在一趟排序過程中沒有進行過交換記錄的操作

24、進行過交換記錄的操作”為止為止。 一般：一般：n個記錄最多進行個記錄最多進行 n-1 趟冒泡排序。趟冒泡排序。10.3 10.3 交換排序交換排序起泡排序起泡排序第 26 頁例：例：10.3 10.3 交換排序交換排序起泡排序起泡排序初始關鍵字：初始關鍵字： 49 38 65 97 76 13 27 49 38 65 97 76 13 27 4949第一趟排序后：第一趟排序后：38 49 65 76 13 27 38 49 65 76 13 27 4949 9797第二趟排序后：第二趟排序后：38 49 65 13 27 38 49 65 13 27 4949 7676第三趟排序后：第三趟排序

25、后：38 49 13 27 38 49 13 27 4949 6565第四趟排序后：第四趟排序后：38 13 27 49 38 13 27 49 4949第五趟排序后：第五趟排序后：13 27 38 13 27 38 4949第六趟排序后：第六趟排序后：13 27 3813 27 38逐步有序逐步有序第 27 頁l快速排序快速排序在起泡排序中，記錄的比較和移動是在在起泡排序中，記錄的比較和移動是在相鄰相鄰單單元中進行的，記錄每次交換只能上移或下移元中進行的，記錄每次交換只能上移或下移一一個單元個單元，因而總的比較次數(shù)和移動次數(shù)較多。，因而總的比較次數(shù)和移動次數(shù)較多。10.3 10.3 交換排序

26、交換排序快速排序快速排序減少總的比較次數(shù)和移動次數(shù)減少總的比較次數(shù)和移動次數(shù)增大記錄的比較和移動距離增大記錄的比較和移動距離較大記錄從前面直接移動到后面較大記錄從前面直接移動到后面較小記錄從后面直接移動到前面較小記錄從后面直接移動到前面第 28 頁l 基本思想：基本思想：選定一記錄，以它的關鍵字作為選定一記錄，以它的關鍵字作為“樞軸樞軸”，關關鍵字小于鍵字小于樞軸樞軸的記錄移的記錄移至該記錄之前；關鍵字至該記錄之前；關鍵字大于大于樞軸樞軸的記錄的記錄移至該記錄之后。移至該記錄之后。記錄序列記錄序列 Rs.t 被分割成兩部分：被分割成兩部分：Rs.i-1和和 Ri+1.t；繼續(xù)；繼續(xù)對對R前后兩

27、部分記錄進行快前后兩部分記錄進行快速排序。速排序。10.3 10.3 交換排序交換排序快速排序快速排序無序序列無序序列一次劃分一次劃分樞軸樞軸無序子序列無序子序列1無序子序列無序子序列2快速排序快速排序快速排序快速排序第 29 頁l一趟快速排序具體算法：一趟快速排序具體算法：設兩個指針設兩個指針 low 和和 high，其初值分別指向，其初值分別指向數(shù)組的元素數(shù)組的元素1和元素和元素n。選第選第 1 個記錄為個記錄為樞軸樞軸，關鍵字為，關鍵字為pivotkey。將將 pivotkey 復制到復制到 r0 中，從中，從 high 所指所指的位置起的位置起 向前向前 搜索找到第一個關鍵字搜索找到第

28、一個關鍵字 小于小于pivotkey的記錄，復制到的記錄，復制到 low 所指位置中；然所指位置中；然后從后從 low 所指位置起所指位置起向后向后搜索，找到第一個關搜索，找到第一個關鍵字鍵字 大于大于 pivotkey的記錄，復制到的記錄，復制到high所指位所指位置中。置中。重復這兩步直到重復這兩步直到 lowhigh 為止。為止。10.3 10.3 交換排序交換排序快速排序快速排序第 30 頁l一趟快速排序算法一趟快速排序算法int Partition ( SqList &L, int low, int high ) L.r0 = L.rlow; pivotkey = L.rlo

29、w.key; while ( low high ) while ( low=pivotkey ) - high; L.rlow = L.rhigh; while ( lowhigh & L.rlow.key=pivotkey ) + low; L.rhigh = L.rlow; L.rlow = L.r0; / 樞軸樞軸記錄到位記錄到位 return low;/ 返回返回樞軸樞軸的位置的位置 / Partition10.3 10.3 交換排序交換排序快速排序快速排序第 31 頁l一趟快速排序的過程一趟快速排序的過程10.3 10.3 交換排序交換排序快速排序快速排序0 1 2 3 4

30、5 0 1 2 3 4 5 6 7 86 7 849493838656597977676131327274949初始關鍵字初始關鍵字pivotkey = 49pivotkey = 49lowlowhighhigh0 1 2 3 4 5 0 1 2 3 4 5 6 7 86 7 827273838656597977676131327274949第一次交換第一次交換lowlowhighhigh0 1 2 3 4 5 0 1 2 3 4 5 6 7 86 7 827273838656597977676131365654949第二次交換第二次交換lowlowhighhigh第 32 頁l一趟快速排序的

31、過程一趟快速排序的過程10.3 10.3 交換排序交換排序快速排序快速排序0 1 2 3 4 5 0 1 2 3 4 5 6 7 86 7 827273838131397977676131365654949第三次交換第三次交換lowlowhighhigh0 1 2 3 4 5 0 1 2 3 4 5 6 7 86 7 827273838131397977676979765654949第四次交換第四次交換lowlowhighhigh0 1 2 3 4 5 0 1 2 3 4 5 6 7 86 7 827273838131349497676979765654949第一趟完成第一趟完成lowlow

32、highhighpivotkey = 49pivotkey = 49子序列子序列1子序列子序列2第 33 頁l快速排序的過程快速排序的過程10.3 10.3 交換排序交換排序快速排序快速排序 初始狀態(tài)初始狀態(tài) 49 38 65 97 76 13 27 49 38 65 97 76 13 27 4949 一趟快速排序后一趟快速排序后 27 38 13 27 38 13 4949 76 97 65 76 97 65 4949 分別進行快速排序分別進行快速排序 13 13 2727 38 38 結束結束結束結束 4949 65 65 7676 97 97 4949 65 65 結束結束結束結束 有序

33、序列有序序列 13 27 38 49 13 27 38 49 4949 65 76 97 65 76 97 整個快速排序過整個快速排序過程可遞歸進行程可遞歸進行第 34 頁10.3 10.3 交換排序交換排序快速排序快速排序void void QSortQSort( SqList &L, int low, int high ) ( SqList &L, int low, int high ) /對表對表L L中的子序列中的子序列 L.rlowhigh L.rlowhigh 作快速排序作快速排序 ifif ( low high ) ( low high ) / / 長度大于長度大

34、于1 1 pivotloc = Partition( L, low, high ); pivotloc = Partition( L, low, high ); / / 將將 L.rlowhigh L.rlowhigh 一分為二一分為二 QSortQSort( L, low, pivotloc-1 );( L, low, pivotloc-1 ); / / 對低子表遞歸排序，對低子表遞歸排序，pivotlocpivotloc是界點位置是界點位置 QSortQSort( L, pivotloc+1, high ); ( L, pivotloc+1, high ); / / 對高子表對高子表 /Q

35、Sort/QSortvoid QuickSort( SqList &L ) void QuickSort( SqList &L ) /對順序表對順序表L L快速排序快速排序 QSortQSort( L, 1, L.length);( L, 1, L.length); /QuickSort/QuickSort第 35 頁10.3 10.3 交換排序交換排序快速排序快速排序l 快速排序特點快速排序特點:存儲結構：順序存儲結構：順序不穩(wěn)定不穩(wěn)定時間復雜度為時間復雜度為O( nlog2n );空間復雜度為空間復雜度為O( log2n ) 。 最壞情況：最壞情況：每次劃分選擇樞軸是最小或

36、最大元素每次劃分選擇樞軸是最小或最大元素 13 . 最好情況（每次劃分折半）：最好情況（每次劃分折半）： ., 49 第 36 頁10.4 10.4 選擇排序選擇排序l選擇排序基本思想選擇排序基本思想每趟排序在當前待排序序列中每趟排序在當前待排序序列中選擇選擇關鍵碼關鍵碼最小最小的記錄，添加到有序序列中。的記錄，添加到有序序列中。有序序列有序序列12i-1ink無序序列無序序列ni+112i-1ii交換交換最小記錄最小記錄第 37 頁10.4 10.4 選擇排序選擇排序簡單選擇排序簡單選擇排序 一趟簡單選擇排序：通過一趟簡單選擇排序：通過 n-i n-i 次關鍵字間次關鍵字間的比較，從的比較，

37、從 n-i+1n-i+1 個記錄中選出關鍵字最小的個記錄中選出關鍵字最小的記錄，并和第記錄，并和第 i i（1=i=n1=i=n）個記錄交換。）個記錄交換。void SelectSort( SqList &L )void SelectSort( SqList &L ) forfor( i=1; i L.length; +i ) ( i=1; i L.length; +i ) j = SelectMinKey( L, i ); j = SelectMinKey( L, i ); if ( i != j ) if ( i != j ) L.ri L.rj; L.ri L.rj; /

38、SelectSort/SelectSort 對于對于n n個關鍵字，要進行個關鍵字，要進行 n-1 n-1 趟選擇排序。趟選擇排序。第 38 頁10.4 10.4 選擇排序選擇排序簡單選擇排序簡單選擇排序例：例：初始：初始： 49 38 65 97 76 13 27 ji=11349一趟：一趟： 13 38 65 97 76 49 27 i=2j2738二趟：二趟： 13 27 65 97 76 49 38 三趟：三趟： 13 27 38 97 76 49 65 四趟：四趟： 13 27 38 49 76 97 65 五趟：五趟： 13 27 38 49 65 97 76 六趟：六趟： 13

39、27 38 49 65 76 97 排序結束：排序結束： 13 27 38 49 65 76 97第 39 頁10.4 10.4 選擇排序選擇排序簡單選擇排序簡單選擇排序l 簡單選擇排序算法的性能分析簡單選擇排序算法的性能分析最壞情況：最壞情況：3(n-1)次次移動次數(shù)：移動次數(shù)：最好情況（正序）：最好情況（正序）：0次次空間性能：空間性能：需要一個輔助空間。需要一個輔助空間。穩(wěn)定性：穩(wěn)定性：是一種是一種不穩(wěn)定不穩(wěn)定的排序算法。的排序算法。比較次數(shù)：比較次數(shù)：= =O O (n2)21n(n-1)= =n-1i=1 （n-i)n-i)簡單選擇排序的時間復雜度為簡單選擇排序的時間復雜度為O(n2

40、)。第 40 頁10.4 10.4 選擇排序選擇排序堆排序堆排序l 對簡單選擇排序算法的改進：對簡單選擇排序算法的改進： 改進的著眼點：改進的著眼點：如何如何減少減少關鍵碼之間的關鍵碼之間的比較比較次數(shù)次數(shù)。 核心思想：核心思想：充分利用每趟比較后的結果充分利用每趟比較后的結果。即。即在找出鍵值最小記錄的同時，也利用找出的鍵在找出鍵值最小記錄的同時，也利用找出的鍵值較小的記錄來減少后面選擇中所用的比較次值較小的記錄來減少后面選擇中所用的比較次數(shù)，從而提高整個排序過程的效率。數(shù)，從而提高整個排序過程的效率。減少關鍵碼間的比較次數(shù)減少關鍵碼間的比較次數(shù)查找最小值的同時，找出較小值查找最小值的同時，

41、找出較小值第 41 頁10.4 10.4 選擇排序選擇排序堆排序堆排序例：樹型選擇排序（錦標賽排序）例：樹型選擇排序（錦標賽排序）序列：序列：49，38，65，97，76，13，27，49133813381327654938657697132749時間復雜度：時間復雜度：O(nlog2n)；需要較多的；需要較多的輔助存儲空輔助存儲空間間；不穩(wěn)定不穩(wěn)定的排序。的排序。第 42 頁10.4 10.4 選擇排序選擇排序堆排序堆排序l 對簡單選擇排序算法的改進：對簡單選擇排序算法的改進：如何如何減少減少關鍵碼之間的關鍵碼之間的比較次數(shù)比較次數(shù)，同時，同時不不增加增加過多的輔助存儲的過多的輔助存儲的空間

42、空間。Robert.Floyd和和J.Williams在在1964年共同發(fā)年共同發(fā)明了明了堆排序算法堆排序算法( Heap Sort ) 。 利用前次比較的結果（較小值），減少利用前次比較的結果（較小值），減少了比較的次數(shù)；了比較的次數(shù)；只需一個輔助空間記錄大小。只需一個輔助空間記錄大小。 第 43 頁10.4 10.4 選擇排序選擇排序堆排序堆排序或或堆的定義堆的定義：n n個元素的序列個元素的序列 kk1 1,k,k2 2, ,k,kn n ，當，當且僅當滿足以下關系時，稱之為且僅當滿足以下關系時，稱之為堆堆： k ki i = k k2i2i k ki i = k k2i+12i+1 (

43、 i=1 ( i=1，2 2， n/2n/2) )kik2ik2i+1第 44 頁10.4 10.4 選擇排序選擇排序堆排序堆排序l若序列若序列 k1，k2，kn 是堆，則是堆，則堆頂元素堆頂元素必為序列中必為序列中 n 個元素的個元素的最小值（或最大值）最小值（或最大值）。l把把堆序列看成完全二叉樹堆序列看成完全二叉樹，則，則堆頂元素堆頂元素（完全二叉（完全二叉樹的根）必為序列中樹的根）必為序列中 n 個元素的個元素的最小值或最大值最小值或最大值。并且，由堆序列形成的完全二叉樹中所有非終端結并且，由堆序列形成的完全二叉樹中所有非終端結點的值均不大于（或不小于）其左、右孩子結點的點的值均不大于

44、（或不小于）其左、右孩子結點的值。值。小根堆：最小堆小根堆：最小堆大根堆：最大堆大根堆：最大堆分類分類第 45 頁10.4 10.4 選擇排序選擇排序堆排序堆排序 堆序列的實例：堆序列的實例：96969 91111838327272 23 31 14 45 5121247478585919136362424535330306 62 27 73 31 18 84 45 5堆序列：堆序列：96,83,27,11,9堆序列：堆序列：12,36,24,85,47,30,53,91第 46 頁10.4 10.4 選擇排序選擇排序堆排序堆排序l 堆的存儲堆的存儲: :將堆用順序存儲結構來存儲，則堆對應一組

45、序列。將堆用順序存儲結構來存儲，則堆對應一組序列。50 38 45 32 36 40 28 20 18 281 2 3 4 5 6 7 8 9 10采用順序存儲采用順序存儲第 47 頁10.4 10.4 選擇排序選擇排序堆排序堆排序l 堆排序堆排序: :利用堆的特性進行排序。利用堆的特性進行排序?；舅枷耄夯舅枷耄菏紫葘⒋判虻挠涗浶蛄袠嬙斐梢皇紫葘⒋判虻挠涗浶蛄袠嬙斐梢粋€堆；然后，選出堆中所有記錄的個堆；然后，選出堆中所有記錄的最小者最小者；再；再把它從堆中移走，并把剩余的記錄再調整成堆，把它從堆中移走，并把剩余的記錄再調整成堆，這樣又找出了這樣又找出了次小次小的記錄。以此類推，直到堆的

46、記錄。以此類推，直到堆中只有一個記錄。中只有一個記錄。 l 需解決的關鍵問題需解決的關鍵問題? ? 如何由一個無序序列建成一個堆（即初始建堆）？如何由一個無序序列建成一個堆（即初始建堆）？ 如何處理堆頂記錄？如何處理堆頂記錄？ 如何調整剩余記錄，成為一個新堆（即重建堆）？如何調整剩余記錄，成為一個新堆（即重建堆）？ 第 48 頁10.4 10.4 選擇排序選擇排序堆排序堆排序131376765050979738382727494965656 62 27 73 31 18 84 45 5用堆中最后一用堆中最后一個元素替代根個元素替代根76765050979738382727494965656 6

47、2 27 73 31 14 45 576765050272738389797494965656 62 27 73 31 14 45 576765050272738384949979765656 62 27 73 31 14 45 57676979750504949383865656 62 23 31 14 45 5 輸出堆頂元素之后，以堆中輸出堆頂元素之后，以堆中最后一個元素替代最后一個元素替代堆堆頂元素；然后將頂元素；然后將根結點根結點值與值與左左、右子樹的根結點右子樹的根結點值進值進行比較，并與其中行比較，并與其中小小者進行交換；重復上述操作，直者進行交換；重復上述操作，直至葉子結點，將得

48、到新的堆，稱這個從堆頂至葉子的至葉子結點，將得到新的堆，稱這個從堆頂至葉子的調整過程為調整過程為“篩選篩選”。進行進行篩選篩選繼續(xù)繼續(xù)篩選篩選輸出輸出堆頂堆頂?shù)?49 頁10.4 10.4 選擇排序選擇排序堆排序堆排序273849657650979727384965765013輸出：輸出：132749389765765013輸出：輸出：139749382765765013輸出：輸出：13 273849502765769713輸出：輸出：13 276549502738769713輸出：輸出：13 27 38第 50 頁10.4 10.4 選擇排序選擇排序堆排序堆排序496550273876971

49、3輸出：輸出：13 27 387665502738499713輸出：輸出：13 27 38 495065762738499713輸出：輸出：13 27 38 499765762738495013輸出：輸出：13 27 38 49 506597762738495013輸出：輸出：13 27 38 49 509765762738495013輸出：輸出：13 27 38 49 50 65第 51 頁10.4 10.4 選擇排序選擇排序堆排序堆排序7665972738495013輸出：輸出：13 27 38 49 50 659765762738495013輸出：輸出：13 27 38 49 50 65

50、 769765762738495013輸出：輸出：13 27 38 49 50 65 76 97第 52 頁10.4 10.4 選擇排序選擇排序堆排序堆排序 從一個無序序列建堆的過程是一個反復從一個無序序列建堆的過程是一個反復“篩選篩選”的過程。的過程。 若將此序列看成是一個完全二叉樹，則最若將此序列看成是一個完全二叉樹，則最后一個非終端結點是第后一個非終端結點是第 n/2n/2個元素，由此個元素，由此篩選只需從第篩選只需從第 n/2n/2個元素開始。個元素開始。時間復雜度時間復雜度：最壞的情況最壞的情況O（nlog2n）接近于平均情況。接近于平均情況。不穩(wěn)定不穩(wěn)定的排序。的排序。第 53 頁

51、10.5 10.5 歸并排序歸并排序l歸并的思想：歸并的思想： 將兩個或兩個以上的有序表將兩個或兩個以上的有序表合并合并成一個新成一個新的有序表。的有序表。l2-2-路歸并排序的核心思想路歸并排序的核心思想：設初始序列含有設初始序列含有n n個記錄，則可看成個記錄，則可看成 n n 個有序的子序列，每個子序列長度為個有序的子序列，每個子序列長度為1 1。兩兩合并兩兩合并，得到，得到 n/2n/2 個長度為個長度為 2 2 或或1 1的有序子序列的有序子序列。再兩兩合并，再兩兩合并，如此重復，直至得到如此重復，直至得到一個長度為一個長度為 n n 的有序序列為止的有序序列為止。第 54 頁10.

52、5 10.5 歸并排序歸并排序例：例：初始關鍵字：初始關鍵字： 49 38 65 97 76 13 27一趟歸并后：一趟歸并后： 38 49 65 97 13 76 27二趟歸并后：二趟歸并后： 38 49 65 97 13 27 76三趟歸并后：三趟歸并后： 13 27 38 49 65 76 97第 55 頁10.6 10.6 基數(shù)排序基數(shù)排序l基數(shù)排序思想：基數(shù)排序思想：借助借助多關鍵字排序多關鍵字排序的方法對的方法對單邏輯關鍵字單邏輯關鍵字排排序。序。l設設n個記錄的序列個記錄的序列R1, R2, . Rn，且每個記，且每個記錄錄Ri都包含都包含d位關鍵字（位關鍵字（ k1, k2,

53、kd）。對）。對此序列排序，保證任意此序列排序，保證任意Ri Rj滿足下列關系滿足下列關系： R( k1, k2, kd)i R( k1, k2, kd)jl基數(shù)排序分類：基數(shù)排序分類：最高位優(yōu)先（最高位優(yōu)先（MSD）最低位優(yōu)先（最低位優(yōu)先（LSD）第 56 頁10.6 10.6 基數(shù)排序基數(shù)排序例：對例：對52張撲克牌排序張撲克牌排序 l排序方法排序方法l先按花色分類，再按面值分類先按花色分類，再按面值分類l先按面值分類，再按花色分類先按面值分類，再按花色分類第 57 頁10.6 10.6 基數(shù)排序基數(shù)排序l最高位優(yōu)先最高位優(yōu)先按花色（最高位）分堆按花色（最高位）分堆梅花：梅花：13 張張方

54、塊：方塊：13 張張紅桃：紅桃：13 張張黑桃：黑桃：13 張張 每一堆按面值從小到大排列每一堆按面值從小到大排列 第 58 頁10.6 10.6 基數(shù)排序基數(shù)排序l最低位優(yōu)先最低位優(yōu)先分配（按面值）分配（按面值） 收集（按面值有序）收集（按面值有序）2：4張，張，3：4張，張，4：4張張 A：4張張第 59 頁10.6 10.6 基數(shù)排序基數(shù)排序再分配（按花色）再分配（按花色） 再收集（按花色有序，同花色按面值有序）再收集（按花色有序，同花色按面值有序） 梅花：梅花：13張，張， 方塊：方塊：13張，張， 紅桃：紅桃：13張，張， 黑桃：黑桃：13張張第 60 頁10.6 10.6 基數(shù)排序基數(shù)排序Initial list：46 91 85 15 92 35