數(shù)據(jù)結(jié)構(gòu)課件：10.內(nèi)部排序

1、第九章第九章一、排序一、排序( (Sorting)Sorting)2第一節(jié)排序第一節(jié)排序n排序排序：將一個數(shù)據(jù)元素（或記錄）的任意序列，：將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列重新排列成一個按關(guān)鍵字有序的序列n內(nèi)部排序內(nèi)部排序：在排序期間數(shù)據(jù)對象全部存放在內(nèi)：在排序期間數(shù)據(jù)對象全部存放在內(nèi)存的排序；存的排序；n外部排序外部排序：在排序期間全部對象個數(shù)太多，不：在排序期間全部對象個數(shù)太多，不能同時存放在內(nèi)存，必須根據(jù)排序過程的要求，能同時存放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動的排序。不斷在內(nèi)、外存之間移動的排序。第第9章內(nèi)部排序章內(nèi)部排序二、排序

2、基本操作二、排序基本操作3第一節(jié)排序第一節(jié)排序排序的基本操作包括：n比較：比較兩個關(guān)鍵字的大小比較：比較兩個關(guān)鍵字的大小n移動：將記錄從一個位置移動至另一個位置移動：將記錄從一個位置移動至另一個位置第第9章內(nèi)部排序章內(nèi)部排序三、排序時間復(fù)雜度三、排序時間復(fù)雜度4第一節(jié)排序第一節(jié)排序n排序的時間復(fù)雜度可用算法執(zhí)行中的記錄關(guān)鍵排序的時間復(fù)雜度可用算法執(zhí)行中的記錄關(guān)鍵字比較次數(shù)與記錄移動次數(shù)來衡量。字比較次數(shù)與記錄移動次數(shù)來衡量。第第9章內(nèi)部排序章內(nèi)部排序四、排序方法的穩(wěn)定性四、排序方法的穩(wěn)定性5第一節(jié)排序第一節(jié)排序n如果在記錄序列中有兩個記錄如果在記錄序列中有兩個記錄riri和和rj, rj, 它

3、它們的關(guān)鍵字們的關(guān)鍵字 keyi = keyj , keyi = keyj , 且在排序之且在排序之前前, , 記錄記錄riri排在排在rjrj前面。前面。n如果在排序之后如果在排序之后, , 記錄記錄riri仍在記錄仍在記錄rjrj的前的前面面, , 則稱這個排序方法是穩(wěn)定的則稱這個排序方法是穩(wěn)定的, , n否則稱這個排序方法是不穩(wěn)定的。否則稱這個排序方法是不穩(wěn)定的。第第9章內(nèi)部排序章內(nèi)部排序6第二節(jié)插入排序第二節(jié)插入排序n每步將一個待排序的對象每步將一個待排序的對象, , 按其關(guān)鍵字大小按其關(guān)鍵字大小, , 插入到前面已經(jīng)排好序的有序表的適當位置上插入到前面已經(jīng)排好序的有序表的適當位置上,

4、 , 直到對象全部插入為止。直到對象全部插入為止。第第9章內(nèi)部排序章內(nèi)部排序一、直接插入排序一、直接插入排序7第二節(jié)插入排序第二節(jié)插入排序n當插入第當插入第i(i1)i(i1)個對象時個對象時, , 前面的前面的r0, r0, r1, r1, , ri-1, ri-1已經(jīng)排好序。已經(jīng)排好序。n用用riri的關(guān)鍵字與的關(guān)鍵字與ri-1, ri-2, ri-1, ri-2, 的關(guān)鍵的關(guān)鍵字順序進行比較字順序進行比較( (和順序查找類似和順序查找類似) )，如果小于，如果小于，則將則將rxrx向后移動向后移動( (插入位置后的記錄向后順插入位置后的記錄向后順移移) )n找到插入位置即將找到插入位置即

5、將riri插入插入第第9章內(nèi)部排序章內(nèi)部排序一、直接插入排序一、直接插入排序( (舉例舉例) )8第二節(jié)插入排序第二節(jié)插入排序n已知待序的一組記錄的初始排列為：已知待序的一組記錄的初始排列為：21, 25, 21, 25, 49, 2549, 25* *, 16, 08, 16, 08第第9章內(nèi)部排序章內(nèi)部排序0 1 2 3 4 5一、直接插入排序一、直接插入排序( (舉例舉例) )9第二節(jié)插入排序第二節(jié)插入排序第第9章內(nèi)部排序章內(nèi)部排序0 1 2 3 4 5 temp2525250 1 2 3 4 5 temp494949一、直接插入排序一、直接插入排序( (舉例舉例) )10第二節(jié)插入排序

