第10章排序(上課用)講述

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

2、利法國法國意大利意大利法國法國英國英國中國中國巴西巴西巴西巴西阿根廷阿根廷西班牙西班牙葡萄牙葡萄牙阿根廷阿根廷例例 子子單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級4數(shù)據(jù)結(jié)構(gòu)期末成績排名學(xué)號姓名成績1110810113劉德華981110810221陳鑫961110820109劉亦菲911110820104黃渤871110820116頊曉宇83例例 子子單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式第二級第二級第三級第三級第四級第四級第五

3、級第五級510.1 概述概述10.2 插入排序插入排序 (直接插入、折半插入、希爾排序直接插入、折半插入、希爾排序)10.3 交換排序交換排序 (冒泡排序、快速排序冒泡排序、快速排序)10.4 選擇排序選擇排序 (簡單選擇、樹形選擇、堆排序簡單選擇、樹形選擇、堆排序)10.5 歸并排序歸并排序 10.6 基數(shù)排序基數(shù)排序10.7 各種排序小結(jié)各種排序小結(jié)單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級6：整理文件中的記錄，使之按：整理文件中的記錄，使之按關(guān)鍵字關(guān)鍵字遞增遞增 (或遞減或遞減

4、) 次序排列起來。次序排列起來。：以數(shù)據(jù)對象的多個屬性域中的一個為：以數(shù)據(jù)對象的多個屬性域中的一個為 排序依據(jù)，該屬性域即為關(guān)鍵字。排序依據(jù)，該屬性域即為關(guān)鍵字。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級7內(nèi)部排序內(nèi)部排序 外部排序外部排序 將欲處理的數(shù)據(jù)整個存放到內(nèi)部存將欲處理的數(shù)據(jù)整個存放到內(nèi)部存儲器中排序，數(shù)據(jù)可被隨機存取儲器中排序，數(shù)據(jù)可被隨機存取 交換式排序交換式排序 選擇式排序選擇式排序 插入式排序插入式排序 由于排序期間數(shù)據(jù)太多，需要借助外部由于排序期間數(shù)據(jù)太多，需要借

5、助外部的輔助存儲器，不斷在內(nèi)、外存只見移的輔助存儲器，不斷在內(nèi)、外存只見移動的排序，數(shù)據(jù)不可隨機存取動的排序，數(shù)據(jù)不可隨機存取 排序的分類排序的分類歸并排序歸并排序 基數(shù)排序基數(shù)排序 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級8排序算法衡量標準排序算法衡量標準穩(wěn)定性穩(wěn)定性 不穩(wěn)定性不穩(wěn)定性 排序過后能使值相同的數(shù)據(jù)保持排序過后能使值相同的數(shù)據(jù)保持原順序中的相對位置原順序中的相對位置 排序過后不能使值相同的數(shù)據(jù)排序過后不能使值相同的數(shù)據(jù)保持原順序中的相對位置保持原順序中的相對位置 49

6、325649272732494956u時間復(fù)雜度時間復(fù)雜度（最好情況和最壞情況）（最好情況和最壞情況）u空間復(fù)雜度空間復(fù)雜度u穩(wěn)定性穩(wěn)定性排序的時間開銷可用算法執(zhí)行中的數(shù)排序的時間開銷可用算法執(zhí)行中的數(shù)據(jù)據(jù)比較次數(shù)比較次數(shù)與數(shù)據(jù)與數(shù)據(jù)移動次數(shù)移動次數(shù)來衡量。來衡量。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級9 本教材定義的待排數(shù)據(jù)表類型本教材定義的待排數(shù)據(jù)表類型 typedef struct KeyType key; /關(guān)鍵字項關(guān)鍵字項 InfoType otherinfo; /其他

7、數(shù)據(jù)項其他數(shù)據(jù)項 RedType; typedef struct RedType rMAXSIZE+1; /r0閑置或作哨兵閑置或作哨兵 int length; SqList;單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級10 直接插入排序直接插入排序 (Insert Sort) 折半插入排序折半插入排序 (Binary Insert Sort) 2-路插入排序（略）路插入排序（略） 表插入排序（略）表插入排序（略） 希爾排序希爾排序 (Shell Sort)基本思想基本思想 每步將一個

