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

數(shù)據(jù)結(jié)構(gòu)排序第1頁，共35頁，2023年，2月20日，星期五本章主要內(nèi)容排序的概念插入排序順序插入排序折半插入排序希爾排序快速排序選擇排序歸并排序分配排序內(nèi)部排序算法分析第2頁，共35頁，2023年，2月20日，星期五排序的概念定義將一組雜亂無章的數(shù)據(jù)按一定規(guī)律順次排列數(shù)據(jù)表(dataList)待排序數(shù)據(jù)元素的有限集合排序碼(key)通常數(shù)據(jù)元素有多個屬性，作為排序依據(jù)的屬性稱為排序碼學(xué)生成績表，按學(xué)號小到大排序，按成績高到低排序第3頁，共35頁，2023年，2月20日，星期五排序的概念排序的穩(wěn)定性兩數(shù)據(jù)元素排序碼相同，排序前后兩元素先后順序若相同，則是穩(wěn)定的若不同，則不穩(wěn)定內(nèi)排序和外排序內(nèi)排序所有元素都在存在內(nèi)存的排序外排序數(shù)據(jù)太多，內(nèi)存放不下，而存放在外部存儲器，排序時需要經(jīng)常在內(nèi)、外存之間讀寫數(shù)據(jù)1(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)定第4頁，共35頁，2023年，2月20日，星期五排序的概念排序的時間開銷內(nèi)排序一般用數(shù)據(jù)比較次數(shù)和數(shù)據(jù)移動次數(shù)衡量外排序一般用外存的讀寫次數(shù)衡量(外存慢)排序的空間開銷執(zhí)行排序算法需要的存儲空間第5頁，共35頁，2023年，2月20日，星期五順序插入排序順序插入排序算法將待排序元素，從后向前尋找適當(dāng)?shù)牟迦胛恢?，直到所有元素都插入為?1254925*1608初始21254925*1608第1步21254925*1608第2步21254925*1608第3步212525*491608第4步16212525*4908第5步插入25，25≥21，無需移動插入49，49≥25，無需移動插入25*，25*<49，212525*491608插入16，16<49,25*,25,21，16212525*49080816212525*49插入08，08<49,25*,25,21,16，49后移，25*填入49,25*,25,21后移，16填入49,25*,25,21,16后移，08填入第6頁，共35頁，2023年，2月20日，星期五順序插入排序算法分析最好情況(n個元素)原數(shù)據(jù)是按小到大順序排好的每步只需與前一個數(shù)據(jù)比較一次，而不用移動數(shù)據(jù)總比較次數(shù)n-1，總移動次數(shù)0最壞情況(n個元素,i=0,1,…,n-1)原數(shù)據(jù)按大到小順序排好的元素i需要比較i次，每比較1次移動1次，元素i移動2次總比較次數(shù)和總移動次數(shù)temp=a[i]a[0]=temp比較和移動最壞最好平均值約為n2/4時間復(fù)雜度O(n2)第7頁，共35頁，2023年，2月20日，星期五順序插入排序算法分析是穩(wěn)定的算法，key相同元素原來的順序不會打亂需要額外一個存儲空間21254925*1608初始0816212525*49排序后temp=a[i]a[0]=temp第8頁，共35頁，2023年，2月20日，星期五折半插入排序折半插入排序算法將待排序元素，按折半搜索法尋找適當(dāng)?shù)牟迦胛恢?，直到所有元素都插入為?621232525*49low>high，49,25*,25后移，23填入16212525*4923012345lowmidhigh16212525*4923012345lowmidhigh16212525*4923012345lowmidhighmid>23,high=mid-1,mid=(low+high)/2mid≤23,low=mid+1,mid=(low+high)/216212525*4923012345lowmidhighmid≤23,low=mid+1,mid=(low+high)/2第9頁，共35頁，2023年，2月20日，星期五折半插入排序算法分析平均情況下，折半搜索比順序搜索快搜索元素i需比較log2i+1次總比較次數(shù)移動的時間復(fù)雜度O(n2)是穩(wěn)定的排序算法，需額外一個存儲空間比較的時間復(fù)雜度O(n*log2n)第10頁，共35頁，2023年，2月20日，星期五希爾排序基本思想設(shè)定不同gap值，距離gap的元素放一起插入排序21254925*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