6、第二節(jié)插入排序第第9章內(nèi)部排序章內(nèi)部排序252525* * *0 1 2 3 4 50 1 2 3 4 5 temp161616一、直接插入排序一、直接插入排序( (舉例舉例) )11第二節(jié)插入排序第二節(jié)插入排序第第9章內(nèi)部排序章內(nèi)部排序0 1 2 3 4 5 temp0808080 1 2 3 4 5完成一、直接插入排序一、直接插入排序( (算法實現(xiàn)算法實現(xiàn)) )12第二節(jié)插入排序第二節(jié)插入排序void InsertSort (int r , int m ) void InsertSort (int r , int m ) / / 假設(shè)關(guān)鍵字為整型，放在向量假設(shè)關(guān)鍵字為整型，放在向量rr中中

7、 int n, j, temp; int n, j, temp; for ( n = 1; n m; n+ ) for ( n = 1; n 0; j- ) / for ( j = n; j 0; j- ) /從后向前順序比較，并依次后移從后向前順序比較，并依次后移 if ( temp rj-1 ) rj = rj-1;if ( temp rj-1 ) rj = rj-1; else break; else break; rj = temp; rj = temp; 第第9章內(nèi)部排序章內(nèi)部排序一、直接插入排序一、直接插入排序( (算法分析算法分析) )13第二節(jié)插入排序第二節(jié)插入排序n關(guān)鍵字比較

8、次數(shù)和記錄移動次數(shù)與記錄關(guān)鍵字關(guān)鍵字比較次數(shù)和記錄移動次數(shù)與記錄關(guān)鍵字的初始排列有關(guān)。的初始排列有關(guān)。n最好情況下最好情況下, , 排序前記錄已按關(guān)鍵字從小到大排序前記錄已按關(guān)鍵字從小到大有序有序, , 每趟只需與前面有序記錄序列的最后一每趟只需與前面有序記錄序列的最后一個記錄比較個記錄比較1 1次次, , 移動移動2 2次記錄次記錄, , 總的關(guān)鍵字比總的關(guān)鍵字比較次數(shù)為較次數(shù)為 n-1, n-1, 記錄移動次數(shù)為記錄移動次數(shù)為 2( 2(n-1)n-1)。第第9章內(nèi)部排序章內(nèi)部排序一、直接插入排序一、直接插入排序( (算法分析算法分析) )14第二節(jié)插入排序第二節(jié)插入排序n最壞情況下最壞情

