數(shù)據(jù)結(jié)構(gòu)_09_排序

1、東南大學(xué)計算機(jī)學(xué)院東南大學(xué)計算機(jī)學(xué)院 方效林方效林本課件借鑒了清華大學(xué)殷人昆老師和哈爾濱工業(yè)大學(xué)張巖老師的課件第第九九章章 排序排序本章主要內(nèi)容本章主要內(nèi)容n排序的概念排序的概念n插入排序插入排序r順序插入排序順序插入排序r折半插入排序折半插入排序r希爾排序希爾排序n快速排序快速排序n選擇排序選擇排序n歸并排序歸并排序n分配排序分配排序n內(nèi)部排序算法分析內(nèi)部排序算法分析2排序的概念排序的概念n定義定義r將一組雜亂無章的數(shù)據(jù)按一定規(guī)律順次排列將一組雜亂無章的數(shù)據(jù)按一定規(guī)律順次排列n數(shù)據(jù)表數(shù)據(jù)表(dataList)r待排序數(shù)據(jù)元素的有限集合待排序數(shù)據(jù)元素的有限集合n排序碼排序碼(key)r通常數(shù)據(jù)

2、元素有多個屬性，作為排序依據(jù)的屬性通常數(shù)據(jù)元素有多個屬性，作為排序依據(jù)的屬性稱為排序碼稱為排序碼學(xué)生成績表，按學(xué)號小到大排序，按成績高到低排序?qū)W生成績表，按學(xué)號小到大排序，按成績高到低排序3排序的概念排序的概念n排序的穩(wěn)定性排序的穩(wěn)定性r兩數(shù)據(jù)元素排序碼相同，排序前后兩元素先后順兩數(shù)據(jù)元素排序碼相同，排序前后兩元素先后順序序若相同，則是穩(wěn)定的若相同，則是穩(wěn)定的若不同，則不穩(wěn)定若不同，則不穩(wěn)定n內(nèi)排序和外排序內(nèi)排序和外排序r內(nèi)排序內(nèi)排序所有元素都在存在內(nèi)存的排序所有元素都在存在內(nèi)存的排序r外排序外排序數(shù)據(jù)太多，內(nèi)存放不下，而存放在外部存儲器，排序數(shù)據(jù)太多，內(nèi)存放不下，而存放在外部存儲器，排序時需

3、要經(jīng)常在內(nèi)、外存之間讀寫數(shù)據(jù)時需要經(jīng)常在內(nèi)、外存之間讀寫數(shù)據(jù)41(a)2(b)2(c)3(d)1(a)2(c)2(b) 3(d)2(c)1(a)3(d) 2(b)初始初始排序排序1排序排序2穩(wěn)定的穩(wěn)定的不穩(wěn)定不穩(wěn)定排序的概念排序的概念n排序的時間開銷排序的時間開銷r內(nèi)排序一般用數(shù)據(jù)比較次數(shù)和數(shù)據(jù)移動次數(shù)衡量內(nèi)排序一般用數(shù)據(jù)比較次數(shù)和數(shù)據(jù)移動次數(shù)衡量r外排序一般用外存的讀寫次數(shù)衡量外排序一般用外存的讀寫次數(shù)衡量(外存慢外存慢)n排序的空間開銷排序的空間開銷r執(zhí)行排序算法需要的存儲空間執(zhí)行排序算法需要的存儲空間5順序插入排序順序插入排序n順序插入排序算法順序插入排序算法r將待排序元素，從后向前尋找

4、適當(dāng)?shù)牟迦胛恢?，將待排序元素，從后向前尋找適當(dāng)?shù)牟迦胛恢?，直到所有元素都插入為止直到所有元素都插入為?212549 25* 1608初始初始212549 25* 1608第第1步步212549 25* 1608第第2步步212549 25* 1608第第3步步2125 25* 491608第第4步步162125 25* 4908第第5步步插入插入25，25 21，無需移動，無需移動插入插入49，49 25，無需移動，無需移動插入插入25*，25* 49，2125 25* 491608插入插入16，16 49,25*,25,21，162125 25* 490808162125 25* 49插入

5、插入08，08 high，49,25*,25后移，后移，23填入填入162125 25* 4923012345lowmidhigh162125 25* 4923012345low mid high162125 25* 4923012345low mid highmid23,high=mid-1,mid=(low+high)/2mid23,low=mid+1,mid=(low+high)/2162125 25* 4923012345lowmid highmid23,low=mid+1,mid=(low+high)/2折半插入排序折半插入排序n算法分析算法分析r平均情況下，折半搜索比順序搜索快平均