8、待排序的對象，按其排序碼大小，每步將一個待排序的對象，按其排序碼大小， 插入插入到前面到前面已經(jīng)排好序已經(jīng)排好序的一組對象的適當(dāng)位置上，的一組對象的適當(dāng)位置上，直到對象全部插入為止。直到對象全部插入為止。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級11基本思想基本思想：順序地把待排序的數(shù)據(jù)元素按其值的大小插順序地把待排序的數(shù)據(jù)元素按其值的大小插入到已排序數(shù)據(jù)元素子集合的適當(dāng)位置。入到已排序數(shù)據(jù)元素子集合的適當(dāng)位置。有序序列有序序列無序序列無序序列1. 直接插入排序直接插入排序(Inse

9、rt Sort)12578630941256783094單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級12基本思想基本思想：順序地把待排序的數(shù)據(jù)元素按其值的大小插順序地把待排序的數(shù)據(jù)元素按其值的大小插入到已排序數(shù)據(jù)元素子集合的適當(dāng)位置。入到已排序數(shù)據(jù)元素子集合的適當(dāng)位置。1. 直接插入排序直接插入排序(Insert Sort)p 當(dāng)插入第當(dāng)插入第i (i 1) 個對象時，前面的個對象時，前面的r1, , ri-1已經(jīng)已經(jīng)排好序。這時，用排好序。這時，用ri的排序碼與的排序碼與ri-1,

10、ri-2, 的排序的排序碼順序進行比較，找到插入位置即將碼順序進行比較，找到插入位置即將Vi插入，原來位插入，原來位置上的對象向后順移。置上的對象向后順移。p 子集合的數(shù)據(jù)元素個數(shù)從只有一個數(shù)據(jù)元素開始逐次子集合的數(shù)據(jù)元素個數(shù)從只有一個數(shù)據(jù)元素開始逐次增大。增大。p 當(dāng)子集合大小最終和集合大小相同時排序完畢。當(dāng)子集合大小最終和集合大小相同時排序完畢。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級1364 7896468989646464直接插入排序直接插入排序 6478962458962

11、457624572456567246489578924初始序列初始序列:第第1趟排序趟排序:第第2趟排序趟排序:第第3趟排序趟排序:第第4趟排序趟排序:第第5趟排序趟排序:jjjj6Temp 6單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級14 直接插入排序的算法直接插入排序的算法 (p265算法算法10.1) void InsertSort(SqList &L) int i, j; for ( i=2; i=L.length; +i ) if ( LT(L.ri.key, L.

12、ri-1.key) ) / 時，需將時，需將L.ri插入有序子表插入有序子表 L.r0 = L.ri; / L.r0為監(jiān)視哨為監(jiān)視哨 for ( j=i-1; LT(L.r0.key,L.rj.key); -j ) L.rj+1 = L.rj; / 記錄后移記錄后移 L.rj+1 = L.r0; / 插入到正確位置插入到正確位置 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級15最壞最壞情況下情況下 最好最好情況下情況下比較次數(shù)：比較次數(shù)：n-1移動次數(shù)：移動次數(shù)：0算法分析算法分析比較

