數(shù)據(jù)結(jié)構(gòu)排序第1頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月本章主要內(nèi)容排序的概念插入排序順序插入排序折半插入排序希爾排序快速排序選擇排序歸并排序分配排序內(nèi)部排序算法分析第2頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月排序的概念定義將一組雜亂無(wú)章的數(shù)據(jù)按一定規(guī)律順次排列數(shù)據(jù)表(dataList)待排序數(shù)據(jù)元素的有限集合排序碼(key)通常數(shù)據(jù)元素有多個(gè)屬性，作為排序依據(jù)的屬性稱(chēng)為排序碼學(xué)生成績(jī)表，按學(xué)號(hào)小到大排序，按成績(jī)高到低排序第3頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月排序的概念排序的穩(wěn)定性?xún)蓴?shù)據(jù)元素排序碼相同，排序前后兩元素先后順序若相同，則是穩(wěn)定的若不同，則不穩(wěn)定內(nèi)排序和外排序內(nèi)排序所有元素都在存在內(nèi)存的排序外排序數(shù)據(jù)太多，內(nèi)存放不下，而存放在外部存儲(chǔ)器，排序時(shí)需要經(jīng)常在內(nèi)、外存之間讀寫(xiě)數(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頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月排序的概念排序的時(shí)間開(kāi)銷(xiāo)內(nèi)排序一般用數(shù)據(jù)比較次數(shù)和數(shù)據(jù)移動(dòng)次數(shù)衡量外排序一般用外存的讀寫(xiě)次數(shù)衡量(外存慢)排序的空間開(kāi)銷(xiāo)執(zhí)行排序算法需要的存儲(chǔ)空間第5頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月順序插入排序順序插入排序算法將待排序元素，從后向前尋找適當(dāng)?shù)牟迦胛恢?，直到所有元素都插入為?1254925*1608初始21254925*1608第1步21254925*1608第2步21254925*1608第3步212525*491608第4步16212525*4908第5步插入25，25≥21，無(wú)需移動(dòng)插入49，49≥25，無(wú)需移動(dòng)插入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頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月順序插入排序算法分析最好情況(n個(gè)元素)原數(shù)據(jù)是按小到大順序排好的每步只需與前一個(gè)數(shù)據(jù)比較一次，而不用移動(dòng)數(shù)據(jù)總比較次數(shù)n-1，總移動(dòng)次數(shù)0最壞情況(n個(gè)元素,i=0,1,…,n-1)原數(shù)據(jù)按大到小順序排好的元素i需要比較i次，每比較1次移動(dòng)1次，元素i移動(dòng)2次總比較次數(shù)和總移動(dòng)次數(shù)temp=a[i]a[0]=temp比較和移動(dòng)最壞最好平均值約為n2/4時(shí)間復(fù)雜度O(n2)第7頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月順序插入排序算法分析是穩(wěn)定的算法，key相同元素原來(lái)的順序不會(huì)打亂需要額外一個(gè)存儲(chǔ)空間21254925*1608初始0816212525*49排序后temp=a[i]a[0]=temp第8頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月折半插入排序折半插入排序算法將待排序元素，按折半搜索法尋找適當(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頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月折半插入排序算法分析平均情況下，折半搜索比順序搜索快搜索元素i需比較log2i+1次總比較次數(shù)移動(dòng)的時(shí)間復(fù)雜度O(n2)是穩(wěn)定的排序算法，需額外一個(gè)存儲(chǔ)空間比較的時(shí)間復(fù)雜度O(n*log2n)第10頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月希爾排序基本思想設(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個(gè)元素進(jìn)行插入排序是不是很慢？第11頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月希爾排序算法分析設(shè)定不同gap值，距離gap的元素放一起插入排序gap值越來(lái)越小，由于前面的排序過(guò)程，使得大多數(shù)數(shù)據(jù)已經(jīng)基本有序，因此希爾排序速度仍然很快gap的取值方法有很多種gap=gap/3+1gap=gap/2……希爾排序復(fù)雜度分析很困難，還沒(méi)有完整的數(shù)學(xué)分析統(tǒng)計(jì)得出，平均比較和移動(dòng)次數(shù)在[n1.25,1.6n1.25]內(nèi)是不穩(wěn)定的排序算法第12頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月快速排序基本思想Partition：任取一元素x為基準(zhǔn)(如選第1個(gè))，小于x的元素放在x左邊，大于等于x的元素放在x右邊對(duì)左、右部分遞歸執(zhí)行上一步驟直至只有一個(gè)元素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頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月快速排序Partition(low,high)初始時(shí)基準(zhǔn)坐標(biāo)p=low,x=a[low]=21從i=low+1位置開(kāi)始判斷，比x小的元素與p下一個(gè)位置交換，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頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月作業(yè)：對(duì)數(shù)據(jù)a[N]進(jìn)行快速排序的程序qsort(a[],0,n-1)第15頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月快速排序性能分析快速排序是一個(gè)遞歸算法21081625*254908162125*2549遞歸樹(shù)第16頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月快速排序性能分析快速排序的趟數(shù)取決于遞歸樹(shù)的深度若每次選取的基準(zhǔn)可將序列劃分成長(zhǎng)度相近的左、右兩部分，則下一層將對(duì)兩個(gè)長(zhǎng)度減半的序列排序設(shè)原序列有n個(gè)元素，選基準(zhǔn)和劃分所需時(shí)間為O(n)設(shè)整個(gè)快速排序所需時(shí)間為T(mén)(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)………≤cnlog2n+nT(1)=O(nlog2n)21081625*2549第17頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月快速排序性能分析快速排序平均計(jì)算時(shí)間為O(nlog2n)平均計(jì)算時(shí)間是所有內(nèi)部排序方法中最好的遞歸算法每層需保存遞歸調(diào)用的指針和參數(shù)平均情況下最大遞歸層數(shù)為log2(n+1)存儲(chǔ)開(kāi)銷(xiāo)為O(log2n)第18頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月快速排序性能分析最壞情況單枝樹(shù)，每次劃分只得到比上一次少一個(gè)元素的序列比較次數(shù)遞歸樹(shù)有n層，存儲(chǔ)開(kāi)銷(xiāo)為O(n)快速排序是不穩(wěn)定的算法21081625*2549第19頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月快速排序改進(jìn)算法快速排序?qū)﹂L(zhǎng)度很小的序列排序并不比直接插入快長(zhǎng)度取5~25時(shí)，直接插入法比快速排序法快10%改進(jìn)方法1：在快速排序遞歸過(guò)程中，當(dāng)序列長(zhǎng)度小于一定值時(shí)，使用直接插入排序法改進(jìn)方法2：在快速排序遞歸過(guò)程中，當(dāng)序列長(zhǎng)度小于一定值時(shí)，退出排序得到一個(gè)整體上幾乎已經(jīng)排好序的序列對(duì)這個(gè)幾乎已經(jīng)排好序的序列使用直接插入排序法第20頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月快速排序改進(jìn)算法基準(zhǔn)元素的選取對(duì)算法性能有很大影響改進(jìn)方法1：可隨機(jī)選擇一個(gè)元素作為基準(zhǔn)，避免最壞情況發(fā)生改進(jìn)方法2：取左端點(diǎn)、右端點(diǎn)、中點(diǎn)(mid=(left+right)/2)這三個(gè)元素中的中間值作為基準(zhǔn)21254925*163508左端點(diǎn)右端點(diǎn)中點(diǎn)取21，25*，08三個(gè)元素中的21為基準(zhǔn)第21頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月選擇排序直接選擇排序在待排序序列中選擇最小的元素xx與第一個(gè)元素對(duì)換剔除x，對(duì)剩下元素執(zhí)行以上步驟21254925*1608初始08254925*1621第1步08164925*2521第2步08162125*2549第3步08162125*2549第4步08162125*2549第5步第22頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月選擇排序直接選擇排序算法分析設(shè)有n個(gè)元素，第i趟比較次數(shù)為n-i-1次總比較次數(shù)為移動(dòng)次數(shù)最好情況為0最壞情況為3(n-1)直接選擇排序是不穩(wěn)定算法第23頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月堆排序算法思想建立最大堆循環(huán)執(zhí)行以下步驟，直至所有元素出堆每次堆頂元素(即最大元素)與堆中最后一個(gè)元素交換剔除最大元素后調(diào)整為最大堆49082525*1621i=221254925*1608最后一元素的父節(jié)點(diǎn)i=2開(kāi)始調(diào)整i=121254925*1608調(diào)整i=1i=0調(diào)整i=021254925*160849082525*162149082525*1621形成最大堆49252125*160821082525*1649第24頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月堆排序算法思想建立最大堆循環(huán)執(zhí)行以下步驟，直至所有元素出堆每次堆頂元素(即最大元素)與堆中最后一個(gè)元素交換剔除最大元素后調(diào)整為最大堆堆頂49與堆尾08交換49252125*1608212525*164908214925*0816252525*21081649虛線(xiàn)內(nèi)調(diào)整為最大堆堆頂25與堆尾16交換虛線(xiàn)內(nèi)調(diào)整為最大堆214916082525*25*1621082549堆頂25*與堆尾08交換虛線(xiàn)內(nèi)調(diào)整為最大堆第25頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月堆排序算法思想建立最大堆循環(huán)執(zhí)行以下步驟，直至所有元素出堆每次堆頂元素(即最大元素)與堆中最后一個(gè)元素交換剔除最大元素后調(diào)整為最大堆491625*252121160825*2549堆頂21與堆尾08交換虛線(xiàn)內(nèi)調(diào)整為最大堆084925*2516082125*2549堆頂16與堆尾08交換虛線(xiàn)內(nèi)調(diào)整為最大堆2108164925*2508162125*2549虛線(xiàn)內(nèi)調(diào)整為最大堆211608第26頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月堆排序堆排序算法分析建立最大堆設(shè)堆中有n個(gè)元素,對(duì)應(yīng)完全二叉樹(shù)有k層(2k-1≤n＜2k)第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(nlog2n)是不穩(wěn)定排序第27頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月歸并排序算法思想將序列分成兩個(gè)長(zhǎng)度相等的子序列分別對(duì)兩個(gè)子序列排序?qū)⑴藕眯虻膬蓚€(gè)子序列合并21254925*1608314121254925*1608314121254925*1608314121254925*1608314121254925*160831410816212525*314149212525*4908163141212525*4908163141第28頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月歸并排序算法分析計(jì)算時(shí)間包括對(duì)兩個(gè)子序列分別排序時(shí)間歸并的時(shí)間T(n)=cn+2T(n/2)=O(nlog2n)最好、最壞、平均時(shí)間復(fù)雜度均為O(nlog2n)是穩(wěn)定排序第29頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月桶式排序基本思想輸入：在[0,1)區(qū)間內(nèi)均勻分布的隨機(jī)序列將區(qū)間[0,1)劃分成一系列桶(等長(zhǎng)子區(qū)間)，如[0,0.1),[0.1,0.2),…,[0.9,1)對(duì)屬于桶內(nèi)的序列分別排序，按桶的編號(hào)依次輸出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頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月桶式排序算法分析整個(gè)桶排序時(shí)間復(fù)雜度為將元素分配到各個(gè)桶中的時(shí)間復(fù)雜度為O(n)假設(shè)每個(gè)桶中序列使用直接插入排序，時(shí)間復(fù)雜度為O(ni2)極限情況下，每個(gè)桶放一個(gè)元素，桶排序最好效率為O(n)第31頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月基數(shù)排序多排序碼排序花色：

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

2,…,A,

2,…,A,

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