6、情況下，折半搜索比順序搜索快r搜索元素搜索元素i需比較需比較 log2i +1次次r總比較次數(shù)總比較次數(shù)r移動的時間復(fù)雜度移動的時間復(fù)雜度O(n2)r是穩(wěn)定的排序算法，需額外一個存儲空間是穩(wěn)定的排序算法，需額外一個存儲空間10 1k21021n1i2222kkk332211)ilog(1nnlog*n11)n(log*n12*1)(k2*k2*32*22*122k1k210-比較的時間復(fù)雜度比較的時間復(fù)雜度O(n*log2n)希爾排序希爾排序n基本思想基本思想r設(shè)定不同設(shè)定不同gap值，距離值，距離gap的元素放一起插入排序的元素放一起插入排序11212549 25* 1608初始初始2125

7、49 25* 1608第第1步步212549 25* 1608212549 25* 1608gap= n/3 +1 = 3 211608 25* 2549結(jié)果結(jié)果211608 25* 2549gap= gap/3 +1 = 2 211608 25* 2549081621 25* 2549結(jié)果結(jié)果081621 25* 2549081621 25* 2549gap= gap/3 +1 = 1 結(jié)果結(jié)果第第2步步第第3步步最后最后1步是步是n個元素進(jìn)行插入排序個元素進(jìn)行插入排序是不是很慢？是不是很慢？希爾排序希爾排序n算法分析算法分析r設(shè)定不同設(shè)定不同gap值，距離值，距離gap的元素放一起插入排序

8、的元素放一起插入排序gap值越來越小，由于前面的排序過程，使得大多數(shù)值越來越小，由于前面的排序過程，使得大多數(shù)數(shù)據(jù)已經(jīng)基本有序，因此希爾排序速度仍然很快數(shù)據(jù)已經(jīng)基本有序，因此希爾排序速度仍然很快gap的取值方法有很多種的取值方法有很多種gap= gap/3 +1gap= gap/2 希爾排序復(fù)雜度分析很困難，還沒有完整的數(shù)學(xué)分析希爾排序復(fù)雜度分析很困難，還沒有完整的數(shù)學(xué)分析統(tǒng)計得出，平均比較和移動次數(shù)在統(tǒng)計得出，平均比較和移動次數(shù)在n1.25,1.6n1.25內(nèi)內(nèi)是是不穩(wěn)定不穩(wěn)定的排序算法的排序算法12快速排序快速排序n基本思想基本思想rPartition：任取一元素：任取一元素x為基準(zhǔn)為基準(zhǔn)

9、(如選第如選第1個個)，小于，小于x的元素放在的元素放在x左邊，大于等于左邊，大于等于x的元素放在的元素放在x右邊右邊r對左、右部分遞歸執(zhí)行上一步驟直至只有一個元對左、右部分遞歸執(zhí)行上一步驟直至只有一個元素素13212549 25* 1608初始初始第第1層層第第2層層第第3層層選選21為基準(zhǔn)為基準(zhǔn)左部選左部選08，右部選，右部選25*為基準(zhǔn)為基準(zhǔn)左部選左部選16，右部選，右部選25為基準(zhǔn)為基準(zhǔn)081621254925*081621 25* 2549081621 25* 2549第第4層層右部選右部選49為基準(zhǔn)為基準(zhǔn)081621 25* 2549快速排序快速排序nPartition(low,h

10、igh)r初始時基準(zhǔn)坐標(biāo)初始時基準(zhǔn)坐標(biāo)p = low, x=alow=21r從從i=low+1位置開始判斷，比位置開始判斷，比x小的元素與小的元素與p下一個下一個位置交換，位置交換，p自加自加1r循環(huán)直至循環(huán)直至i high，最后，最后alow與與ap交換交換14pppipihigh,停止停止ialow與與ap交換交換ai與與ap+1交換交換, p+ai與與ap+1交換交換, p+212549 25* 1608211649 25* 2508211608 25* 2549081621 25* 254915作業(yè)：作業(yè)：對數(shù)據(jù)對數(shù)據(jù)aN進(jìn)行快速排序的程序進(jìn)行快速排序的程序qsort(a , 0, n

11、-1)快速排序快速排序n性能分析性能分析r快速排序是一個遞歸算法快速排序是一個遞歸算法1621081625*2549081621 25* 2549遞歸樹遞歸樹快速排序快速排序n性能分析性能分析r快速排序的趟數(shù)取決于遞歸樹的深度快速排序的趟數(shù)取決于遞歸樹的深度r若每次選取的基準(zhǔn)可將序列劃分成長度相近的左若每次選取的基準(zhǔn)可將序列劃分成長度相近的左、右兩部分，則下一層將對兩個長度減半的序列、右兩部分，則下一層將對兩個長度減半的序列排序排序設(shè)原序列有設(shè)原序列有n個元素，選基準(zhǔn)和劃分所需時間為個元素，選基準(zhǔn)和劃分所需時間為O(n)設(shè)整個快速排序所需時間為設(shè)整個快速排序所需時間為T(n)，則有：，則有：T

12、(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(nlog2n )1721081625*2549快速排序快速排序n性能分析性能分析r快速排序平均計算時間為快速排序平均計算時間為O(nlog2n)r平均計算時間是所有內(nèi)部排序方法中最好的平均計算時間是所有內(nèi)部排序方法中最好的r遞歸算法每層需保存遞歸調(diào)用的指針和參數(shù)遞歸算法每層需保存遞歸調(diào)用的指針和參數(shù)r平均情況下平均情況下最大遞歸層數(shù)為最大遞

13、歸層數(shù)為 log2(n+1) 存儲開銷為存儲開銷為O(log2n)18快速排序快速排序n性能分析性能分析r最壞情況最壞情況單枝樹，每次劃分只得到比上一次少一個元素的序列單枝樹，每次劃分只得到比上一次少一個元素的序列比較次數(shù)比較次數(shù)遞歸樹有遞歸樹有n層，存儲開銷為層，存儲開銷為O(n)快速排序是不穩(wěn)定的算法快速排序是不穩(wěn)定的算法1921081625*25492n1)n(n21i)(n21n1i快速排序快速排序n改進(jìn)算法改進(jìn)算法r快速排序?qū)焖倥判驅(qū)﹂L度很小的序列長度很小的序列排序并不比直接插入排序并不比直接插入快快r長度取長度取525時，直接插入法比快速排序法快時，直接插入法比快速排序法快10%

14、r改進(jìn)方法改進(jìn)方法1：在快速排序遞歸過程中，當(dāng)序列長度小于一定值時，在快速排序遞歸過程中，當(dāng)序列長度小于一定值時，使用直接插入排序法使用直接插入排序法r改進(jìn)方法改進(jìn)方法2：在快速排序遞歸過程中，當(dāng)序列長度小于一定值時，在快速排序遞歸過程中，當(dāng)序列長度小于一定值時，退出排序退出排序得到一個整體上幾乎已經(jīng)排好序的序列得到一個整體上幾乎已經(jīng)排好序的序列對這個幾乎已經(jīng)排好序的序列使用直接插入排序法對這個幾乎已經(jīng)排好序的序列使用直接插入排序法20快速排序快速排序n改進(jìn)算法改進(jìn)算法r基準(zhǔn)元素的選取對算法性能有很大影響基準(zhǔn)元素的選取對算法性能有很大影響r改進(jìn)方法改進(jìn)方法1：可隨機(jī)選擇一個元素作為基準(zhǔn)，避免最

15、壞情況發(fā)生可隨機(jī)選擇一個元素作為基準(zhǔn)，避免最壞情況發(fā)生r改進(jìn)方法改進(jìn)方法2：取左端點(diǎn)、右端點(diǎn)、中點(diǎn)取左端點(diǎn)、右端點(diǎn)、中點(diǎn)(mid= (left+right)/2 )這三這三個元素中的中間值作為基準(zhǔn)個元素中的中間值作為基準(zhǔn)21212549 25* 163508左端點(diǎn)左端點(diǎn)右端點(diǎn)右端點(diǎn)中點(diǎn)中點(diǎn)取取21，25*，08三個元素中的三個元素中的21為基準(zhǔn)為基準(zhǔn)選擇排序選擇排序n直接選擇排序直接選擇排序r在待排序序列中選擇最小的元素在待排序序列中選擇最小的元素xrx與第一個元素對換與第一個元素對換r剔除剔除x，對剩下元素執(zhí)行以上步驟，對剩下元素執(zhí)行以上步驟22212549 25* 1608初始初始0825

16、49 25* 1621第第1步步081649 25* 2521第第2步步081621 25* 2549第第3步步081621 25* 2549第第4步步081621 25* 2549第第5步步選擇排序選擇排序n直接選擇排序直接選擇排序r算法分析算法分析設(shè)有設(shè)有n個元素，第個元素，第i趟比較次數(shù)為趟比較次數(shù)為n-i-1次次總比較次數(shù)為總比較次數(shù)為移動次數(shù)移動次數(shù)最好情況為最好情況為0最壞情況為最壞情況為3(n-1)直接選擇排序是不穩(wěn)定算法直接選擇排序是不穩(wěn)定算法232n0i21)n(n1)i(nKCN堆排序堆排序n算法思想算法思想r建立最大堆建立最大堆r循環(huán)執(zhí)行以下步驟，直至所有元素出堆循環(huán)執(zhí)行

17、以下步驟，直至所有元素出堆每次堆頂元素每次堆頂元素(即最大元素即最大元素)與堆中最后一個元素交換與堆中最后一個元素交換剔除最大元素后調(diào)整為最大堆剔除最大元素后調(diào)整為最大堆49082525* 1621i=221 25 4925*16 08最后一元素的父節(jié)點(diǎn)最后一元素的父節(jié)點(diǎn)i=2開始調(diào)整開始調(diào)整i=121 25 4925*16 08調(diào)整調(diào)整i=1i=0調(diào)整調(diào)整i=021 25 4925*16 0849082525* 162149082525* 1621形成最大堆形成最大堆49 25 2125*16 0821082525* 1649堆排序堆排序n算法思想算法思想r建立最大堆建立最大堆r循環(huán)執(zhí)行以下

18、步驟，直至所有元素出堆循環(huán)執(zhí)行以下步驟，直至所有元素出堆每次堆頂元素每次堆頂元素(即最大元素即最大元素)與堆中最后一個元素交換與堆中最后一個元素交換剔除最大元素后調(diào)整為最大堆剔除最大元素后調(diào)整為最大堆堆頂堆頂49與堆尾與堆尾08交換交換49 25 2125*16 08212525* 164908214925*0816252525*21 08 16 49虛線內(nèi)調(diào)整為最大堆虛線內(nèi)調(diào)整為最大堆堆頂堆頂25與堆尾與堆尾16交換交換虛線內(nèi)調(diào)整為最大堆虛線內(nèi)調(diào)整為最大堆214916082525*25*16 21 08 25 49堆頂堆頂25*與堆尾與堆尾08交換交換虛線內(nèi)調(diào)整為最大堆虛線內(nèi)調(diào)整為最大堆堆排

19、序堆排序n算法思想算法思想r建立最大堆建立最大堆r循環(huán)執(zhí)行以下步驟，直至所有元素出堆循環(huán)執(zhí)行以下步驟，直至所有元素出堆每次堆頂元素每次堆頂元素(即最大元素即最大元素)與堆中最后一個元素交換與堆中最后一個元素交換剔除最大元素后調(diào)整為最大堆剔除最大元素后調(diào)整為最大堆491625* 252121 16 0825*25 49堆頂堆頂21與堆尾與堆尾08交換交換虛線內(nèi)調(diào)整為最大堆虛線內(nèi)調(diào)整為最大堆084925* 2516 08 2125*25 49堆頂堆頂16與堆尾與堆尾08交換交換虛線內(nèi)調(diào)整為最大堆虛線內(nèi)調(diào)整為最大堆2108164925* 2508 16 2125*25 49虛線內(nèi)調(diào)整為最大堆虛線內(nèi)調(diào)

20、整為最大堆211608堆排序堆排序n堆排序算法分析堆排序算法分析r建立最大堆建立最大堆設(shè)堆中有設(shè)堆中有n個元素個元素, 對應(yīng)完全二叉樹有對應(yīng)完全二叉樹有k層層(2k-1n2k)第第i層向下調(diào)整移動距離最大為層向下調(diào)整移動距離最大為(k-i), 第第i層節(jié)點(diǎn)數(shù)為層節(jié)點(diǎn)數(shù)為2i-1總移動次數(shù)總移動次數(shù)r循環(huán)彈出堆頂元素循環(huán)彈出堆頂元素執(zhí)行執(zhí)行n-1次向下調(diào)整，每次調(diào)整距離次向下調(diào)整，每次調(diào)整距離 log2(n+1) 總調(diào)整時間總調(diào)整時間O(nlog2n) ) )( (k kn nO O 1k1i1- ii22堆排序算法的計算時間復(fù)雜度為堆排序算法的計算時間復(fù)雜度為O(nlog2n)是不穩(wěn)定排序是不

21、穩(wěn)定排序歸并排序歸并排序n算法思想算法思想r將序列分成兩個長度相等的子序列將序列分成兩個長度相等的子序列r分別對兩個子序列排序分別對兩個子序列排序r將排好序的兩個子序列合并將排好序的兩個子序列合并28212549 25*1608314121 25 4925*16 08 31 4121 25 4925*16 08 31 4121 254925*16 0831 41212549 25*1608314108 16 21 2525*31 41 4921 2525*4908 16 31 4121 2525*4908 1631 41歸并排序歸并排序n算法分析算法分析r計算時間包括計算時間包括對兩個子序列分

22、別排序時間對兩個子序列分別排序時間歸并的時間歸并的時間rT(n) = cn+2T(n/2) = O(nlog2n)r最好、最壞、平均時間復(fù)雜度均為最好、最壞、平均時間復(fù)雜度均為O(nlog2n)r是穩(wěn)定排序是穩(wěn)定排序29桶式排序桶式排序n基本思想基本思想r輸入：在輸入：在0,1)區(qū)間內(nèi)均勻分布的隨機(jī)序列區(qū)間內(nèi)均勻分布的隨機(jī)序列將區(qū)間將區(qū)間0,1)劃分成一系列桶劃分成一系列桶(等長子區(qū)間等長子區(qū)間)，如，如0, 0.1), 0.1, 0.2), , 0.9, 1)對屬于桶內(nèi)的序列分別排序，按桶的編號依次輸出對屬于桶內(nèi)的序列分別排序，按桶的編號依次輸出300123456789.72 .78.12