13、次數(shù)：比較次數(shù)：移動次數(shù)：移動次數(shù)：2) 1)(2(2- -+ += = = =nnini2) 1)(4(1- -+ += =+ + nnin2= =i）（正序）（正序） （逆序）（逆序） 直接插入排序的時間復(fù)雜度為直接插入排序的時間復(fù)雜度為O(n2)。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級16空間性能：空間性能：需要一個記錄的輔助空間（監(jiān)視哨）。需要一個記錄的輔助空間（監(jiān)視哨）。穩(wěn)定性：穩(wěn)定性：直接插入排序算法是一種直接插入排序算法是一種穩(wěn)定穩(wěn)定的排序算法。的排序算法。特點：特

14、點：簡單、容易實現(xiàn)，適用于待排序記錄簡單、容易實現(xiàn)，適用于待排序記錄基本有基本有 序序或待排序記錄或待排序記錄較小較小時。時。算法分析算法分析單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級17246457624576489896第第2趟排序趟排序:第第3趟排序趟排序:temp 62. 折半插入折半插入(Binary Insert Sort) 基本思想基本思想：在查找插入位置時，使用折半查找算法。：在查找插入位置時，使用折半查找算法。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此

15、處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級18642. 折半插入折半插入(Binary Insert Sort) 基本思想基本思想：在查找插入位置時，使用折半查找算法。：在查找插入位置時，使用折半查找算法。57624576489896第第2趟排序趟排序:第第3趟排序趟排序:temp 689647low6mhigh單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級19void BInsertSort ( SqList &L ) i

16、nt i, j, high, low, m; for (i=2; i=L.length; +i) L.r0 = L.ri; / 將將L.ri暫存到暫存到L.r0 low = 1; high = i-1; while (low=high+1; -j) L.rj+1 = L.rj; / 記錄后移記錄后移 L.rhigh+1 = L.r0; / 插入插入 / BInsertSort折半插入排序算法折半插入排序算法單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級20時間性能分析：時間性能分析： 移

17、動次數(shù)與直接插入排序相同移動次數(shù)與直接插入排序相同 比較次數(shù)與初始順序無關(guān)，只依賴于記錄個數(shù)比較次數(shù)與初始順序無關(guān)，只依賴于記錄個數(shù) 插入每個記錄需要插入每個記錄需要log2 i次比較次比較 時間復(fù)雜度為時間復(fù)雜度為O(n2)。空間代價空間代價: 與直接插入排序相同與直接插入排序相同穩(wěn)定性穩(wěn)定性: 穩(wěn)定穩(wěn)定算法分析算法分析單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級21 基本思想基本思想：把待排序的數(shù)據(jù)元素把待排序的數(shù)據(jù)元素分成若干個小組分成若干個小組，對，對同一小組內(nèi)的數(shù)據(jù)元素用直接

18、插入法排序；同一小組內(nèi)的數(shù)據(jù)元素用直接插入法排序；小組的個數(shù)小組的個數(shù)逐次縮小逐次縮??；當(dāng)完成了所有數(shù)據(jù)元素都在一個組內(nèi)的排序；當(dāng)完成了所有數(shù)據(jù)元素都在一個組內(nèi)的排序后排序過程結(jié)束。希爾排序又稱作縮小增量排序。后排序過程結(jié)束。希爾排序又稱作縮小增量排序。3. 希爾排序希爾排序(Shell Sort) 開始時開始時 gap（間隔值）（間隔值） 的值較大，子序列中的對象較的值較大，子序列中的對象較少，排序速度較快；隨著排序進展，少，排序速度較快；隨著排序進展，gap 值逐漸變小，值逐漸變小，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎(chǔ)，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對象已基本

19、有序，所以排序速度仍然很快。大多數(shù)對象已基本有序，所以排序速度仍然很快。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級22希爾排序過程希爾排序過程6565 343425258787 121238385656 464614147777 929223235656656514142525777787873838232356563434141477771212232365654646252587879292383865657777121234345656121214146565343423237

20、77746462525878792923838121214142323252534343838464656566565777787879292結(jié)果序列結(jié)果序列g(shù)ap=6gap=3gap=1單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級23void ShellInsert(SqList &L, int gap) / 對順序表對順序表L作一趟希爾插入排序。本算法對算法作一趟希爾插入排序。本算法對算法10.1作了以下修改：作了以下修改： / 1. 前后記錄位置的增量是前后記錄位置的增量

21、是gap，而不是，而不是1； / 2. r0只是暫存單元，不是哨兵。當(dāng)只是暫存單元，不是哨兵。當(dāng)j=0時，插入位置已找到。時，插入位置已找到。 int i, j; for (i=gap+1; i0 & LT(L.r0.key, L.rj.key); j-=gap) L.rj+gap = L.rj; / 記錄后移，查找插入位置記錄后移，查找插入位置 L.rj+gap = L.r0; / 插入插入 / ShellInsert希爾排序的算法希爾排序的算法 (算法算法10.4)單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三

22、級第三級 第四級第四級 第五級第五級24void ShellSort ( SqList &L, int dlta, int t ) / 按增量序列按增量序列dlta0.t-1對順序表對順序表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問題

23、：剛才的改進算法是否已經(jīng)最優(yōu)問題：剛才的改進算法是否已經(jīng)最優(yōu)?冒泡排序的冒泡排序的改進改進算法算法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 8 9 1 2 3 4 5 6 7 8 9 如何解決呢？如何解決呢？單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級31 冒泡排序的冒泡排序的改進改進算法算法void BubbleSort ( SqList &L ) for (i=n, Change =TRUE; i = 2 &

24、Change; -i ) Change = FALSE; for ( j=1; j L. rj+1. key ) ElemType temp=L.rj; L.rj=L.rj+1; L.rj+1=temp; Change=TRUE; 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級32最壞情況（逆序）：最壞情況（逆序）：最好情況（正序）：最好情況（正序）：比較次數(shù)：比較次數(shù)：n-1移動次數(shù)：移動次數(shù)：0 比較次數(shù)：比較次數(shù)：移動次數(shù)：移動次數(shù)：2) 1(1- -= = = =nn(n-i)n

25、-1i2) 1(1- -= = = =n3n3(n-i)n-1i算法分析算法分析 n 時間復(fù)雜度為時間復(fù)雜度為O(n2)n 穩(wěn)定性：穩(wěn)定性：穩(wěn)定穩(wěn)定單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級33基本思想基本思想：任取待排序?qū)ο笮蛄兄械哪硞€對象（例如取任取待排序?qū)ο笮蛄兄械哪硞€對象（例如取第一個對象）作為第一個對象）作為樞軸樞軸(pivot)，按照該對象的關(guān)鍵字大小，按照該對象的關(guān)鍵字大小，將整個對象序列劃分為，將整個對象序列劃分為左右兩個子序列左右兩個子序列：2. 快速排序快速排序(

26、Quick Sort)u左側(cè)左側(cè)子序列中所有對象的關(guān)鍵字都子序列中所有對象的關(guān)鍵字都小于小于樞軸對象的關(guān)樞軸對象的關(guān)鍵字。鍵字。u右側(cè)右側(cè)子序列中所有對象的關(guān)鍵字都子序列中所有對象的關(guān)鍵字都大于或等于大于或等于樞軸對樞軸對象的關(guān)鍵字。象的關(guān)鍵字。樞軸對象則排在這兩個子序列中間樞軸對象則排在這兩個子序列中間(這也是該對象最終應(yīng)安這也是該對象最終應(yīng)安放的位置放的位置)。然后分別對這兩個子序列重復(fù)施行上述方法，。然后分別對這兩個子序列重復(fù)施行上述方法，直到所有的對象都排在相應(yīng)位置上為止。直到所有的對象都排在相應(yīng)位置上為止。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊

