1、單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級1數 據 結 構主講人：主講人： 張立震張立震e-mail: 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級2打撲克例例 子子單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級3世界杯比賽排名阿根廷阿根廷法國法國阿根廷阿根廷意大利意大

2、利法國法國意大利意大利法國法國英國英國中國中國巴西巴西巴西巴西阿根廷阿根廷西班牙西班牙葡萄牙葡萄牙阿根廷阿根廷例例 子子單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級4數據結構期末成績排名例例 子子單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式第二級第二級第三級第三級第四級第四級第五級第五級510.1 概述概述10.2 插入排序插入排序 (直接插入、折半插入、希爾排序直接插入、折半插入、希爾排序)10.3 交換排序交換排序 (冒泡排序、快

3、速排序冒泡排序、快速排序)10.4 選擇排序選擇排序 (簡單選擇、樹形選擇、堆排序簡單選擇、樹形選擇、堆排序)10.5 歸并排序歸并排序 10.6 基數排序基數排序10.7 各種排序小結各種排序小結單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級6：整理文件中的記錄，使之按：整理文件中的記錄，使之按關鍵字關鍵字遞增遞增 (或遞減或遞減) 次序排列起來。次序排列起來。：以數據對象的多個屬性域中的一個為：以數據對象的多個屬性域中的一個為 排序依據，該屬性域即為關鍵字。排序依據，該屬性域即為關鍵

4、字。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級7內部排序內部排序 外部排序外部排序 將欲處理的數據整個存放到內部存將欲處理的數據整個存放到內部存儲器中排序，數據可被隨機存取儲器中排序，數據可被隨機存取 交換式排序交換式排序 選擇式排序選擇式排序 插入式排序插入式排序 由于排序期間數據太多，需要借助外部由于排序期間數據太多，需要借助外部的輔助存儲器，不斷在內、外存只見移的輔助存儲器，不斷在內、外存只見移動的排序，數據不可隨機存取動的排序，數據不可隨機存取 排序的分類排序的分類歸并排序歸

5、并排序 基數排序基數排序 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級8排序算法衡量標準排序算法衡量標準穩定性穩定性 不穩定性不穩定性 排序過后能使值相同的數據保持排序過后能使值相同的數據保持原順序中的相對位置原順序中的相對位置 排序過后不能使值相同的數據排序過后不能使值相同的數據保持原順序中的相對位置保持原順序中的相對位置 u時間復雜度時間復雜度（最好情況和最壞情況）（最好情況和最壞情況）u空間復雜度空間復雜度u穩定性穩定性排序的時間開銷可用算法執行中的數排序的時間開銷可用算法執行中

6、的數據據比較次數比較次數與數據與數據移動次數移動次數來衡量。來衡量。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級9 本教材定義的待排數據表類型本教材定義的待排數據表類型 typedef struct KeyType key; /關鍵字項關鍵字項 InfoType otherinfo; /其他數據項其他數據項 RedType; typedef struct RedType rMAXSIZE+1; /r0閑置或作哨兵閑置或作哨兵 int length; SqList;單擊此處編輯母版標題樣

7、式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級10 直接插入排序直接插入排序 (Insert Sort) 折半插入排序折半插入排序 (Binary Insert Sort) 2-路插入排序（略）路插入排序（略） 表插入排序（略）表插入排序（略） 希爾排序希爾排序 (Shell Sort)基本思想基本思想 每步將一個待排序的對象，按其排序碼大小，每步將一個待排序的對象，按其排序碼大小， 插入插入到前面到前面已經排好序已經排好序的一組對象的適當位置上，的一組對象的適當位置上，直到對象全部插入為止。直到對象全部插入

8、為止。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級11基本思想基本思想：順序地把待排序的數據元素按其值的大小插順序地把待排序的數據元素按其值的大小插入到已排序數據元素子集合的適當位置。入到已排序數據元素子集合的適當位置。有序序列有序序列無序序列無序序列1. 直接插入排序直接插入排序(Insert Sort)12578630941256783094單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級