9、況下, , 第第i i趟時第趟時第i i個記錄必須與前面?zhèn)€記錄必須與前面i i個記錄都做關(guān)鍵字比較個記錄都做關(guān)鍵字比較, , 并且每做并且每做1 1次比較就次比較就要做要做1 1次數(shù)據(jù)移動。則總關(guān)鍵字比較次數(shù)次數(shù)據(jù)移動。則總關(guān)鍵字比較次數(shù)KCNKCN和和記錄移動次數(shù)記錄移動次數(shù)RMNRMN分別為分別為第第9章內(nèi)部排序章內(nèi)部排序111122142221nininnniRMNnnniKCN/)()( ,/)(22一、直接插入排序一、直接插入排序( (算法分析算法分析) )15第二節(jié)插入排序第二節(jié)插入排序n在平均情況下的關(guān)鍵字比較次數(shù)和記錄移動次在平均情況下的關(guān)鍵字比較次數(shù)和記錄移動次數(shù)約為數(shù)約為

10、n n2 2/4/4。n直接插入排序的時間復(fù)雜度為直接插入排序的時間復(fù)雜度為O(nO(n2 2) )。n直接插入排序是一種穩(wěn)定的排序方法直接插入排序是一種穩(wěn)定的排序方法n直接插入排序最大的優(yōu)點是簡單，在記錄數(shù)較直接插入排序最大的優(yōu)點是簡單，在記錄數(shù)較少時，是比較好的辦法少時，是比較好的辦法第第9章內(nèi)部排序章內(nèi)部排序二、折半插入排序二、折半插入排序16第二節(jié)插入排序第二節(jié)插入排序n折半插入排序在查找記錄插入位置時，采用折折半插入排序在查找記錄插入位置時，采用折半查找算法半查找算法n折半查找比順序查找快折半查找比順序查找快, , 所以折半插入排序在所以折半插入排序在查找上性能比直接插入排序好查找上

11、性能比直接插入排序好n但需要移動的記錄數(shù)目與直接插入排序相同但需要移動的記錄數(shù)目與直接插入排序相同( (為為O(nO(n2 2)n折半插入排序的時間復(fù)雜度為折半插入排序的時間復(fù)雜度為O(nO(n2 2) )。n折半插入排序是一種穩(wěn)定的排序方法折半插入排序是一種穩(wěn)定的排序方法第第9章內(nèi)部排序章內(nèi)部排序三、希爾排序三、希爾排序17第二節(jié)插入排序第二節(jié)插入排序n從直接插入排序可以看出，當待排序列為正序從直接插入排序可以看出，當待排序列為正序時，時間復(fù)雜度為時，時間復(fù)雜度為O(n)O(n)n若待排序列基本有序時，插入排序效率會提高若待排序列基本有序時，插入排序效率會提高n希爾排序方法是先將待排序列分成

12、若干子序列希爾排序方法是先將待排序列分成若干子序列分別進行插入排序，待整個序列基本有序時，分別進行插入排序，待整個序列基本有序時，再對全體記錄進行一次直接插入排序再對全體記錄進行一次直接插入排序n希爾排序又稱為縮小增量排序。希爾排序又稱為縮小增量排序。第第9章內(nèi)部排序章內(nèi)部排序三、希爾排序三、希爾排序( (算法算法) )18第二節(jié)插入排序第二節(jié)插入排序n首先取一個整數(shù)首先取一個整數(shù) gap n(gap 1; i- - ) for ( i = m; i 1; i- - ) for ( j = 1; j m; j+ ) for ( j = 1; j rj+1 )if ( rj rj+1 ) rj

13、rj+1; rj rj+1; 第第9章內(nèi)部排序章內(nèi)部排序一、起泡排序一、起泡排序27第三節(jié)快速排序第三節(jié)快速排序第第9章內(nèi)部排序章內(nèi)部排序初始關(guān)鍵字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序一、起泡排序一、起泡排序( (性能分析性能分析) )28第三節(jié)快速排序第三節(jié)快速排序n最好情況：在記錄的初始排列已經(jīng)按關(guān)鍵字從最好情況：在記錄的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時小到大排好序時, ,此算法只執(zhí)行一趟起泡此算法只執(zhí)行一趟起泡, ,做做n-n-1 1次關(guān)鍵字比較次關(guān)鍵字比較, ,不移動記錄不移動記錄第第9章內(nèi)部排序章內(nèi)部排序一、起泡排序一、起泡排序( (性能分析性能分析) )29第三節(jié)

14、快速排序第三節(jié)快速排序n最壞情況：執(zhí)行最壞情況：執(zhí)行n-1n-1趟起泡趟起泡, ,第第i i趟做趟做n-in-i次關(guān)鍵次關(guān)鍵字比較字比較, , 執(zhí)行執(zhí)行n-in-i次記錄交換，共計：次記錄交換，共計：n起泡排序的時間復(fù)雜度為起泡排序的時間復(fù)雜度為O(nO(n2 2) )n起泡排序是一種穩(wěn)定的排序方法起泡排序是一種穩(wěn)定的排序方法第第9章內(nèi)部排序章內(nèi)部排序11111233121nininninRMNnninKCN)()()()(二、快速排序二、快速排序30第三節(jié)快速排序第三節(jié)快速排序n任取待排序記錄序列中的某個記錄任取待排序記錄序列中的某個記錄( (例如取第例如取第一個記錄一個記錄) )作為基準作

15、為基準( (樞樞),),按照該記錄的關(guān)鍵字按照該記錄的關(guān)鍵字大小大小, ,將整個記錄序列劃分為左右兩個子序列：將整個記錄序列劃分為左右兩個子序列： n左側(cè)子序列中所有記錄的關(guān)鍵字都小于或等于左側(cè)子序列中所有記錄的關(guān)鍵字都小于或等于基準記錄的關(guān)鍵字基準記錄的關(guān)鍵字 n右側(cè)子序列中所有記錄的關(guān)鍵字都大于基準記右側(cè)子序列中所有記錄的關(guān)鍵字都大于基準記錄的關(guān)鍵字錄的關(guān)鍵字第第9章內(nèi)部排序章內(nèi)部排序二、快速排序二、快速排序31第三節(jié)快速排序第三節(jié)快速排序n基準記錄則排在這兩個子序列中間基準記錄則排在這兩個子序列中間( (這也是該這也是該記錄最終應(yīng)安放的位置記錄最終應(yīng)安放的位置) )。n然后分別對這兩個子

16、序列重復(fù)施行上述方法，然后分別對這兩個子序列重復(fù)施行上述方法，直到所有的記錄都排在相應(yīng)位置上為止。直到所有的記錄都排在相應(yīng)位置上為止。n基準記錄也稱為樞軸（或支點）記錄?；鶞视涗浺卜Q為樞軸（或支點）記錄。第第9章內(nèi)部排序章內(nèi)部排序二、快速排序二、快速排序( (算法算法) )32第三節(jié)快速排序第三節(jié)快速排序n取序列第一個記錄為樞軸記錄，其關(guān)鍵字為取序列第一個記錄為樞軸記錄，其關(guān)鍵字為PivotkeyPivotkeyn指針指針lowlow指向序列第一個記錄位置指向序列第一個記錄位置n指針指針highhigh指向序列最后一個記錄位置指向序列最后一個記錄位置第第9章內(nèi)部排序章內(nèi)部排序二、快速排序二、快

17、速排序( (算法算法) )33第三節(jié)快速排序第三節(jié)快速排序n一趟排序一趟排序( (某個子序列某個子序列) )過程過程1.1.從從highhigh指向的記錄開始指向的記錄開始, ,向前找到第一個關(guān)鍵字的值向前找到第一個關(guān)鍵字的值小于小于PivotkeyPivotkey的記錄的記錄, ,將其放到將其放到lowlow指向的位指向的位置置, ,low+1low+12.2.從從lowlow指向的記錄開始指向的記錄開始, ,向后找到第一個關(guān)鍵字的值向后找到第一個關(guān)鍵字的值大于大于PivotkeyPivotkey的記錄的記錄, ,將其放到將其放到highhigh指向的位指向的位置置, ,high-1high

18、-13.3.重復(fù)重復(fù)1,21,2，直到，直到low=highlow=high，將樞軸記錄放在將樞軸記錄放在low(high)low(high)指向的位置指向的位置第第9章內(nèi)部排序章內(nèi)部排序二、快速排序二、快速排序( (算法算法) )34第三節(jié)快速排序第三節(jié)快速排序n對樞軸記錄前后兩個子序列執(zhí)行相同的操作，對樞軸記錄前后兩個子序列執(zhí)行相同的操作，直到每個子序列都只有一個記錄為止直到每個子序列都只有一個記錄為止第第9章內(nèi)部排序章內(nèi)部排序一、快速排序一、快速排序( (算法實現(xiàn)算法實現(xiàn)) )35第二節(jié)快速排序第二節(jié)快速排序第第9章內(nèi)部排序章內(nèi)部排序void void QuickSortQuickSor

19、t ( (intint r ; r ;intint b;intb;int m ) m ) / / 假設(shè)關(guān)鍵字為整型，放在向量假設(shè)關(guān)鍵字為整型，放在向量rr中中 intint low=b, high=m, temp=r1; low=b, high=m, temp=r1; while ( lowhigh) while ( lowtemp) high=high-1; while(rhightemp) high=high-1; rlow rlow-rhigh-rhigh; while(rlowtemp) low=low+1; while(rlow-rhigh;rhigh; rlow=rhigh=tem

20、p; rlow=rhigh=temp; QuickSortQuickSort(r,1,high-1);(r,1,high-1); QuickSortQuickSort(r,high+1,m);(r,high+1,m); 二、快速排序二、快速排序( (舉例舉例) )36第三節(jié)快速排序第三節(jié)快速排序第第9章內(nèi)部排序章內(nèi)部排序初始關(guān)鍵字初始關(guān)鍵字pivotkey一次交換一次交換二次交換二次交換三次交換三次交換high-1完成一趟排序完成一趟排序lowhighlowlowlowlowlowhighhighhighhighhigh二、快速排序二、快速排序( (舉例舉例) )37第三節(jié)快速排序第三節(jié)快速排

21、序第第9章內(nèi)部排序章內(nèi)部排序完成一趟排序完成一趟排序分別進行快速排序分別進行快速排序有序序列有序序列二、快速排序二、快速排序( (性能分析性能分析) )38第三節(jié)快速排序第三節(jié)快速排序n快速排序是一個遞歸過程快速排序是一個遞歸過程, , 其遞歸樹如圖所示其遞歸樹如圖所示第第9章內(nèi)部排序章內(nèi)部排序n利用序列第一個記錄作為利用序列第一個記錄作為基準，將整個序列劃分為基準，將整個序列劃分為左右兩個子序列。只要是左右兩個子序列。只要是關(guān)鍵字小于基準記錄關(guān)鍵關(guān)鍵字小于基準記錄關(guān)鍵字的記錄都移到序列左側(cè)字的記錄都移到序列左側(cè)二、快速排序二、快速排序( (性能分析性能分析) )39第三節(jié)快速排序第三節(jié)快速排

22、序n快速排序的趟數(shù)取決于遞歸樹的高度。快速排序的趟數(shù)取決于遞歸樹的高度。n如果每次劃分對一個記錄定位后如果每次劃分對一個記錄定位后, , 該記錄的左該記錄的左側(cè)子序列與右側(cè)子序列的長度相同側(cè)子序列與右側(cè)子序列的長度相同, , 則下一步則下一步將是對兩個長度減半的子序列進行排序?qū)⑹菍蓚€長度減半的子序列進行排序, , 這是這是最理想的情況。最理想的情況。第第9章內(nèi)部排序章內(nèi)部排序二、快速排序二、快速排序( (性能分析性能分析) )40第三節(jié)快速排序第三節(jié)快速排序n在在 n n個元素的序列中個元素的序列中, ,對一個記錄定位所需時對一個記錄定位所需時間為間為 O(n)O(n)。若設(shè)若設(shè) t(n)

23、t(n) 是對是對 n n 個元素的序列個元素的序列進行排序所需的時間進行排序所需的時間, , 而且每次對一個記錄正而且每次對一個記錄正確定位后確定位后, , 正好把序列劃分為長度相等的兩個正好把序列劃分為長度相等的兩個子序列子序列, , 此時此時, , 總的計算時間為：總的計算時間為：T(n) cn + 2T(n/2 ) / c 是一個常數(shù)是一個常數(shù) cn + 2 ( cn/2 + 2T(n/4) ) = 2cn + 4T(n/4) 2cn + 4 ( cn/4 +2T(n/8) ) = 3cn + 8T(n/8) cn log2n + nT(1) = O(n log2n )第第9章內(nèi)部排序

24、章內(nèi)部排序二、快速排序二、快速排序( (性能分析性能分析) )41第三節(jié)快速排序第三節(jié)快速排序n可以證明可以證明, , 快速排序的平均計算時間也是快速排序的平均計算時間也是O(nlogO(nlog2 2n)n)。n實驗結(jié)果表明實驗結(jié)果表明: : 就平均計算時間而言就平均計算時間而言, , 快速排快速排序是所有內(nèi)排序方法中最好的一個。序是所有內(nèi)排序方法中最好的一個。n但快速排序是一種不穩(wěn)定的排序方法但快速排序是一種不穩(wěn)定的排序方法第第9章內(nèi)部排序章內(nèi)部排序二、快速排序二、快速排序( (性能分析性能分析) )42第三節(jié)快速排序第三節(jié)快速排序n在最壞情況下在最壞情況下, , 即待排序記錄序列已經(jīng)按其

25、關(guān)鍵字從即待排序記錄序列已經(jīng)按其關(guān)鍵字從小到大排好序小到大排好序, , 其遞歸樹成為單支樹其遞歸樹成為單支樹, , n每次劃分只得到一個比上一次少一個記錄的子序列。每次劃分只得到一個比上一次少一個記錄的子序列。n必須經(jīng)過必須經(jīng)過n-1 n-1 趟才能把所有記錄定位趟才能把所有記錄定位, , n而且第而且第 i i 趟需要經(jīng)過趟需要經(jīng)過 n-i n-i 次關(guān)鍵字比較才能找到第次關(guān)鍵字比較才能找到第 i i 個記錄的安放位置，總的關(guān)鍵字比較次數(shù)將達到個記錄的安放位置，總的關(guān)鍵字比較次數(shù)將達到第第9章內(nèi)部排序章內(nèi)部排序2121211nnninni)()(二、快速排序二、快速排序( (改進改進) )4

26、3第三節(jié)快速排序第三節(jié)快速排序n樞軸記錄取樞軸記錄取lowlow、highhigh、(low+high)/2(low+high)/2三者指三者指向記錄關(guān)鍵字居中的記錄向記錄關(guān)鍵字居中的記錄第第9章內(nèi)部排序章內(nèi)部排序一、簡單選擇排序一、簡單選擇排序44第四節(jié)選擇排序第四節(jié)選擇排序n每一趟每一趟( (例如第例如第i i趟趟, ,i=0,1,i=0,1,n-2),n-2)在后面在后面n-in-i個待排序記錄中選出關(guān)鍵字最小的記錄個待排序記錄中選出關(guān)鍵字最小的記錄, ,與第與第i i個記錄交換個記錄交換第第9章內(nèi)部排序章內(nèi)部排序一、簡單選擇排序一、簡單選擇排序( (舉例舉例) )45第四節(jié)選擇排序第四

27、節(jié)選擇排序第第9章內(nèi)部排序章內(nèi)部排序0 1 2 3 4 5 最小者 08交換21,08最小者 16交換25,16最小者 21交換49,21i=0i=1i=2一、簡單選擇排序一、簡單選擇排序( (舉例舉例) )46第四節(jié)選擇排序第四節(jié)選擇排序第第9章內(nèi)部排序章內(nèi)部排序0 1 2 3 4 5 最小者 25*不需交換最小者 25不需交換結(jié)束i=3i=4i=5一、簡單選擇排序一、簡單選擇排序( (性能分析性能分析) )47第四節(jié)選擇排序第四節(jié)選擇排序n直接選擇排序的關(guān)鍵字比較次數(shù)直接選擇排序的關(guān)鍵字比較次數(shù) KCN KCN 與記錄與記錄的初始排列無關(guān)。的初始排列無關(guān)。n設(shè)整個待排序記錄序列有設(shè)整個待排

28、序記錄序列有n n個記錄個記錄, ,則第則第i i趟選趟選擇具有最小關(guān)鍵字記錄所需的比較次數(shù)總是擇具有最小關(guān)鍵字記錄所需的比較次數(shù)總是 n-i-1n-i-1次?？偟年P(guān)鍵字比較次數(shù)為次?？偟年P(guān)鍵字比較次數(shù)為第第9章內(nèi)部排序章內(nèi)部排序20211ninninKCN)()(一、簡單選擇排序一、簡單選擇排序( (性能分析性能分析) )48第四節(jié)選擇排序第四節(jié)選擇排序n記錄的移動次數(shù)與記錄序列的初始排列有關(guān)。記錄的移動次數(shù)與記錄序列的初始排列有關(guān)。當這組記錄的初始狀態(tài)是按其關(guān)鍵字從小到大當這組記錄的初始狀態(tài)是按其關(guān)鍵字從小到大有序的時候有序的時候, ,記錄的移動次數(shù)記錄的移動次數(shù)RMN=0,RMN=0,達

29、到最少。達到最少。n最壞情況是每一趟都要進行交換，總的記錄移最壞情況是每一趟都要進行交換，總的記錄移動次數(shù)為動次數(shù)為 RMN = 3(n-1)RMN = 3(n-1)。n直接選擇排序是一種不穩(wěn)定的排序方法。直接選擇排序是一種不穩(wěn)定的排序方法。第第9章內(nèi)部排序章內(nèi)部排序二、堆排序二、堆排序49第四節(jié)選擇排序第四節(jié)選擇排序n設(shè)有一個關(guān)鍵字集合，按完全二叉樹的順序存設(shè)有一個關(guān)鍵字集合，按完全二叉樹的順序存儲方式存放在一個一維數(shù)組中。對它們從根開儲方式存放在一個一維數(shù)組中。對它們從根開始，自頂向下，同一層自左向右從始，自頂向下，同一層自左向右從 1 1 開始連開始連續(xù)編號。若滿足續(xù)編號。若滿足 K K

30、i i K K2i2i & K & Ki i K K2i+1 2i+1 則稱該關(guān)鍵字集合構(gòu)成一個堆則稱該關(guān)鍵字集合構(gòu)成一個堆( (最大堆最大堆) )第第9章內(nèi)部排序章內(nèi)部排序二、堆排序二、堆排序( (舉例舉例) )50第四節(jié)選擇排序第四節(jié)選擇排序第第9章內(nèi)部排序章內(nèi)部排序136542二、堆排序二、堆排序51第四節(jié)選擇排序第四節(jié)選擇排序n堆排序主要要解決兩個問題：堆排序主要要解決兩個問題：1.1.如何根據(jù)給的序列建初始堆如何根據(jù)給的序列建初始堆2.2.如何在交換掉根結(jié)點后，將剩下的結(jié)點調(diào)整為如何在交換掉根結(jié)點后，將剩下的結(jié)點調(diào)整為新的堆新的堆( (篩選篩選) )第第9章內(nèi)部排序章

31、內(nèi)部排序二、堆排序二、堆排序( (篩選篩選) )52第四節(jié)選擇排序第四節(jié)選擇排序n輸出根結(jié)點輸出根結(jié)點n用最后結(jié)點代替根結(jié)點值用最后結(jié)點代替根結(jié)點值n比較根結(jié)點與兩個子結(jié)點的值，如果小于其中比較根結(jié)點與兩個子結(jié)點的值，如果小于其中一個子結(jié)點，則選擇大的子結(jié)點與根結(jié)點交換一個子結(jié)點，則選擇大的子結(jié)點與根結(jié)點交換n繼續(xù)將交換的結(jié)點與其子結(jié)點比較繼續(xù)將交換的結(jié)點與其子結(jié)點比較n直到葉子結(jié)點或者根節(jié)點值大于兩個子結(jié)點直到葉子結(jié)點或者根節(jié)點值大于兩個子結(jié)點第第9章內(nèi)部排序章內(nèi)部排序二、堆排序二、堆排序( (篩選舉例篩選舉例) )53第四節(jié)選擇排序第四節(jié)選擇排序第第9章內(nèi)部排序章內(nèi)部排序136542136

32、542136542二、堆排序二、堆排序( (創(chuàng)建初始堆創(chuàng)建初始堆) )54第四節(jié)選擇排序第四節(jié)選擇排序n根據(jù)給定的序列，從根據(jù)給定的序列，從1 1至至n n按順序創(chuàng)建一個完全按順序創(chuàng)建一個完全二叉樹二叉樹n由最后一個非終端結(jié)點由最后一個非終端結(jié)點( (第第n/2n/2個結(jié)點個結(jié)點) )開始至開始至第第1 1個結(jié)點，逐步做篩選個結(jié)點，逐步做篩選第第9章內(nèi)部排序章內(nèi)部排序二、堆排序二、堆排序( (創(chuàng)建初始堆舉例創(chuàng)建初始堆舉例) )55第四節(jié)選擇排序第四節(jié)選擇排序n已知待序的一組記錄的初始排列為：已知待序的一組記錄的初始排列為：21,25,49, 21,25,49, 2525* *,16,08,16

33、,08第第9章內(nèi)部排序章內(nèi)部排序123456二、堆排序二、堆排序( (創(chuàng)建初始堆舉例創(chuàng)建初始堆舉例) )56第四節(jié)選擇排序第四節(jié)選擇排序第第9章內(nèi)部排序章內(nèi)部排序123456136542i = 3 時的局部調(diào)整時的局部調(diào)整二、堆排序二、堆排序( (創(chuàng)建初始堆舉例創(chuàng)建初始堆舉例) )57第四節(jié)選擇排序第四節(jié)選擇排序第第9章內(nèi)部排序章內(nèi)部排序123456136542二、堆排序二、堆排序( (舉例舉例) )58第四節(jié)選擇排序第四節(jié)選擇排序第第9章內(nèi)部排序章內(nèi)部排序012345025431二、堆排序二、堆排序( (舉例舉例) )59第四節(jié)選擇排序第四節(jié)選擇排序第第9章內(nèi)部排序章內(nèi)部排序01234502

34、5431二、堆排序二、堆排序( (舉例舉例) )60第四節(jié)選擇排序第四節(jié)選擇排序第第9章內(nèi)部排序章內(nèi)部排序012345025431二、堆排序二、堆排序( (舉例舉例) )61第四節(jié)選擇排序第四節(jié)選擇排序第第9章內(nèi)部排序章內(nèi)部排序012345025431二、堆排序二、堆排序( (舉例舉例) )62第四節(jié)選擇排序第四節(jié)選擇排序第第9章內(nèi)部排序章內(nèi)部排序012345025431二、堆排序二、堆排序( (性能分析性能分析) )63第四節(jié)選擇排序第四節(jié)選擇排序n對于長度為對于長度為n n的序列，其對應(yīng)的完全二叉樹的的序列，其對應(yīng)的完全二叉樹的深度為深度為k(k(2 2k-1k-1 n n 2 2k k)

35、 )n對深度為對深度為k k的堆，篩選算法中進行的關(guān)鍵比較的堆，篩選算法中進行的關(guān)鍵比較次數(shù)至多為次數(shù)至多為2(2(k-1)k-1)次次n堆排序時間主要耗費在建初始堆和調(diào)整建新堆堆排序時間主要耗費在建初始堆和調(diào)整建新堆( (篩選篩選) )上上n建初始堆最多做建初始堆最多做n/2n/2次篩選次篩選第第9章內(nèi)部排序章內(nèi)部排序二、堆排序二、堆排序( (性能分析性能分析) )64第四節(jié)選擇排序第四節(jié)選擇排序n對長度為對長度為n n的序列，排序最多需要做的序列，排序最多需要做n-1n-1次調(diào)整次調(diào)整建新堆建新堆( (篩選篩選) )n因此共需要因此共需要O(nxk)O(nxk)量級的時間量級的時間nk =

36、 logk = log2 2n nn堆排序時間復(fù)雜度為堆排序時間復(fù)雜度為O(nlogO(nlog2 2n)n)n堆排序是一個不穩(wěn)定的排序方法堆排序是一個不穩(wěn)定的排序方法第第9章內(nèi)部排序章內(nèi)部排序一、歸并一、歸并65第五節(jié)歸并排序第五節(jié)歸并排序n歸并是將兩個或兩個以上的有序表合并成一個歸并是將兩個或兩個以上的有序表合并成一個新的有序表。新的有序表。第第9章內(nèi)部排序章內(nèi)部排序二、兩路歸并二、兩路歸并66第五節(jié)歸并排序第五節(jié)歸并排序typedef int SortData;void merge ( SortData InitList , SortData mergedList , int left,

37、 int mid, int right ) int i = left, j = mid+1, k = left; while ( i = mid & j = right ) /兩兩比較將較小的并入 if ( InitListi = InitListj ) mergedList k = InitListi; i+; k+; else mergedList k = InitListj; j+; k+; while (i = mid) mergedListk = InitListi; i+; k+; /將mid前剩余的并入 while (j = right) mergedListk = In

38、itListj; j+; k+; /將mid后剩余的并入第第9章內(nèi)部排序章內(nèi)部排序Left midrightInitListmergedList二、兩路歸并二、兩路歸并( (性能分析性能分析) )67第五節(jié)歸并排序第五節(jié)歸并排序n假設(shè)待歸兩個有序表長度分別為假設(shè)待歸兩個有序表長度分別為m m和和n n，則兩路則兩路歸并后，新的有序表長度為歸并后，新的有序表長度為m+nm+nn兩路歸并操作至多只需要兩路歸并操作至多只需要m+nm+n次移位和次移位和m+nm+n次比次比較較n因此兩路歸并的時間復(fù)雜度為因此兩路歸并的時間復(fù)雜度為O(m+n)O(m+n)第第9章內(nèi)部排序章內(nèi)部排序三、三、2 2路歸并排

39、序路歸并排序68第五節(jié)歸并排序第五節(jié)歸并排序n將將n n個記錄看成是個記錄看成是n n個有序序列個有序序列n將前后相鄰的兩個有序序列歸并為一個有序序?qū)⑶昂笙噜彽膬蓚€有序序列歸并為一個有序序列列( (兩路歸并兩路歸并) )n重復(fù)做兩路歸并操作，直到只有一個有序序列重復(fù)做兩路歸并操作，直到只有一個有序序列為止為止第第9章內(nèi)部排序章內(nèi)部排序三、三、2 2路歸并排序路歸并排序( (舉例舉例) )69第五節(jié)歸并排序第五節(jié)歸并排序第第9章內(nèi)部排序章內(nèi)部排序0 1 2 3 4 5 一趟歸并之后二趟歸并之后三趟歸并之后三、三、2 2路歸并排序路歸并排序( (性能分析性能分析) )70第五節(jié)歸并排序第五節(jié)歸并排

40、序n如果待排序的記錄為如果待排序的記錄為n n個，則需要做個，則需要做loglog2 2n n趟兩趟兩路歸并排序路歸并排序n每趟兩路歸并排序的時間復(fù)雜度為每趟兩路歸并排序的時間復(fù)雜度為O(n)O(n)n因此因此2 2路歸并排序的時間復(fù)雜度為路歸并排序的時間復(fù)雜度為O(nlogO(nlog2 2n)n)n歸并排序是一種穩(wěn)定的排序方法歸并排序是一種穩(wěn)定的排序方法第第9章內(nèi)部排序章內(nèi)部排序一、多關(guān)鍵字的排序一、多關(guān)鍵字的排序71第六節(jié)基數(shù)排序第六節(jié)基數(shù)排序n例：對例：對5252張撲克牌按以下次序排序：張撲克牌按以下次序排序：23A23A23A23An兩個關(guān)鍵字：花色兩個關(guān)鍵字：花色（） 面值面值（2

41、3A）n并且并且“花色花色”地位高于地位高于“面值面值”第第9章內(nèi)部排序章內(nèi)部排序一、多關(guān)鍵字的排序一、多關(guān)鍵字的排序( (最低位優(yōu)先法最低位優(yōu)先法LSD)LSD)72第六節(jié)基數(shù)排序第六節(jié)基數(shù)排序n從最低位關(guān)鍵字從最低位關(guān)鍵字kdkd起進行排序，起進行排序，n然后再對高一位的關(guān)鍵字排序，然后再對高一位的關(guān)鍵字排序，n依次重復(fù)，直至對最高位關(guān)鍵字依次重復(fù)，直至對最高位關(guān)鍵字k1k1排序后，便排序后，便成為一個有序序列成為一個有序序列第第9章內(nèi)部排序章內(nèi)部排序一、多關(guān)鍵字的排序一、多關(guān)鍵字的排序( (最低位優(yōu)先法最低位優(yōu)先法LSDLSD舉例舉例) )73第六節(jié)基數(shù)排序第六節(jié)基數(shù)排序第第9章內(nèi)部排序

42、章內(nèi)部排序0 1 2 3 4 5 最低位(個位)排序后最高位(十位)排序后二、鏈式基數(shù)排序二、鏈式基數(shù)排序74第六節(jié)基數(shù)排序第六節(jié)基數(shù)排序n基數(shù)排序：借助基數(shù)排序：借助“分配分配”和和“收集收集”對單邏輯對單邏輯關(guān)鍵字進行排序的一種方法關(guān)鍵字進行排序的一種方法n鏈式基數(shù)排序方法：用鏈表作存儲結(jié)構(gòu)的基數(shù)鏈式基數(shù)排序方法：用鏈表作存儲結(jié)構(gòu)的基數(shù)排序排序n設(shè)置設(shè)置1010個隊列，個隊列，fifi和和eiei分別為第分別為第i i個隊列個隊列的頭指針和尾指針的頭指針和尾指針第第9章內(nèi)部排序章內(nèi)部排序二、鏈式基數(shù)排序二、鏈式基數(shù)排序75第六節(jié)基數(shù)排序第六節(jié)基數(shù)排序n第第i i趟分配：根據(jù)第趟分配：根據(jù)第

43、i i位關(guān)鍵字的值，改變記錄位關(guān)鍵字的值，改變記錄的指針，將鏈表中記錄分配至的指針，將鏈表中記錄分配至1010個鏈隊列中，個鏈隊列中，每個隊列中記錄關(guān)鍵字的第每個隊列中記錄關(guān)鍵字的第i i位關(guān)鍵字相同位關(guān)鍵字相同n第第i i趟收集：改變所有非空隊列的隊尾記錄的趟收集：改變所有非空隊列的隊尾記錄的指針域，令其指向下一個非空隊列的隊頭記錄，指針域，令其指向下一個非空隊列的隊頭記錄，重新將重新將1010個隊列鏈成一個鏈表個隊列鏈成一個鏈表第第9章內(nèi)部排序章內(nèi)部排序二、鏈式基數(shù)排序二、鏈式基數(shù)排序76第六節(jié)基數(shù)排序第六節(jié)基數(shù)排序n從最低位至最高位，逐位執(zhí)行上述兩步操作，從最低位至最高位，逐位執(zhí)行上述兩步操作，最后得到一個有序序列最后得到一個有序序列第第9章內(nèi)部排序章內(nèi)部排序二、鏈式基數(shù)排序二、鏈式基數(shù)排序( (舉例舉例) )第六節(jié)基數(shù)排序第六節(jié)基數(shù)排序第第9章內(nèi)部排序章內(nèi)部排序初始狀態(tài)初始狀態(tài)278109063930