23、.17.21 .23 .26.39.68.94.78.17.39.26.72.94.21.12.23.680123456789.78 .72.17 .12.26 .21 .23.39.68.94桶式排序桶式排序n算法分析算法分析r整個桶排序時間復(fù)雜度為整個桶排序時間復(fù)雜度為將元素分配到各個桶中的時間復(fù)雜度為將元素分配到各個桶中的時間復(fù)雜度為O(n)假設(shè)每個桶中序列使用直接插入排序，時間復(fù)雜度為假設(shè)每個桶中序列使用直接插入排序，時間復(fù)雜度為O(ni2)r極限情況下，每個桶放一個元素，桶排序最好效極限情況下，每個桶放一個元素，桶排序最好效率為率為O(n)31)O(n)O(nO(n)2n1i2i 基

24、數(shù)排序基數(shù)排序n多排序碼排序多排序碼排序r花色：花色： r面值：面值：2345678910JQKAr排成以下序列就是多排序碼排序排成以下序列就是多排序碼排序 2, , A, 2, , A, 2, , A, 2, , Ar排序后的有序序列稱為字典有序序列排序后的有序序列稱為字典有序序列可先按花色排序，再按字母排序可先按花色排序，再按字母排序也可先按字母排序，再按花色排序也可先按字母排序，再按花色排序32基數(shù)排序基數(shù)排序n多排序碼排序多排序碼排序r最高位優(yōu)先最高位優(yōu)先(MSD, Most Significant Digit first)按第按第1排序碼排序，會分成若干組排序碼排序，會分成若干組遞歸

25、遞歸對各組按第對各組按第2,3,d排序碼排序排序碼排序最后把所有子組元素依次連接起來形成有序序列最后把所有子組元素依次連接起來形成有序序列r最低位優(yōu)先最低位優(yōu)先(LSD, Least Significant Digit first)按第按第d排序碼排序碼(最低位最低位)排序排序?qū)ι弦慌判蚪Y(jié)果按第對上一排序結(jié)果按第d-1排序碼排序碼(次低位次低位)排序排序?qū)ι弦慌判蚪Y(jié)果按第對上一排序結(jié)果按第d-2排序碼排序，以此類推，直到排序碼排序，以此類推，直到按第按第1排序碼完成排序，可得最終排序結(jié)果排序碼完成排序，可得最終排序結(jié)果33基數(shù)排序基數(shù)排序n多排序碼排序多排序碼排序r最高位優(yōu)先最高位優(yōu)先(MSD

26、, Most Significant Digit first)按第按第1排序碼排序，會分成若干組排序碼排序，會分成若干組遞歸遞歸對各組按第對各組按第2,3,d排序碼排序排序碼排序最后把所有子組元素依次連接起來形成有序序列最后把所有子組元素依次連接起來形成有序序列34332 633 059 589 232 664 179 457 825 714 405 361179 232 332, 361 457, 405 589633,664714 82505912345678903323610 1 243567 8 94574051 2 3 465708 96336640 1 243567 8 9基數(shù)排序基數(shù)排序n最低位優(yōu)先最低位優(yōu)先(LSD)r按第按第d排序碼排序碼(最低位最低位)排序排序r對上一排序結(jié)果按第對上一排序結(jié)果按第d-1排序碼排序碼(次低位次低位)排序排序r對上一排序結(jié)果按第對上一排序結(jié)果按第d-2排序碼排序，以此類推，直到按排序碼排序，以此類推，直到按第第1排序碼完成排序，可得最終排序結(jié)果排序碼完成排序，可得最終排序結(jié)果33263358923266417945782540536101234567893613326335898251796644052324573613322326336648254054575891790123456789361332 232 63