9、第五級第五級12基本思想基本思想：順序地把待排序的數據元素按其值的大小插順序地把待排序的數據元素按其值的大小插入到已排序數據元素子集合的適當位置。入到已排序數據元素子集合的適當位置。1. 直接插入排序直接插入排序(Insert Sort)p 當插入第當插入第i (i 1) 個對象時，前面的個對象時，前面的r1, , ri-1已經已經排好序。這時，用排好序。這時，用ri的排序碼與的排序碼與ri-1, ri-2, 的排序的排序碼順序進行比較，找到插入位置即將碼順序進行比較，找到插入位置即將Vi插入，原來位插入，原來位置上的對象向后順移。置上的對象向后順移。p 子集合的數據元素個數從只有一個數據元素

10、開始逐次子集合的數據元素個數從只有一個數據元素開始逐次增大。增大。p 當子集合大小最終和集合大小相同時排序完畢。當子集合大小最終和集合大小相同時排序完畢。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級1364 7896468989646464直接插入排序直接插入排序 6478962458962457624572456567246489578924初始序列初始序列:第第1趟排序趟排序:第第2趟排序趟排序:第第3趟排序趟排序:第第4趟排序趟排序:第第5趟排序趟排序:jjjj6Temp 6單擊

11、此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級14 直接插入排序的算法直接插入排序的算法 (p265算法算法10.1) void InsertSort(SqList &L) int i, j; for ( i=2; i=L.length; +i ) if ( LT(L.ri.key, L.ri-1.key) ) / 時，需將時，需將L.ri插入有序子表插入有序子表 L.r0 = L.ri; / L.r0為監視哨為監視哨 for ( j=i-1; LT(L.r0.key,L.rj.ke

12、y); -j ) L.rj+1 = L.rj; / 記錄后移記錄后移 L.rj+1 = L.r0; / 插入到正確位置插入到正確位置 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級15最壞最壞情況下情況下 最好最好情況下情況下比較次數：比較次數：n-1移動次數：移動次數：0算法分析算法分析比較次數：比較次數：移動次數：移動次數：2) 1)(2(2- -+ += = = =nnini2) 1)(4(1- -+ += =+ + nnin2= =i）（正序）（正序） （逆序）（逆序） 直接插入

13、排序的時間復雜度為直接插入排序的時間復雜度為O(n2)。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級16空間性能：空間性能：需要一個記錄的輔助空間（監視哨）。需要一個記錄的輔助空間（監視哨）。穩定性：穩定性：直接插入排序算法是一種直接插入排序算法是一種穩定穩定的排序算法。的排序算法。特點：特點：簡單、容易實現，適用于待排序記錄簡單、容易實現，適用于待排序記錄基本有基本有 序序或待排序記錄或待排序記錄較小較小時。時。算法分析算法分析單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此

14、處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級17246457624576489896第第2趟排序趟排序:第第3趟排序趟排序:temp 62. 折半插入折半插入(Binary Insert Sort) 基本思想基本思想：在查找插入位置時，使用折半查找算法。：在查找插入位置時，使用折半查找算法。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級18642. 折半插入折半插入(Binary Insert Sort) 基本思想基本思想：在查找插入

15、位置時，使用折半查找算法。：在查找插入位置時，使用折半查找算法。57624576489896第第2趟排序趟排序:第第3趟排序趟排序:temp 689647low6mhigh單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級19void BInsertSort ( SqList &L ) int i, j, high, low, m; for (i=2; i=L.length; +i) L.r0 = L.ri; / 將將L.ri暫存到暫存到L.r0 low = 1; high = i-

16、1; while (low=high+1; -j) L.rj+1 = L.rj; / 記錄后移記錄后移 L.rhigh+1 = L.r0; / 插入插入 / BInsertSort折半插入排序算法折半插入排序算法單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級20時間性能分析：時間性能分析： 移動次數與直接插入排序相同移動次數與直接插入排序相同 比較次數與初始順序無關，只依賴于記錄個數比較次數與初始順序無關，只依賴于記錄個數 插入每個記錄需要插入每個記錄需要log2 i次比較次比較 時間復

17、雜度為時間復雜度為O(n2)。空間代價空間代價: 與直接插入排序相同與直接插入排序相同穩定性穩定性: 穩定穩定算法分析算法分析單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級21 基本思想基本思想：把待排序的數據元素把待排序的數據元素分成若干個小組分成若干個小組，對，對同一小組內的數據元素用直接插入法排序；同一小組內的數據元素用直接插入法排序；小組的個數小組的個數逐次縮小逐次縮小；當完成了所有數據元素都在一個組內的排序；當完成了所有數據元素都在一個組內的排序后排序過程結束。希爾排序又稱作縮

18、小增量排序。后排序過程結束。希爾排序又稱作縮小增量排序。3. 希爾排序希爾排序(Shell Sort) 開始時開始時 gap（間隔值）（間隔值） 的值較大，子序列中的對象較的值較大，子序列中的對象較少，排序速度較快；隨著排序進展，少，排序速度較快；隨著排序進展，gap 值逐漸變小，值逐漸變小，子序列中對象個數逐漸變多，由于前面工作的基礎，子序列中對象個數逐漸變多，由于前面工作的基礎，大多數對象已基本有序，所以排序速度仍然很快。大多數對象已基本有序，所以排序速度仍然很快。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級

19、 第四級第四級 第五級第五級22希爾排序過程希爾排序過程6565 343425258787 121238385656 464614147777 92922323565665651414252577778787383823235656343414147777121223236565464625258787929238386565777712123434565612121414656534342323777746462525878792923838121214142323252534343838464656566565777787879292結果序列結果序列gap=6gap=3gap=1單擊此處編

20、輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級23void ShellInsert(SqList &L, int gap) / 對順序表對順序表L作一趟希爾插入排序。本算法對算法作一趟希爾插入排序。本算法對算法10.1作了以下修改：作了以下修改： / 1. 前后記錄位置的增量是前后記錄位置的增量是gap，而不是，而不是1； / 2. r0只是暫存單元，不是哨兵。當只是暫存單元，不是哨兵。當j=0時，插入位置已找到。時，插入位置已找到。 int i, j; for (i=gap+1; i0

21、& LT(L.r0.key, L.rj.key); j-=gap) L.rj+gap = L.rj; / 記錄后移，查找插入位置記錄后移，查找插入位置 L.rj+gap = L.r0; / 插入插入 / ShellInsert希爾排序的算法希爾排序的算法 (算法算法10.4)單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級24void ShellSort ( SqList &L, int dlta, int t ) / 按增量序列按增量序列dlta0.t-1對順序表對順序表

22、L作希爾排序。作希爾排序。 for (int k=0; k= 2; -i ) for ( j=1; j L. rj+1. key ) ElemType temp=L.rj; / 交換交換 L.rj=L.rj+1; L.rj+1=temp; 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級30問題：剛才的改進算法是否已經最優問題：剛才的改進算法是否已經最優?冒泡排序的冒泡排序的改進改進算法算法1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7

23、8 9 1 2 3 4 5 6 7 8 9 如何解決呢？如何解決呢？單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級31 冒泡排序的冒泡排序的改進改進算法算法void BubbleSort ( SqList &L ) for (i=n, Change =TRUE; i = 2 &Change; -i ) Change = FALSE; for ( j=1; j L. rj+1. key ) ElemType temp=L.rj; L.rj=L.rj+1; L.rj+1=te

24、mp; Change=TRUE; 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級32最壞情況（逆序）：最壞情況（逆序）：最好情況（正序）：最好情況（正序）：比較次數：比較次數：n-1移動次數：移動次數：0 比較次數：比較次數：移動次數：移動次數：2) 1(1- -= = = =nn(n-i)n-1i2) 1(1- -= = = =n3n3(n-i)n-1i算法分析算法分析 n 時間復雜度為時間復雜度為O(n2)n 穩定性：穩定性：穩定穩定單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式

25、單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級33基本思想基本思想：任取待排序對象序列中的某個對象（例如取任取待排序對象序列中的某個對象（例如取第一個對象）作為第一個對象）作為樞軸樞軸(pivot)，按照該對象的關鍵字大小，按照該對象的關鍵字大小，將整個對象序列劃分為，將整個對象序列劃分為左右兩個子序列左右兩個子序列：2. 快速排序快速排序(Quick Sort)u左側左側子序列中所有對象的關鍵字都子序列中所有對象的關鍵字都小于小于樞軸對象的樞軸對象的關鍵字。關鍵字。u右側右側子序列中所有對象的關鍵字都子序列中所有對象的關鍵字都大于或等

26、于大于或等于樞軸樞軸對象的關鍵字。對象的關鍵字。樞軸對象則排在這兩個子序列中間樞軸對象則排在這兩個子序列中間(這也是該對象最終應安這也是該對象最終應安放的位置放的位置)。然后分別對這兩個子序列重復施行上述方法，。然后分別對這兩個子序列重復施行上述方法，直到所有的對象都排在相應位置上為止。直到所有的對象都排在相應位置上為止。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級34一趟快速排序的具體過程一趟快速排序的具體過程49 38 65 97 76 13 27 49pivot=49lowhig

27、h27low65high13low97highhigh49第一趟結果：第一趟結果： 27 38 13 49 76 97 65 49 小于小于49大于等于大于等于49單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級35快速排序每一趟的劃分快速排序每一趟的劃分 int Partition ( SqList &L, int low, int high ) /* 交換順序表交換順序表L中子表中子表r low high 的記錄，樞軸記錄到位，并的記錄，樞軸記錄到位，并返回其所在返回其所在 的

28、位置，此時在它之前（后）的記錄均不大（小）于它的位置，此時在它之前（后）的記錄均不大（小）于它 */ / Partition 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級36快速排序每一趟的劃分快速排序每一趟的劃分 int Partition ( SqList &L, int low, int high ) /* 交換順序表交換順序表L中子表中子表r low high 的記錄，樞軸記錄的記錄，樞軸記錄到位，并返回其所在到位，并返回其所在 的位置，此時在它之前（后）的記的位置，此

29、時在它之前（后）的記錄均不大（小）于它錄均不大（小）于它 */ L. r0=L. rlow; / 用子表的第一個記錄作樞軸記錄用子表的第一個記錄作樞軸記錄 int pivotkey = L. rlow. key; / 樞軸記錄關鍵字樞軸記錄關鍵字 / Partition 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級37快速排序每一趟的劃分快速排序每一趟的劃分 int Partition ( SqList &L, int low, int high ) /* 交換順序表交換順序表

30、L中子表中子表r low high 的記錄，樞軸記錄到位，并返的記錄，樞軸記錄到位，并返回其所在回其所在 的位置，此時在它之前（后）的記錄均不大（小）于它的位置，此時在它之前（后）的記錄均不大（小）于它 */ L. r0=L. rlow; / 用子表的第一個記錄作樞軸記錄用子表的第一個記錄作樞軸記錄 int pivotkey = L. rlow. key; / 樞軸記錄關鍵字樞軸記錄關鍵字 while ( low high ) / Partition 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第

31、五級第五級38快速排序每一趟的劃分快速排序每一趟的劃分 int Partition ( SqList &L, int low, int high ) /* 交換順序表交換順序表L中子表中子表r low high 的記錄，樞軸記錄到位，并返的記錄，樞軸記錄到位，并返回其所在回其所在 的位置，此時在它之前（后）的記錄均不大（小）于它的位置，此時在它之前（后）的記錄均不大（小）于它 */ L. r0=L. rlow; / 用子表的第一個記錄作樞軸記錄用子表的第一個記錄作樞軸記錄 int pivotkey = L. rlow. key; / 樞軸記錄關鍵字樞軸記錄關鍵字 while ( low

32、 high ) L. rlow=L. r0; / 樞軸記錄到位樞軸記錄到位 return low; / 返回樞軸位置返回樞軸位置 / Partition 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級39快速排序每一趟的劃分快速排序每一趟的劃分 int Partition ( SqList &L, int low, int high ) /* 交換順序表交換順序表L中子表中子表r low high 的記錄，樞軸記錄到位，并返回其所在的記錄，樞軸記錄到位，并返回其所在 的位置，此時

33、在它之前（后）的記錄均不大（小）于它的位置，此時在它之前（后）的記錄均不大（小）于它 */ L. r0=L. rlow; / 用子表的第一個記錄作樞軸記錄用子表的第一個記錄作樞軸記錄 int pivotkey = L. rlow. key; / 樞軸記錄關鍵字樞軸記錄關鍵字 while ( low high ) while ( low=pivotkey ) -high; L. rlow=L. r0; / 樞軸記錄到位樞軸記錄到位 return low; / 返回樞軸位置返回樞軸位置 / Partition 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母

34、版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級40快速排序每一趟的劃分快速排序每一趟的劃分 int Partition ( SqList &L, int low, int high ) /* 交換順序表交換順序表L中子表中子表r low high 的記錄，樞軸記錄到位，并返回其所在的記錄，樞軸記錄到位，并返回其所在 的位置，此時在它之前（后）的記錄均不大（小）于它的位置，此時在它之前（后）的記錄均不大（小）于它 */ L. r0=L. rlow; / 用子表的第一個記錄作樞軸記錄用子表的第一個記錄作樞軸記錄 int pivotkey = L. rlow. key;

35、/ 樞軸記錄關鍵字樞軸記錄關鍵字 while ( low high ) while ( low=pivotkey ) -high; L. rlow = L. rhigh; / 將比樞軸記錄小的記錄移到低端將比樞軸記錄小的記錄移到低端 L. rlow=L. r0; / 樞軸記錄到位樞軸記錄到位 return low; / 返回樞軸位置返回樞軸位置 / Partition 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級41快速排序每一趟的劃分快速排序每一趟的劃分 int Partition

36、( SqList &L, int low, int high ) /* 交換順序表交換順序表L中子表中子表r low high 的記錄，樞軸記錄到位，并返回其所在的記錄，樞軸記錄到位，并返回其所在 的位置，此時在它之前（后）的記錄均不大（小）于它的位置，此時在它之前（后）的記錄均不大（小）于它 */ L. r0=L. rlow; / 用子表的第一個記錄作樞軸記錄用子表的第一個記錄作樞軸記錄 int pivotkey = L. rlow. key; / 樞軸記錄關鍵字樞軸記錄關鍵字 while ( low high ) while ( low=pivotkey ) -high; L. r

37、low = L. rhigh; / 將比樞軸記錄小的記錄移到低端將比樞軸記錄小的記錄移到低端 while ( low high & L. rlow. key = pivotkey ) +low; L.rhigh = L.rlow; / 將比樞軸記錄大的記錄移到高端將比樞軸記錄大的記錄移到高端 L. rlow=L. r0; / 樞軸記錄到位樞軸記錄到位 return low; / 返回樞軸位置返回樞軸位置 / Partition 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級42快

38、速排序算法快速排序算法void QSort ( SqList &L, int low, int high ) / 對順序表對順序表L中的子序列中的子序列L. rlowhigh作快速排序作快速排序 if ( low high ) / 長度大于長度大于1 pivotloc=Partition (L, low, high); / 將將L.rlow.high一分為二一分為二 QSort ( L, low, pivotloc-1 ); / 對低子表遞歸排序對低子表遞歸排序 QSort(L,pivotloc+1,high); / 對高子表遞歸排序對高子表遞歸排序 / QSort單擊此處編輯母版標題

39、樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級43算法分析算法分析n最理想的情況：每次劃分對一個對象定位后，該對象最理想的情況：每次劃分對一個對象定位后，該對象的左側子序列與右側子序列的長度相同。的左側子序列與右側子序列的長度相同。n就就平均時間平均時間而言，快速排序是而言，快速排序是最好最好的一種內部排序方的一種內部排序方法。平均計算時間是法。平均計算時間是O(nlog2n)n最壞情況：初始關鍵字有序或基本有序。此時快速排最壞情況：初始關鍵字有序或基本有序。此時快速排序蛻化為冒泡排序，序蛻化為冒泡排序，時

40、間復雜度時間復雜度為為O(n2)。占用附加存。占用附加存儲儲(即棧即棧)將達到將達到O(n)。n快速排序是一種快速排序是一種不穩定不穩定的排序方法。的排序方法。n對于對于 n 較大的平均情況而言，快速排序是較大的平均情況而言，快速排序是“快速快速”的，的，但是當但是當 n 很小時，這種排序方法往往比其它簡單排序很小時，這種排序方法往往比其它簡單排序方法還要慢。方法還要慢。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級44 簡單選擇排序簡單選擇排序 (Simple Selection So

41、rt) 樹形選擇排序樹形選擇排序 (Tree Selection Sort) 堆排序堆排序 (Heap Sort)基本思想基本思想 每一趟每一趟 (例如第例如第 i 趟趟, i = 1, , n-1) 在后面在后面 n-i +1個待個待排序記錄中選出排序碼最小的記錄排序記錄中選出排序碼最小的記錄, 作為有序序列中的作為有序序列中的第第 i 個記錄。待到第個記錄。待到第n-1 趟作完趟作完, 待排序記錄只剩下待排序記錄只剩下1個個,就不用再選了。就不用再選了。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四

42、級 第五級第五級45基本思想基本思想：i 從從 1 開始，直到開始，直到 n-1，進行，進行 n-1 趟排序。第趟排序。第 i 趟的排序過程為：趟的排序過程為： 在一組對象在一組對象 rirn ( i = 1, 2, , n-1) 中選擇具有最小關鍵字的對象，并和第中選擇具有最小關鍵字的對象，并和第 i 個對象進行交個對象進行交換。換。1. 簡單選擇排序簡單選擇排序(Simple Selection Sort)單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級46一趟簡單選擇排序的過程一趟簡

43、單選擇排序的過程ki=1jkjjjjkjjk1349單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級47i=kjjjjjj1349k k2一趟簡單選擇排序的過程一趟簡單選擇排序的過程單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級48void SelectSort ( SqList & L) for ( int i = 1; i L.length; i+ ) k= Select

44、MinKey( L, i ); if (i!=k) ElemType temp=L.ri; L.ri=L.rk; L.rk=temp; int SelectMinKey (SqList & L, int i ) int m = i; for (j = i+1; j =L.length; j+) if (L.rj. key L.rm. key) m = j; /當前具最小關鍵碼的對象當前具最小關鍵碼的對象 return m;簡單選擇排序的算法簡單選擇排序的算法單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第

45、四級第四級 第五級第五級49最壞情況：最壞情況：算法分析算法分析移動次數：移動次數：最好情況：最好情況：比較次數：比較次數：)() 1(21211nOnninni= =- -= =- - - -= =）（l 時間復雜度為時間復雜度為O(n2)。l 穩定性：穩定性：不穩定不穩定 為什么？為什么？0次次3(n-1)次次單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級50世界杯比賽排名巴西巴西法國法國巴西巴西意大利意大利法國法國意大利意大利法國法國英國英國中國中國巴西巴西巴西巴西阿根廷阿根廷西班

46、牙西班牙葡萄牙葡萄牙阿根廷阿根廷8個國家參加世界杯，個國家參加世界杯，需要多少次比賽得出冠軍？需要多少次比賽得出冠軍？單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級51樹形選擇排序又稱為錦標賽排序。樹形選擇排序又稱為錦標賽排序。基本思想基本思想：與體育比賽時的淘汰賽類似。首先取得與體育比賽時的淘汰賽類似。首先取得 n 個個對象的關鍵碼，進行對象的關鍵碼，進行兩兩比較兩兩比較，得到，得到 n/2 個比較的個比較的優勝優勝者者(關鍵碼小者關鍵碼小者)，作為第一步比較的結果保留下來。然后，作為

47、第一步比較的結果保留下來。然后對這對這 n/2 個對象再進行關鍵碼的兩兩比較，個對象再進行關鍵碼的兩兩比較，如此重，如此重復，直到選出一個關鍵碼最小的對象。復，直到選出一個關鍵碼最小的對象。2. 樹形選擇排序樹形選擇排序(TreeSelection Sort)單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級52133813973865493876131327652749單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第

48、三級 第四級第四級 第五級第五級5313974938761365274938133865132727382738657627單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級542797493876136527493827386576271338384938657649單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級55p錦標賽排序構成的樹是錦標賽排序構成的樹是滿的完全二叉樹滿的完全二叉

49、樹，其深度為，其深度為 log2(2n-1)取上整，其中取上整，其中 n 為待排序元素個數。為待排序元素個數。p除第一次選擇具有最小關鍵字的對象需要進行除第一次選擇具有最小關鍵字的對象需要進行 n-1 次次關鍵字比較外，重構勝者樹選擇具有次小、再次小關關鍵字比較外，重構勝者樹選擇具有次小、再次小關鍵字對象所需的關鍵字比較次數均為鍵字對象所需的關鍵字比較次數均為 O(log2n)。總關總關鍵字比較次數為鍵字比較次數為O(nlog2n)。p對象的移動次數不超過關鍵字的比較次數，所以錦標對象的移動次數不超過關鍵字的比較次數，所以錦標賽排序賽排序總的時間復雜度總的時間復雜度為為O(nlog2n)。p這

50、種排序方法雖然減少了許多排序時間，但是這種排序方法雖然減少了許多排序時間，但是使用了使用了較多的附加存儲較多的附加存儲。p錦標賽排序是一個錦標賽排序是一個穩定穩定的排序方法。的排序方法。算法分析算法分析單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級563. 堆排序堆排序(Heap Sort)堆定義：堆定義：n 個元素的序列個元素的序列 k1, k2, , kn 當且僅當當且僅當滿足下列關系時，稱之為滿足下列關系時，稱之為堆堆。 kik2i kik2i ki k2i+1 ki k2i+1其

51、中，其中，i = 1, 2, , n/2.前者稱為前者稱為最小堆最小堆，后者稱為，后者稱為最大堆最大堆。或或單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級57最小堆與最大堆舉例最小堆與最大堆舉例9683273811091236248547913053最大堆最大堆最小堆最小堆單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級58基本思想基本思想：在輸出堆頂的最小值之后，使得剩余在輸出堆頂

52、的最小值之后，使得剩余n-1個元個元素的序列重又建成一個堆，則得到素的序列重又建成一個堆，則得到n個元素中的次小值。個元素中的次小值。反復執行，反復執行，直到直到得到一個有序序列。得到一個有序序列。堆排序分為兩個步驟：堆排序分為兩個步驟：u 根據初始輸入數據形成初始堆；根據初始輸入數據形成初始堆；u 通過一系列的對象交換和重新調整堆進行排序。通過一系列的對象交換和重新調整堆進行排序。3. 堆排序堆排序(Heap Sort)單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級59關鍵問題：關鍵問

53、題：如何由一個無序序列建成一個堆如何由一個無序序列建成一個堆? (1) 如何調整余下的元素成為一個新堆如何調整余下的元素成為一個新堆? 3. 堆排序堆排序(Heap Sort)單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級60堆調整過程堆調整過程1338277697654949rc=13單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級61123456136542堆調整堆調整單擊此處編

54、輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級62123456136542堆調整堆調整單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級63123456136542堆調整堆調整單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級64123456136542堆調整堆調整單擊此處編輯母版標題樣式單擊

55、此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級65123456136542堆調整堆調整單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級66123456136542建立初始的最大堆建立初始的最大堆單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級67123456136542建立初始的最大堆建立初始的最大堆單擊此

56、處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級68u最大堆的第一個對象最大堆的第一個對象r1具有最大的關鍵字，將具有最大的關鍵字，將r1與與rn對調，把具有最大關鍵字的對象交換到最后，對調，把具有最大關鍵字的對象交換到最后，再對前面的再對前面的n-1個對象，使用堆的調整算法個對象，使用堆的調整算法HeapAdjust(1, n-1)，重新建立最大堆。結果具有次，重新建立最大堆。結果具有次最大關鍵字的對象又上浮到堆頂，即最大關鍵字的對象又上浮到堆頂，即r1位置。位置。u再對調再對調r1和和rn-

57、1，調用，調用HeapAdjust (1, n-2)，對前，對前n-2個對象重新調整。個對象重新調整。u如此反復執行，最后得到全部排序好的對象序列。如此反復執行，最后得到全部排序好的對象序列。這個算法即堆排序算法。這個算法即堆排序算法。utypedef SqList HeapType; /順序存儲方式順序存儲方式基于初始堆進行堆排序基于初始堆進行堆排序單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級69void HeapAdjust(HeapType &H, int s, int

58、m) /調整調整H.rs的關鍵字，使的關鍵字，使H.rsm成為一個大頂堆成為一個大頂堆 ElemType rc=H.rs; for (int j=2*s; j=m; j*=2) /沿較大的孩子結點向下篩選沿較大的孩子結點向下篩選 if (j0; -i) / 把把H.r1.H.length建成大頂堆建成大頂堆 HeapAdjust ( H, i, H.length ); for (i=H.length; i1; -i) temp=H.ri; H.ri=H.r1; H.r1=temp; /* 將堆頂記錄和當前未經排序子序列將堆頂記錄和當前未經排序子序列Hr1.i中中 最后一個記錄相互交換最后一個記

59、錄相互交換 */ HeapAdjust (H, 1, i-1); / 將將H.r1.i-1 重新調整為大頂堆重新調整為大頂堆 / HeapSort堆排序算法堆排序算法單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級71算法分析算法分析p適宜記錄較多的文件適宜記錄較多的文件p在最壞的情況下，時間復雜度為在最壞的情況下，時間復雜度為O(nlog2n)p堆排序是一個堆排序是一個不穩定不穩定的排序方法。的排序方法。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編

60、輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級72基本思想基本思想 將一個具有將一個具有n個待排序記錄的序列看成是個待排序記錄的序列看成是 n 個長度個長度為為 1 的有序序列，然后進行的有序序列，然后進行兩兩歸并兩兩歸并，得到，得到 n/2 個長度個長度為為 2 的有序序列，再進行兩兩歸并，得到的有序序列，再進行兩兩歸并，得到 n/4 個長度為個長度為 4 的有序序列，的有序序列，直至得到一個長度為，直至得到一個長度為 n 的有序序的有序序列為止。列為止。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級73歸并排序過程歸并排序過程 (49) (38) (65) (97) (76) (13) (27)(38 49)(13 27