東南大學(xué)計(jì)算機(jī)學(xué)院方效林教學(xué)課件

1、東南大學(xué)計(jì)算機(jī)學(xué)院 方效林本課件借鑒了清華大學(xué)殷人昆老師和哈爾濱工業(yè)大學(xué)張巖老師的課件第九章 排序本章主要內(nèi)容排序的概念插入排序順序插入排序折半插入排序希爾排序快速排序選擇排序歸并排序分配排序內(nèi)部排序算法分析2排序的概念定義將一組雜亂無章的數(shù)據(jù)按一定規(guī)律順次排列數(shù)據(jù)表(dataList)待排序數(shù)據(jù)元素的有限集合排序碼(key)通常數(shù)據(jù)元素有多個(gè)屬性，作為排序依據(jù)的屬性稱為排序碼學(xué)生成績表，按學(xué)號小到大排序，按成績高到低排序3排序的概念排序的穩(wěn)定性兩數(shù)據(jù)元素排序碼相同，排序前后兩元素先后順序若相同，則是穩(wěn)定的若不同，則不穩(wěn)定內(nèi)排序和外排序內(nèi)排序所有元素都在存在內(nèi)存的排序外排序數(shù)據(jù)太多，內(nèi)存放不下

2、，而存放在外部存儲(chǔ)器，排序時(shí)需要經(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)定順序插入排序順序插入排序算法將待排序元素，從后向前尋找適當(dāng)?shù)牟迦胛恢?，直到所有元素都插入為?21254925*1608初始21254925*1608第1步21254925*1608第2步21254925*1608第3步212525*491608第4步16212525*4908第5步插入25，25 21，無需移動(dòng)插入49，49 25，無需移動(dòng)插入25*，25* 49，212525*491608插入16，16 49

3、,25*,25,21，16212525*49080816212525*49插入08，08 high，49,25*,25后移，23填入16212525*4923012345lowmidhigh16212525*4923012345lowmidhigh16212525*4923012345lowmidhighmid23,high=mid-1,mid=(low+high)/2mid23,low=mid+1,mid=(low+high)/216212525*4923012345lowmidhighmid23,low=mid+1,mid=(low+high)/2折半插入排序算法分析平均情況下，折半搜索比

4、順序搜索快搜索元素i需比較log2i +1次總比較次數(shù)移動(dòng)的時(shí)間復(fù)雜度O(n2)是穩(wěn)定的排序算法，需額外一個(gè)存儲(chǔ)空間10比較的時(shí)間復(fù)雜度O(n*log2n)希爾排序基本思想設(shè)定不同gap值，距離gap的元素放一起插入排序1121254925*1608初始21254925*1608第1步21254925*160821254925*1608gap= n/3+1 = 3 21160825*2549結(jié)果21160825*2549gap= gap/3+1 = 2 21160825*254908162125*2549結(jié)果08162125*254908162125*2549gap= gap/3+1 = 1

5、結(jié)果第2步第3步最后1步是n個(gè)元素進(jìn)行插入排序是不是很慢？希爾排序算法分析設(shè)定不同gap值，距離gap的元素放一起插入排序gap值越來越小，由于前面的排序過程，使得大多數(shù)數(shù)據(jù)已經(jīng)基本有序，因此希爾排序速度仍然很快gap的取值方法有很多種gap= gap/3+1gap= gap/2希爾排序復(fù)雜度分析很困難，還沒有完整的數(shù)學(xué)分析統(tǒng)計(jì)得出，平均比較和移動(dòng)次數(shù)在n1.25,1.6n1.25內(nèi)是不穩(wěn)定的排序算法12快速排序基本思想Partition：任取一元素x為基準(zhǔn)(如選第1個(gè))，小于x的元素放在x左邊，大于等于x的元素放在x右邊對左、右部分遞歸執(zhí)行上一步驟直至只有一個(gè)元素1321254925*160

6、8初始第1層第2層第3層選21為基準(zhǔn)左部選08，右部選25*為基準(zhǔn)左部選16，右部選25為基準(zhǔn)081621254925*08162125*254908162125*2549第4層右部選49為基準(zhǔn)08162125*2549快速排序Partition(low,high)初始時(shí)基準(zhǔn)坐標(biāo)p = low, x=alow=21從i=low+1位置開始判斷，比x小的元素與p下一個(gè)位置交換，p自加1循環(huán)直至i high，最后alow與ap交換14pppipihigh,停止ialow與ap交換ai與ap+1交換, p+ai與ap+1交換, p+21254925*160821164925*250821160825

7、*254908162125*2549快速排序性能分析快速排序是一個(gè)遞歸算法1621081625*254908162125*2549遞歸樹快速排序性能分析快速排序的趟數(shù)取決于遞歸樹的深度若每次選取的基準(zhǔn)可將序列劃分成長度相近的左、右兩部分，則下一層將對兩個(gè)長度減半的序列排序設(shè)原序列有n個(gè)元素，選基準(zhǔn)和劃分所需時(shí)間為O(n)設(shè)整個(gè)快速排序所需時(shí)間為T(n)，則有：T(n) cn + 2T(n/2) / c 是一個(gè)常數(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

8、) = O(nlog2n )1721081625*2549快速排序性能分析最壞情況單枝樹，每次劃分只得到比上一次少一個(gè)元素的序列比較次數(shù)遞歸樹有n層，存儲(chǔ)開銷為O(n)快速排序是不穩(wěn)定的算法1921081625*2549快速排序改進(jìn)算法快速排序?qū)﹂L度很小的序列排序并不比直接插入快長度取525時(shí)，直接插入法比快速排序法快10%改進(jìn)方法1：在快速排序遞歸過程中，當(dāng)序列長度小于一定值時(shí)，使用直接插入排序法改進(jìn)方法2：在快速排序遞歸過程中，當(dāng)序列長度小于一定值時(shí)，退出排序得到一個(gè)整體上幾乎已經(jīng)排好序的序列對這個(gè)幾乎已經(jīng)排好序的序列使用直接插入排序法20快速排序改進(jìn)算法基準(zhǔn)元素的選取對算法性能有很大影響