27、此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級34一趟快速排序的具體過程一趟快速排序的具體過程49 38 65 97 76 13 27 49pivot=49lowhigh27low65high13low97highhigh49第一趟結(jié)果：第一趟結(jié)果： 27 38 13 49 76 97 65 49 小于小于49大于等于大于等于49單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級35快速排序每一趟的劃分快速排序每一趟的劃分 int Partition ( SqL

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

29、, int high ) /* 交換順序表交換順序表L中子表中子表r low high 的記錄，樞軸記錄的記錄，樞軸記錄到位，并返回其所在到位，并返回其所在 的位置，此時在它之前（后）的記的位置，此時在它之前（后）的記錄均不大（?。┯谒浘淮螅ㄐ。┯谒?*/ L. r0=L. rlow; / 用子表的第一個記錄作樞軸記錄用子表的第一個記錄作樞軸記錄 int pivotkey = L. rlow. key; / 樞軸記錄關(guān)鍵字樞軸記錄關(guān)鍵字 / Partition 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第

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

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

32、0=L. rlow; / 用子表的第一個記錄作樞軸記錄用子表的第一個記錄作樞軸記錄 int pivotkey = L. rlow. key; / 樞軸記錄關(guān)鍵字樞軸記錄關(guān)鍵字 while ( low high ) L. rlow=L. r0; / 樞軸記錄到位樞軸記錄到位 return low; / 返回樞軸位置返回樞軸位置 / Partition 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級39快速排序每一趟的劃分快速排序每一趟的劃分 int Partition ( SqList &

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

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

35、此時在它之前（后）的記錄均不大（?。┯谒?*/ L. r0=L. rlow; / 用子表的第一個記錄作樞軸記錄用子表的第一個記錄作樞軸記錄 int pivotkey = L. rlow. key; / 樞軸記錄關(guān)鍵字樞軸記錄關(guān)鍵字 while ( low high ) while ( low=pivotkey ) -high; L. rlow = L. rhigh; / 將比樞軸記錄小的記錄移到低端將比樞軸記錄小的記錄移到低端 L. rlow=L. r0; / 樞軸記錄到位樞軸記錄到位 return low; / 返回樞軸位置返回樞軸位置 / Partition 單擊此處編輯母版標題樣式單擊此

36、處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級41快速排序每一趟的劃分快速排序每一趟的劃分 int Partition ( SqList &L, int low, int high ) /* 交換順序表交換順序表L中子表中子表r low high 的記錄，樞軸記錄到位，并返回其所在的記錄，樞軸記錄到位，并返回其所在 的位置，此時在它之前（后）的記錄均不大（?。┯谒奈恢?，此時在它之前（后）的記錄均不大（?。┯谒?*/ L. r0=L. rlow; / 用子表的第一個記錄作樞軸記錄用子表的第一個記錄作樞軸記錄

37、int pivotkey = L. rlow. key; / 樞軸記錄關(guān)鍵字樞軸記錄關(guān)鍵字 while ( low high ) while ( low=pivotkey ) -high; L. rlow = L. rhigh; / 將比樞軸記錄小的記錄移到低端將比樞軸記錄小的記錄移到低端 while ( low high & L. rlow. key = pivotkey ) +low; L.rhigh = L.rlow; / 將比樞軸記錄大的記錄移到高端將比樞軸記錄大的記錄移到高端 L. rlow=L. r0; / 樞軸記錄到位樞軸記錄到位 return low; / 返回樞軸位置

38、返回樞軸位置 / Partition 單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級42快速排序算法快速排序算法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, l

39、ow, pivotloc-1 ); / 對低子表遞歸排序?qū)Φ妥颖磉f歸排序 QSort(L,pivotloc+1,high); / 對高子表遞歸排序?qū)Ω咦颖磉f歸排序 / QSort單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級43算法分析算法分析n最理想的情況：每次劃分對一個對象定位后，該對象最理想的情況：每次劃分對一個對象定位后，該對象的左側(cè)子序列與右側(cè)子序列的長度相同。的左側(cè)子序列與右側(cè)子序列的長度相同。n就就平均時間平均時間而言，快速排序是而言，快速排序是最好最好的一種內(nèi)部排序方的一