結(jié)果第2步第3步最后1步是n個元素進行插入排序是不是很慢？第11頁，共35頁，2023年，2月20日，星期五希爾排序算法分析設(shè)定不同gap值，距離gap的元素放一起插入排序gap值越來越小，由于前面的排序過程，使得大多數(shù)數(shù)據(jù)已經(jīng)基本有序，因此希爾排序速度仍然很快gap的取值方法有很多種gap=gap/3+1gap=gap/2……希爾排序復(fù)雜度分析很困難，還沒有完整的數(shù)學(xué)分析統(tǒng)計得出，平均比較和移動次數(shù)在[n1.25,1.6n1.25]內(nèi)是不穩(wěn)定的排序算法第12頁，共35頁，2023年，2月20日，星期五快速排序基本思想Partition：任取一元素x為基準(zhǔn)(如選第1個)，小于x的元素放在x左邊，大于等于x的元素放在x右邊對左、右部分遞歸執(zhí)行上一步驟直至只有一個元素21254925*1608初始第1層第2層第3層選21為基準(zhǔn)左部選08，右部選25*為基準(zhǔn)左部選16，右部選25為基準(zhǔn)081621254925*08162125*254908162125*2549第4層右部選49為基準(zhǔn)08162125*2549第13頁，共35頁，2023年，2月20日，星期五快速排序Partition(low,high)初始時基準(zhǔn)坐標(biāo)p=low,x=a[low]=21從i=low+1位置開始判斷，比x小的元素與p下一個位置交換，p自加1循環(huán)直至i>high，最后a[low]與a[p]交換pppipi>high,停止ia[low]與a[p]交換a[i]與a[p+1]交換,p++a[i]與a[p+1]交換,p++21254925*160821164925*250821160825*254908162125*2549第14頁，共35頁，2023年，2月20日，星期五作業(yè)：對數(shù)據(jù)a[N]進行快速排序的程序qsort(a[],0,n-1)第15頁，共35頁，2023年，2月20日，星期五快速排序性能分析快速排序是一個遞歸算法21081625*254908162125*2549遞歸樹第16頁，共35頁，2023年，2月20日，星期五快速排序性能分析快速排序的趟數(shù)取決于遞歸樹的深度若每次選取的基準(zhǔn)可將序列劃分成長度相近的左、右兩部分，則下一層將對兩個長度減半的序列排序設(shè)原序列有n個元素，選基準(zhǔn)和劃分所需時間為O(n)設(shè)整個快速排序所需時間為T(n)，則有：T(n)≤cn+2T(n/2)//c是一個常數(shù)≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)≤2cn+4(cn/4+2T(n/8))=3cn+8T(n/8)………≤cnlog2n+nT(1)=O(nlog2n)21081625*2549第17頁，共35頁，2023年，2月20日，星期五快速排序性能分析快速排序平均計算時間為O(nlog2n)平均計算時間是所有內(nèi)部排序方法中最好的遞歸算法每層需保存遞歸調(diào)用的指針和參數(shù)平均情況下最大遞歸層數(shù)為log2(n+1)存儲開銷為O(log2n)第18頁，共35頁，2023年，2月20日，星期五快速排序性能分析最壞情況單枝樹，每次劃分只得到比上一次少一個元素的序列比較次數(shù)遞歸樹有n層，存儲開銷為O(n)快速排序是不穩(wěn)定的算法21081625*2549第19頁，共35頁，2023年，2月20日，星期五快速排序改進算法快速排序?qū)﹂L度很小的序列排序并不比直接插入快長度取5~25時，直接插入法比快速排序法快10%改進方法1：在快速排序遞歸過程中，當(dāng)序列長度小于一定值時，使用直接插入排序法改進方法2：在快速排序遞歸過程中，當(dāng)序列長度小于一定值時，退出排序得到一個整體上幾乎已經(jīng)排好序的序列對這個幾乎已經(jīng)排好序的序列使用直接插入排序法第20頁，共35頁，2023年，2月20日，星期五快速排序改進算法基準(zhǔn)元素的選取對算法性能有很大影響改進方法1：可隨機選擇一個元素作為基準(zhǔn)，避免最壞情況發(fā)生改進方法2：取左端點、右端點、中點(mid=(left+right)/2)這三個元素中的中間值作為基準(zhǔn)21254925*163508左端點右端點中點取21，25*，08三個元素中的21為基準(zhǔn)第21頁，共35頁，2023年，2月20日，星期五選擇排序直接選擇排序在待排序序列中選擇最小的元素xx與第一個元素對換剔除x，對剩下元素執(zhí)行以上步驟21254925*1608初始08254925*1621第1步08164925*2521第2步08162125*2549第3步08162125*2549第4步08162125*2549第5步第22頁，共35頁，2023年，2月20日，星期五選擇排序直接選擇排序算法分析設(shè)有n個元素，第i趟比較次數(shù)為n-i-1次總比較次數(shù)為移動次數(shù)最好情況為0最壞情況為3(n-1)直接選擇排序是不穩(wěn)定算法第23頁，共35頁，2023年，2月20日，星期五堆排序算法思想建立最大堆循環(huán)執(zhí)行以下步驟，直至所有元素出堆每次堆頂元素(即最大元素)與堆中最后一個元素交換剔除最大元素后調(diào)整為最大堆49082525*1621i=221254925*1608最后一元素的父節(jié)點i=2開始調(diào)整i=121254925*1608調(diào)整i=1i=0調(diào)整i=021254925*160849082525*162149082525*1621形成最大堆49252125*160821082525*1649第24頁，共35頁，2023年，2月20日，星期五堆排序算法思想建立最大堆循環(huán)執(zhí)行以下步驟，直至所有元素出堆每次堆頂元素(即最大元素)與堆中最后一個元素交換剔除最大元素后調(diào)整為最大堆堆頂49與堆尾08交換49252125*1608212525*164908214925*0816252525*21081649虛線內(nèi)調(diào)整為最大堆堆頂25與堆尾16交換虛線內(nèi)調(diào)整為最大堆214916082525*25*1621082549堆頂25*與堆尾08交換虛線內(nèi)調(diào)整為最大堆第25頁，共35頁，2023年，2月20日，星期五堆排序算法思想建立最大堆循環(huán)執(zhí)行以下步驟，直至所有元素出堆每次堆頂元素(即最大元素)與堆中最后一個元素交換剔除最大元素后調(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第26頁，共35頁，2023年，2月20日，星期五堆排序堆排序算法分析建立最大堆設(shè)堆中有n個元素,對應(yīng)完全二叉樹有k層(2k-1≤n＜2k)第i層向下調(diào)整移動距離最大為(k-i),第i層節(jié)點數(shù)為2i-1總移動次數(shù)循環(huán)彈出堆頂元素執(zhí)行n-1次向下調(diào)整，每次調(diào)整距離log2(n+1)總調(diào)整時間O(nlog2n)堆排序算法的計算時間復(fù)雜度為O(nlog2n)是不穩(wěn)定排序第27頁，共35頁，2023年，2月20日，星期五歸并排序算法思想將序列分成兩個長度相等的子序列分別對兩個子序列排序?qū)⑴藕眯虻膬蓚€子序列合并21254925*1608314121254925*1608314121254925*1608314121254925*1608314121254925*160831410816212525*314149212525*4908163141212525*4908163141第28頁，共35頁，2023年，2月20日，星期五歸并排序算法分析計算時間包括對兩個子序列分別排序時間歸并的時間T(n)=cn+2T(n/2)=O(nlog2n)最好、最壞、平均時間復(fù)雜度均為O(nlog2n)是穩(wěn)定排序第29頁，共35頁，2023年，2月20日，星期五桶式排序基本思想輸入：在[0,1)區(qū)間內(nèi)均勻分布的隨機序列將區(qū)間[0,1)劃分成一系列桶(等長子區(qū)間)，如[0,0.1),[0.1,0.2),…,[0.9,1)對屬于桶內(nèi)的序列分別排序，按桶的編號依次輸出0123456789.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.21.23.39.68.94第30頁，共35頁，2023年，2月20日，星期五桶式排序算法分析整個桶排序時間復(fù)雜度為將元素分配到各個桶中的時間復(fù)雜度為O(n)假設(shè)每個桶中序列使用直接插入排序，時間復(fù)雜度為O(ni2)極限情況下，每個桶放一個元素，桶排序最好效率為O(n)第31頁，共35頁，2023年，2月20日，星期五基數(shù)排序多排序碼排序花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A排成以下序列就是多排序碼排序2,…,A,

2,…,A,

2,…,A,

2,…,A排序后的有序序列稱為字典有序序列可先按花色排序，再按字母排序也可先按字母排序，再按花色排序第32頁，共35頁，2023年，2月20日，星期五基數(shù)排序多排序碼排序最高位優(yōu)先(MSD,MostSignificantDigitfirst)按第1排序碼排序，會分成若干組遞歸對各組按第2,3,…,d排序碼排序最后把所有子組元素依次連接起來形成有序序列最低位優(yōu)先(LSD,LeastSignificantDigitfirst)按第d排序碼(最低位)排序?qū)ι弦慌判蚪Y(jié)果按第d-1排序碼(次低位)排序?qū)ι弦慌判蚪Y(jié)果按第d-2排序碼排序，以此類推，直到按第1排序碼完成排序，可得最終排序結(jié)果第33頁，共35頁，2023年，2月20日，星期五基數(shù)排序