9、改進(jìn)方法1：可隨機(jī)選擇一個(gè)元素作為基準(zhǔn)，避免最壞情況發(fā)生改進(jìn)方法2：取左端點(diǎn)、右端點(diǎn)、中點(diǎn)(mid=(left+right)/2)這三個(gè)元素中的中間值作為基準(zhǔn)2121254925*163508左端點(diǎn)右端點(diǎn)中點(diǎn)取21，25*，08三個(gè)元素中的21為基準(zhǔn)選擇排序直接選擇排序在待排序序列中選擇最小的元素xx與第一個(gè)元素對換剔除x，對剩下元素執(zhí)行以上步驟2221254925*1608初始08254925*1621第1步08164925*2521第2步08162125*2549第3步08162125*2549第4步08162125*2549第5步選擇排序直接選擇排序算法分析設(shè)有n個(gè)元素，第i趟比較次數(shù)為

10、n-i-1次總比較次數(shù)為移動(dòng)次數(shù)最好情況為0最壞情況為3(n-1)直接選擇排序是不穩(wěn)定算法23堆排序算法思想建立最大堆循環(huán)執(zhí)行以下步驟，直至所有元素出堆每次堆頂元素(即最大元素)與堆中最后一個(gè)元素交換剔除最大元素后調(diào)整為最大堆49082525*1621i=221254925*1608最后一元素的父節(jié)點(diǎn)i=2開始調(diào)整i=121254925*1608調(diào)整i=1i=0調(diào)整i=021254925*160849082525*162149082525*1621形成最大堆49252125*160821082525*1649堆排序算法思想建立最大堆循環(huán)執(zhí)行以下步驟，直至所有元素出堆每次堆頂元素(即最大元素)與

11、堆中最后一個(gè)元素交換剔除最大元素后調(diào)整為最大堆491625*252121160825*2549堆頂21與堆尾08交換虛線內(nèi)調(diào)整為最大堆084925*2516082125*2549堆頂16與堆尾08交換虛線內(nèi)調(diào)整為最大堆2108164925*2508162125*2549虛線內(nèi)調(diào)整為最大堆211608堆排序堆排序算法分析建立最大堆設(shè)堆中有n個(gè)元素, 對應(yīng)完全二叉樹有k層(2k-1n2k)第i層向下調(diào)整移動(dòng)距離最大為(k-i), 第i層節(jié)點(diǎn)數(shù)為2i-1總移動(dòng)次數(shù)循環(huán)彈出堆頂元素執(zhí)行n-1次向下調(diào)整，每次調(diào)整距離log2(n+1) 總調(diào)整時(shí)間O(nlog2n)堆排序算法的計(jì)算時(shí)間復(fù)雜度為O(nlog

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

13、21.23.39.68.94桶式排序算法分析整個(gè)桶排序時(shí)間復(fù)雜度為將元素分配到各個(gè)桶中的時(shí)間復(fù)雜度為O(n)假設(shè)每個(gè)桶中序列使用直接插入排序，時(shí)間復(fù)雜度為O(ni2)極限情況下，每個(gè)桶放一個(gè)元素，桶排序最好效率為O(n)31基數(shù)排序多排序碼排序花色： 面值：2345678910JQKA排成以下序列就是多排序碼排序2, , A, 2, , A, 2, , A, 2, , A排序后的有序序列稱為字典有序序列可先按花色排序，再按字母排序也可先按字母排序，再按花色排序32基數(shù)排序多排序碼排序最高位優(yōu)先(MSD, Most Significant Digit first)按第1排序碼排序，會(huì)分成若干組遞

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

15、179232332, 361457, 405589633,6647148250591234567890332361012435678945740512346570896336640124356789基數(shù)排序最低位優(yōu)先(LSD)按第d排序碼(最低位)排序?qū)ι弦慌判蚪Y(jié)果按第d-1排序碼(次低位)排序?qū)ι弦慌判蚪Y(jié)果按第d-2排序碼排序，以此類推，直到按第1排序碼完成排序，可得最終排序結(jié)果332633589232664179457825405361012345678936133263358982517966440523245736133223263366482540545758917901234567

16、893613322326336648254054575891794058253322326334573616641795890123456789405825332232633457361664179589179232332361405457589633664825基數(shù)排序算法性能分析n：記錄數(shù)，d：排序碼數(shù)，r：基數(shù)時(shí)間復(fù)雜度：分配操作：O(n),收集操作O(r)，需進(jìn)行d趟分配和收集。時(shí)間復(fù)雜度：O(d(n+r)空間復(fù)雜度：所需輔助空間為隊(duì)首和隊(duì)尾指針2r個(gè)，此外還有為每個(gè)記錄增加的鏈域空間n個(gè)?？臻g復(fù)雜度O(n+r)36各排序方法時(shí)間復(fù)雜度比較37排序方法平均情況最好情況最壞情況直接插入排序O(n2)O(n)O(n2)希爾排序O(nlog2n)O(n1.3)O(n2)起泡排序O(n2)O (n)O(n2)快速排序O(nlog2n)O(nlog2n)O(n2)直接選擇排序O(n2)O(n2)O(n2)