40、種內(nèi)部排序方法。平均計算時間是法。平均計算時間是O(nlog2n)n最壞情況：初始關(guān)鍵字有序或基本有序。此時快速排最壞情況：初始關(guān)鍵字有序或基本有序。此時快速排序蛻化為冒泡排序，序蛻化為冒泡排序，時間復(fù)雜度時間復(fù)雜度為為O(n2)。占用附加存。占用附加存儲儲(即棧即棧)將達到將達到O(n)。n快速排序是一種快速排序是一種不穩(wěn)定不穩(wěn)定的排序方法。的排序方法。n對于對于 n 較大的平均情況而言，快速排序是較大的平均情況而言，快速排序是“快速快速”的，的，但是當(dāng)?shù)钱?dāng) n 很小時，這種排序方法往往比其它簡單排序很小時，這種排序方法往往比其它簡單排序方法還要慢。方法還要慢。單擊此處編輯母版標題樣式單擊

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

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

43、 Sort)單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級46一趟簡單選擇排序的過程一趟簡單選擇排序的過程149238365497576613727849ki=1jkjjjjkjjk1349單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級47149238365497576613727849i=kjjjjjj1349k k2一趟簡單選擇排序的過程一趟簡單選擇排序的過程單擊此處編輯母版標

44、題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級48void SelectSort ( SqList & L) for ( int i = 1; i L.length; i+ ) k= SelectMinKey( 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+) i

45、f (L.rj. key L.rm. key) m = j; /當(dāng)前具最小關(guān)鍵碼的對象當(dāng)前具最小關(guān)鍵碼的對象 return m;簡單選擇排序的算法簡單選擇排序的算法單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級49最壞情況：最壞情況：算法分析算法分析移動次數(shù)：移動次數(shù)：最好情況：最好情況：比較次數(shù)：比較次數(shù)：)() 1(21211nOnninni= =- -= =- - - -= =）（l 時間復(fù)雜度為時間復(fù)雜度為O(n2)。l 穩(wěn)定性：穩(wěn)定性：不穩(wěn)定不穩(wěn)定 為什么？為什么？0次次3(n

46、-1)次次單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級50世界杯比賽排名巴西巴西法國法國巴西巴西意大利意大利法國法國意大利意大利法國法國英國英國中國中國巴西巴西巴西巴西阿根廷阿根廷西班牙西班牙葡萄牙葡萄牙阿根廷阿根廷8個國家參加世界杯，個國家參加世界杯，需要多少次比賽得出冠軍？需要多少次比賽得出冠軍？單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級51樹形選擇排序又稱為錦標賽排序。

47、樹形選擇排序又稱為錦標賽排序?；舅枷牖舅枷耄号c體育比賽時的淘汰賽類似。首先取得與體育比賽時的淘汰賽類似。首先取得 n 個個對象的關(guān)鍵碼，進行對象的關(guān)鍵碼，進行兩兩比較兩兩比較，得到，得到 n/2 個比較的個比較的優(yōu)勝優(yōu)勝者者(關(guān)鍵碼小者關(guān)鍵碼小者)，作為第一步比較的結(jié)果保留下來。然后，作為第一步比較的結(jié)果保留下來。然后對這對這 n/2 個對象再進行關(guān)鍵碼的兩兩比較，個對象再進行關(guān)鍵碼的兩兩比較，如此重，如此重復(fù)，直到選出一個關(guān)鍵碼最小的對象。復(fù)，直到選出一個關(guān)鍵碼最小的對象。2. 樹形選擇排序樹形選擇排序(TreeSelection Sort)單擊此處編輯母版標題樣式單擊此處編輯母版標題樣

48、式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級52133813973865493876131327652749單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級5313974938761365274938133865132727382738657627單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級54279749387613

49、6527493827386576271338384938657649單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級55p錦標賽排序構(gòu)成的樹是錦標賽排序構(gòu)成的樹是滿的完全二叉樹滿的完全二叉樹，其深度為，其深度為 log2(2n-1)取上整，其中取上整，其中 n 為待排序元素個數(shù)。為待排序元素個數(shù)。p除第一次選擇具有最小關(guān)鍵字的對象需要進行除第一次選擇具有最小關(guān)鍵字的對象需要進行 n-1 次次關(guān)鍵字比較外，重構(gòu)勝者樹選擇具有次小、再次小關(guān)關(guān)鍵字比較外，重構(gòu)勝者樹選擇具有次小、再次小關(guān)鍵字對象

50、所需的關(guān)鍵字比較次數(shù)均為鍵字對象所需的關(guān)鍵字比較次數(shù)均為 O(log2n)?？傟P(guān)總關(guān)鍵字比較次數(shù)為鍵字比較次數(shù)為O(nlog2n)。p對象的移動次數(shù)不超過關(guān)鍵字的比較次數(shù)，所以錦標對象的移動次數(shù)不超過關(guān)鍵字的比較次數(shù)，所以錦標賽排序賽排序總的時間復(fù)雜度總的時間復(fù)雜度為為O(nlog2n)。p這種排序方法雖然減少了許多排序時間，但是這種排序方法雖然減少了許多排序時間，但是使用了使用了較多的附加存儲較多的附加存儲。p錦標賽排序是一個錦標賽排序是一個穩(wěn)定穩(wěn)定的排序方法。的排序方法。算法分析算法分析單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二

51、級第二級 第三級第三級 第四級第四級 第五級第五級563. 堆排序堆排序(Heap Sort)堆定義：堆定義：n 個元素的序列個元素的序列 k1, k2, , kn 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)滿足下列關(guān)系時，稱之為滿足下列關(guān)系時，稱之為堆堆。 kik2i kik2i ki k2i+1 ki k2i+1其中，其中，i = 1, 2, , n/2.前者稱為前者稱為最小堆最小堆，后者稱為，后者稱為最大堆最大堆。或或單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級57最小堆與最大堆舉例最小堆與最大堆舉例96

52、83273811091236248547913053最大堆最大堆最小堆最小堆單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級58基本思想基本思想：在輸出堆頂?shù)淖钚≈抵?，使得剩余在輸出堆頂?shù)淖钚≈抵?，使得剩余n-1個元個元素的序列重又建成一個堆，則得到素的序列重又建成一個堆，則得到n個元素中的次小值。個元素中的次小值。反復(fù)執(zhí)行，反復(fù)執(zhí)行，直到直到得到一個有序序列。得到一個有序序列。堆排序分為兩個步驟：堆排序分為兩個步驟：u 根據(jù)初始輸入數(shù)據(jù)形成初始堆；根據(jù)初始輸入數(shù)據(jù)形成初始堆；u 通過

53、一系列的對象交換和重新調(diào)整堆進行排序。通過一系列的對象交換和重新調(diào)整堆進行排序。3. 堆排序堆排序(Heap Sort)單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級59關(guān)鍵問題：關(guān)鍵問題：如何由一個無序序列建成一個堆如何由一個無序序列建成一個堆? (1) 如何調(diào)整余下的元素成為一個新堆如何調(diào)整余下的元素成為一個新堆? 3. 堆排序堆排序(Heap Sort)單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第

54、四級第四級 第五級第五級60堆調(diào)整過程堆調(diào)整過程1338277697654949rc=13單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級61123456136542堆調(diào)整堆調(diào)整單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級62123456136542堆調(diào)整堆調(diào)整單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第

55、三級 第四級第四級 第五級第五級63123456136542堆調(diào)整堆調(diào)整單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級64123456136542堆調(diào)整堆調(diào)整單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級65123456136542堆調(diào)整堆調(diào)整單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級

56、 第五級第五級66123456136542建立初始的最大堆建立初始的最大堆單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級67123456136542建立初始的最大堆建立初始的最大堆單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級68u最大堆的第一個對象最大堆的第一個對象r1具有最大的關(guān)鍵字，將具有最大的關(guān)鍵字，將r1與與rn對調(diào)，把具有最大關(guān)鍵字的對象交換到最后，對調(diào)，把具有最大關(guān)鍵

57、字的對象交換到最后，再對前面的再對前面的n-1個對象，使用堆的調(diào)整算法個對象，使用堆的調(diào)整算法HeapAdjust(1, n-1)，重新建立最大堆。結(jié)果具有次，重新建立最大堆。結(jié)果具有次最大關(guān)鍵字的對象又上浮到堆頂，即最大關(guān)鍵字的對象又上浮到堆頂，即r1位置。位置。u再對調(diào)再對調(diào)r1和和rn-1，調(diào)用，調(diào)用HeapAdjust (1, n-2)，對前，對前n-2個對象重新調(diào)整。個對象重新調(diào)整。u如此反復(fù)執(zhí)行，最后得到全部排序好的對象序列。如此反復(fù)執(zhí)行，最后得到全部排序好的對象序列。這個算法即堆排序算法。這個算法即堆排序算法。utypedef SqList HeapType; /順序存儲方式順序

58、存儲方式基于初始堆進行堆排序基于初始堆進行堆排序單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級69void HeapAdjust(HeapType &H, int s, int m) /調(diào)整調(diào)整H.rs的關(guān)鍵字，使的關(guān)鍵字，使H.rsm成為一個大頂堆成為一個大頂堆 ElemType rc=H.rs; for (int j=2*s; j=m; j*=2) /沿較大的孩子結(jié)點向下篩選沿較大的孩子結(jié)點向下篩選 if (j0; -i) / 把把H.r1.H.length建成大頂堆建成大頂

59、堆 HeapAdjust ( H, i, H.length ); for (i=H.length; i1; -i) temp=H.ri; H.ri=H.r1; H.r1=temp; /* 將堆頂記錄和當(dāng)前未經(jīng)排序子序列將堆頂記錄和當(dāng)前未經(jīng)排序子序列Hr1.i中中 最后一個記錄相互交換最后一個記錄相互交換 */ HeapAdjust (H, 1, i-1); / 將將H.r1.i-1 重新調(diào)整為大頂堆重新調(diào)整為大頂堆 / HeapSort堆排序算法堆排序算法單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級

60、 第五級第五級71算法分析算法分析p適宜記錄較多的文件適宜記錄較多的文件p在最壞的情況下，時間復(fù)雜度為在最壞的情況下，時間復(fù)雜度為O(nlog2n)p堆排序是一個堆排序是一個不穩(wěn)定不穩(wěn)定的排序方法。的排序方法。單擊此處編輯母版標題樣式單擊此處編輯母版標題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級72基本思想基本思想 將一個具有將一個具有n個待排序記錄的序列看成是個待排序記錄的序列看成是 n 個長度個長度為為 1 的有序序列，然后進行的有序序列，然后進行兩兩歸并兩兩歸并，得到，得到 n/2 個長度個長度為為 2 的有序序列，再進行兩兩歸并，得到的有序序列，再進行兩兩歸并，得到 n/4 個長度為個長度為 4 的有序序列，的有序序列，直至得到一個長度為，直至得到一個長度為 n 的有序序的有序序列