2016數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)課件第8章排序

第8章排序

教學(xué)內(nèi)容8.1概述8.2插入排序8.3交換排序8.4選擇排序8.5歸并排序8.6基數(shù)排序8.7外部排序21254925*16081.掌握排序的基本概念和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用2.熟練掌握直接插入排序、折半插入排序、起泡排序、直接選擇排序、快速排序的排序算法及其性能分析3.掌握希爾排序、歸并排序、堆排序、基數(shù)排序的方法及其性能分析4.掌握外部排序方法中敗者樹(shù)的建立及歸并方法，掌握置換-選擇排序的過(guò)程和最佳歸并樹(shù)的構(gòu)造方法。教學(xué)目標(biāo)8.1概述1.什么是排序？將一組雜亂無(wú)章的數(shù)據(jù)按一定規(guī)律順次排列起來(lái)。

2.排序的目的是什么？存放在數(shù)據(jù)表中按關(guān)鍵字排序

——便于查找以及方便去除重復(fù)！3.什么叫內(nèi)部排序？什么叫外部排序？

若待排序記錄都在內(nèi)存中，稱(chēng)為內(nèi)部排序；若待排序記錄一部分在內(nèi)存，一部分在外存，則稱(chēng)為外部排序。注：外部排序時(shí)，要將數(shù)據(jù)分批調(diào)入內(nèi)存來(lái)排序，中間結(jié)果還要及時(shí)放入外存，顯然外部排序要復(fù)雜得多。

4.排序算法的好壞如何衡量？時(shí)間效率——排序速度（比較次數(shù)與移動(dòng)次數(shù)）空間效率——占內(nèi)存輔助空間的大小穩(wěn)定性——A和B的關(guān)鍵字相等，排序后A、B的先后次序保持不變，則稱(chēng)這種排序算法是穩(wěn)定的。記錄序列以順序表存儲(chǔ)Typedefstruct{//定義每個(gè)記錄（數(shù)據(jù)元素）的結(jié)構(gòu)

KeyTypekey;//關(guān)鍵字

InfoTypeotherinfo;//其它數(shù)據(jù)項(xiàng)}RedType;Typedefstruct{//定義順序表的結(jié)構(gòu)

RedTyper[MAXSIZE+1];//存儲(chǔ)順序表的向量

//r[0]一般作哨兵或緩沖區(qū)

intlength;//順序表的長(zhǎng)度}SqList;#defineMAXSIZE20//設(shè)記錄不超過(guò)20個(gè)typedefintKeyType;//設(shè)關(guān)鍵字為整型量（int型）排序算法分類(lèi)規(guī)則不同插入排序交換排序選擇排序歸并排序時(shí)間復(fù)雜度不同簡(jiǎn)單排序O(n2)先進(jìn)排序O(nlog2n)8.2插入排序基本思想：

每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。即邊插入邊排序，保證子序列中隨時(shí)都是排好序的直接插入排序（基于順序查找）不同的具體實(shí)現(xiàn)方法導(dǎo)致不同的算法描述折半插入排序（基于折半查找）希爾排序（基于逐趟縮小增量）最簡(jiǎn)單的排序法！直接插入排序排序過(guò)程：整個(gè)排序過(guò)程為n-1趟插入，即先將序列中第1個(gè)記錄看成是一個(gè)有序子序列，然后從第2個(gè)記錄開(kāi)始，逐個(gè)用順序進(jìn)行插入，直至整個(gè)序列有序?！?3】,6,3,31,9,27,5,11【6,13】,3,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13，31】,9,27,5,11【3,6,9,13，31】,27,5,11【3,6,9,13，27,31】,5,11【3,5,6,9,13，27,31】,11【3,5,6,9,11，13，27,31】

例（13，6，3，31，9，27，5，11）21254925*16080123456暫存21i=2i=3i=5i=4i=62525494925*25*49161625*08084921254925*21初態(tài)：164925*25211608完成!將序列存入順序表L中，將L.r[0]作為哨兵（21，25，49，25*，16，08）*表示后一個(gè)25有序序列R[1..i-1]R[i]

無(wú)序序列R[i..n]插入排序的基本思想：有序序列R[1..i]無(wú)序序列R[i+1..n]3．將R[i]插入到R[j+1]的位置上。2．將R[j+1..i-1]中的所有記錄均后移一個(gè)位置；1．在R[1..i-1]中查找R[i]的插入位置，

R[1..j].keyR[i].key<R[j+1..i-1].key；插入排序的基本步驟：從R[i-1]向前進(jìn)行順序查找，監(jiān)視哨設(shè)置在R[0]if(L.r[i].key<L.r[i-1].key){R[0]=R[i];//設(shè)置“哨兵”

R[i]=R[i-1];

for(j=i-2;R[0].key<R[j].key;--j)R[j+1]=R[j];jR[i]i-1插入位置直接插入排序關(guān)鍵字大于R[i].key的記錄向后移動(dòng)循環(huán)結(jié)束表明R[i]的插入位置為j+1L.r[j+1]=L.r[0];//插入到正確位置直接插入排序voidInsertSort(SqList＆L){inti,j;for(i=2;i<=L.length;++i)if(L.r[i].key<L.r[i-1].key)//將L.r[i]插入有序子表

{L.r[0]=L.r[i];//復(fù)制為哨兵

L.r[i]=L.r[i-1];for(j=i-2;L.r[0].key<L.r[j].key;--j) L.r[j+1]=L.r[j];//記錄后移

L.r[j+1]=L.r[0];//插入到正確位置

}}算法分析設(shè)對(duì)象個(gè)數(shù)為n，則執(zhí)行n-1趟比較次數(shù)和移動(dòng)次數(shù)與初始排列有關(guān)最好情況下：每趟只需比較1次，不移動(dòng)總比較次數(shù)為

n-121254925*1608for(i=2;i<=L.length;++i)if(L.r[i].key<L.r[i-1].key)

2023年2月14日

最壞情況下：第i趟比較i次，移動(dòng)i+1次21254925*1608算法分析比較次數(shù)移動(dòng)次數(shù)if(L.r[i].key<L.r[i-1].key)

{

L.r[0]=L.r[i];//復(fù)制為哨兵L.r[i]=L.r[i-1];

……L.r[j+1]=L.r[0];//插入到正確位置}若出現(xiàn)各種可能排列的概率相同，則可取最好情況和最壞情況的平均情況平均情況比較次數(shù)和移動(dòng)次數(shù)為n2/4時(shí)間復(fù)雜度為o(n2)空間復(fù)雜度為o(1)是一種穩(wěn)定的排序方法21254925*160821254925*1608012345算法分析折半插入排序直接插入排序減少關(guān)鍵字間的比較次數(shù)在插入r[i]時(shí)，利用折半查找法尋找r[i]的插入位置i=2折半插入排序i=3折半插入排序i=4折半插入排序i=5折半插入排序i=6折半插入排序voidBInsertSort(SqList&L){for(i=2;i<=L.length;++i){L.r[0]=L.r[i];low=1;high=i-1;while(low<=high){m=(low+high)/2;if(L.r[0].key<L.r[m].key)high=m-1;elselow=m+1;}for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];L.r[high+1]=L.r[0];}}//BInsertSort折半查找比順序查找快，所以折半插入排序就平均性能來(lái)說(shuō)比直接插入排序要快它所需要的關(guān)鍵碼比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o(wú)關(guān)，僅依賴(lài)于對(duì)象個(gè)數(shù)。在插入第i個(gè)對(duì)象時(shí)，需要經(jīng)過(guò)log2i+1次關(guān)鍵碼比較，才能確定它應(yīng)插入的位置算法分析當(dāng)n較大時(shí)，總關(guān)鍵碼比較次數(shù)比直接插入排序的最壞情況要好得多，但比其最好情況要差在對(duì)象的初始排列已經(jīng)按關(guān)鍵碼排好序或接近有序時(shí)，直接插入排序比折半插入排序執(zhí)行的關(guān)鍵碼比較次數(shù)要少折半插入排序的對(duì)象移動(dòng)次數(shù)與直接插入排序相同，依賴(lài)于對(duì)象的初始排列算法分析減少了比較次數(shù)，但沒(méi)有減少移動(dòng)次數(shù)平均性能優(yōu)于直接插入排序時(shí)間復(fù)雜度為o(n2)空間復(fù)雜度為o(1)是一種穩(wěn)定的排序方法算法分析希爾排序算法思想的出發(fā)點(diǎn)：直接插入排序在基本有序時(shí)，效率較高在待排序的記錄個(gè)數(shù)較少時(shí)，效率較高基本思想：先將整個(gè)待排記錄序列分割成若干子序列,分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。希爾排序子序列的構(gòu)成不是簡(jiǎn)單地“逐段分割”將相隔某個(gè)增量dk的記錄組成一個(gè)子序列讓增量dk逐趟縮短（例如依次取5,3,1）直到dk＝1為止。技巧：小元素跳躍式前移最后一趟增量為1時(shí)，序列已基本有序平均性能優(yōu)于直接插入排序優(yōu)點(diǎn)：38例：關(guān)鍵字序列T=(49，38，65，97,76,13,27,49*，55,04）0123456789104938659776132749*5504初態(tài)：第1趟(dk=5)第2趟(dk=3)第3趟(dk=1)4913134938276549*9755760427386549*9755135576045513270427044949*4949*76387665659797551327044949*3876659713270449*7697r[i]dk

值較大，子序列中對(duì)象較少，速度較快；dk

值逐漸變小，子序列中對(duì)象變多，但大多數(shù)對(duì)象已基本有序，所以排序速度仍然很快。voidShellSort(SqList&L，intdlta[]，intt){

//按增量序列dlta[0…t-1]對(duì)順序表L作Shell排序

for(k=0；k<t；++k)

ShellInsert(L，dlta[k])；

//增量為dlta[k]的一趟插入排序}//ShellSort希爾排序算法（主程序）dk值依次裝在dlta[t]中voidShellInsert(SqList&L，int

dk){

for(i=dk+1；i<=L.length；++i)if(r[i].key<r[i-dk].key){

r[0]=r[i]；

for(j=i-dk;j>0&&(r[0].key<r[j].key);j=j-dk) r[j+dk]=r[j]；

r[j+dk]=r[0]；

}}//對(duì)順序表L進(jìn)行一趟增量為dk的Shell排序，dk為步長(zhǎng)因子//開(kāi)始將r[i]插入有序增量子表//暫存在r[0]//關(guān)鍵字較大的記錄在子表中后移//在本趟結(jié)束時(shí)將r[i]插入到正確位置希爾排序算法（其中某一趟的排序操作）時(shí)間復(fù)雜度是n和d的函數(shù)：空間復(fù)雜度為o(1)是一種不穩(wěn)定的排序方法算法分析O(n1.25）～O（1.6n1.25）—經(jīng)驗(yàn)公式如何選擇最佳d序列，目前尚未解決最后一個(gè)增量值必須為1，無(wú)除1以外的公因子不宜在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)8.3交換排序基本思想：兩兩比較，如果發(fā)生逆序則交換，直到所有記錄都排好序?yàn)橹?。起泡排序O(n2)快速排序O(nlog2n)基本思想：每趟不斷將記錄兩兩比較，并按“前小后大”規(guī)則交換起泡排序21，25，49，25*，16，0821，25，25*，16，08，

4921，25，16，08，25*，4921，16，08，25，25*，4916，08，21，25，25*，4908，16，21，25，25*，49起泡排序優(yōu)點(diǎn)：每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素；

一旦下趟沒(méi)有交換，還可提前結(jié)束排序voidmain() { inta[11]; /*a[0]不用，之用a[1]~a[10]*/ inti,j,t; printf("\nInput10numbers:\n"); for(i=1;i<=10;i++) scanf("%d",&a[i]); printf("\n");

for(j=1;j<=9;j++) for(i=1;i<=10-j;i++)

if(a[i]>a[i+1]) {t=a[i];a[i]=a[i+1];a[i+1]=t;}//交換

for(i=1;i<=10;i++) printf("%d",a[i]);}例3849657613273097

第一趟38496513273076第二趟384913273065第三趟3813273049第四趟13273038第五趟132730第六趟4938659776132730

初始關(guān)鍵字n=8384976971397279730971376767627301365276530651313494930492738273830381327第七趟排序后序列為：1327303849657697voidbubble_sort(SqList&L){intm,i,j,flag=1;RedTypex;m=n-1;while((m>0)&&(flag==1)){flag=0;for(j=1;j<=m;j++)if(L.r[j].key>L.r[j+1].key){flag=1;x=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=x;//交換

}//endifm--;}//endwhile}

算法分析設(shè)對(duì)象個(gè)數(shù)為n比較次數(shù)和移動(dòng)次數(shù)與初始排列有關(guān)只需1趟排序，比較次數(shù)為

n-1，不移動(dòng)21254925*1608while((m>0)&&(flag==1)){flag=0;for(j=1;j<=m;j++)if(L.r[j].key>L.r[j+1].key){flag=1;x=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=x;}……最好情況下：21254925*1608算法分析時(shí)間復(fù)雜度為o(n2)空間復(fù)雜度為o(1)是一種穩(wěn)定的排序方法需n-1趟排序，第i趟比較n-i次，移動(dòng)3(n-i)次最壞情況下：快速排序基本思想：任取一個(gè)元素(如第一個(gè))為中心所有比它小的元素一律前放，比它大的元素一律后放，形成左右兩個(gè)子表；對(duì)各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個(gè)子表的元素只剩一個(gè)21254925*16080123452125*1625160849pivotkey0821081625*21pivotkeypivotkey快速排序25*25492549pivotkey49081625*25210123 45678493838656597977676131327274949highlow49界點(diǎn)快速排序0123 45678493838656597977676131327274949highlow49界點(diǎn)快速排序0123 45678493838656597977676131327274949highlow49界點(diǎn)快速排序0123 45678493838656597977676131327274949highlow49界點(diǎn)快速排序0123 45678493838656597977676131327274949highlow49界點(diǎn)快速排序0123 45678493838656597977676131327274949highlow49界點(diǎn)快速排序0123 45678493838656597977676131327274949highlow49界點(diǎn)快速排序0123 45678493838656597977676131327274949highlow49界點(diǎn)快速排序0123 45678493838656597977676131327274949highlow49界點(diǎn)快速排序0123 45678493838656597977676131327274949highlow49界點(diǎn)快速排序0123 45678493838656597977676131327274949highlow49界點(diǎn)快速排序0123 45678493838656597977676131327274949highlow49界點(diǎn)快速排序0123 45678493838656597977676131327274949highlow49界點(diǎn)快速排序0123 45678273838136597497676139765274949highlow49界點(diǎn)快速排序0123 45678273838136597497676139765274949highlow49界點(diǎn)快速排序0123 45678273838136597497676139765274949highlow49界點(diǎn)快速排序0123 45678273838136597497676139765274949highlow49界點(diǎn)快速排序0123 45678273838136597497676139765274949highlow49界點(diǎn)快速排序0123 45678133827386597497676139765274949highlow49界點(diǎn)快速排序0123 45678133827386597497676139765274949highlow49界點(diǎn)快速排序0123 45678133827386597497676139765274949highlow49界點(diǎn)快速排序0123 45678133827386597497676139765274949highlow49界點(diǎn)快速排序0123 45678133827386597497676139765274949highlow49界點(diǎn)快速排序0123 45678133827386597497676139765274949highlow49界點(diǎn)快速排序0123 45678133827386597497676139765274949highlow49界點(diǎn)0123 45678133827386597497676139765274949highlow49界點(diǎn)0123 45678133827386597494976136576274997highlow49界點(diǎn)快速排序0123 45678133827386597494976136576274997highlow49界點(diǎn)快速排序0123 45678133827386597494976136576274997highlow49界點(diǎn)快速排序

2023年2月14日

①每一趟的子表的形成是采用從兩頭向中間交替式逼近法；②由于每趟中對(duì)各子表的操作都相似，可采用遞歸算法?？焖倥判騰oidmain(){QSort(L,1,L.length);}voidQSort(SqList&L，intlow,inthigh){if(low<high){pivotloc=Partition(L,low,high);

Qsort(L,low,pivotloc-1);

Qsort(L,pivotloc+1,high)}}intPartition(SqList&L，intlow,inthigh

)

{L.r[0]=L.r[low];pivotkey=L.r[low].key;

while(low<high){while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]=L.r[high];while(low<high&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low];}

L.r[low]=L.r[0];returnlow;}可以證明，平均計(jì)算時(shí)間是O(nlog2n)。實(shí)驗(yàn)結(jié)果表明：就平均計(jì)算時(shí)間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個(gè)?？焖倥判蚴沁f歸的，需要有一個(gè)棧存放每層遞歸調(diào)用時(shí)參數(shù)（新的low和high）。最大遞歸調(diào)用層次數(shù)與遞歸樹(shù)的深度一致，因此，要求存儲(chǔ)開(kāi)銷(xiāo)為O(log2n)

。算法分析算法分析最好：劃分后，左側(cè)右側(cè)子序列的長(zhǎng)度相同最壞：從小到大排好序，遞歸樹(shù)成為單支樹(shù)，每次劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列，必須經(jīng)過(guò)n-1趟才能把所有對(duì)象定位，而且第i

趟需要經(jīng)過(guò)n-i

次關(guān)鍵碼比較才能找到第i

個(gè)對(duì)象的安放位置算法分析時(shí)間效率：O(nlog2n)—每趟確定的元素呈指數(shù)增加空間效率：O（log2n）—遞歸要用到?？臻g穩(wěn)定性：不穩(wěn)定—可選任一元素為支點(diǎn)。8.4選擇排序基本思想：每一趟在后面n-i+1個(gè)中選出關(guān)鍵碼最小的對(duì)象,作為有序序列的第i個(gè)記錄2125*i=125164908最小者

08交換21,0825160825*4921i=2最小者

16交換25,1649i=3081625*2521最小者

21交換49,21簡(jiǎn)單選擇排序4925*012345i=408162521最小者

25*無(wú)交換25*i=549最小者

25無(wú)交換2521160825160825*4921結(jié)果各趟排序后的結(jié)果簡(jiǎn)單選擇排序voidSelectSort(SqList&K){for(i=1;i<L.length;++i){//在L.r[i..L.length]中選擇key最小的記錄

k=i;for(j=i+1;j<=L.length;j++)if(L.r[j].key<L.r[k].key)k=j;if(k!=i)L.r[i]←→L.r[k];}}簡(jiǎn)單選擇排序算法分析時(shí)間復(fù)雜度：O(n2)空間復(fù)雜度：O(1)穩(wěn)定比較次數(shù)：移動(dòng)次數(shù)最好情況：0最壞情況：3(n-1)BAOBAODIAOCHABAODIAOWANGZHAOCHALIUBAODIAOYANGXUEWANG樹(shù)形選擇排序DIAOCHADIAOWANGZHAOCHALIUDIAOYANGXUEWANG樹(shù)形選擇排序CHACHADIAOCHALIUDIAOWANGZHAOCHALIU*DIAOYANGXUEWANG樹(shù)形選擇排序DIAOLIUDIAOWANGZHAOLIU*DIAOYANGXUEWANG樹(shù)形選擇排序DIAOLIUDIAOZHAOLIUDIAOWANGZHAO*LIU*DIAOYANGXUEWANG樹(shù)形選擇排序

改進(jìn)：簡(jiǎn)單選擇排序沒(méi)有利用上次選擇的結(jié)果，是造成速度慢的重要原因。如果，能夠加以改進(jìn)，將會(huì)提高排序的速度。381376276549974938651327133813選出最小者13樹(shù)形選擇排序

改進(jìn)：簡(jiǎn)單選擇排序沒(méi)有利用上次選擇的結(jié)果，是造成速度滿(mǎn)的重要原因。如果，能夠加以改進(jìn)，將會(huì)提高排序的速度。381376276549974938651327133813選出次最小者，應(yīng)利用上次比較的結(jié)果。從被13打敗的結(jié)點(diǎn)27、76、38中加以確定。樹(shù)形選擇排序n個(gè)元素的序列{k1,k2,…,kn}，當(dāng)且僅當(dāng)滿(mǎn)足下列關(guān)系時(shí)，成為堆：堆排序什么是堆？如果將序列看成一個(gè)完全二叉樹(shù)，非終端結(jié)點(diǎn)的值均小于或大于左右子結(jié)點(diǎn)的值。(87,78,53,45,65,09,31,17,23)堆頂元素（根）為最小值或最大值(09,17,65,23,45,78,87,53,31)利用樹(shù)的結(jié)構(gòu)特征來(lái)描述堆，所以樹(shù)只是作為堆的描述工具，堆實(shí)際是存放在線(xiàn)形空間中的。小根堆

816

9

1

6

2

1110

5

4大根堆

1

6

812

916

2

11

51416

9

810

6

2

11

1

5

4

1

9

810

616

2

11

5

4×判定(80,75,40,62,73,35,28,50,38,25,47,15)是否為堆807540627328355038254715完全二叉樹(shù)大根堆將無(wú)序序列建成一個(gè)堆輸出堆頂?shù)淖钚。ù螅┲凳故Ｓ嗟膎-1個(gè)元素又調(diào)整成一個(gè)堆，則可得到n個(gè)元素的次小值重復(fù)執(zhí)行，得到一個(gè)有序序列堆排序基本思想：如何建？？如何調(diào)整？？30160240

4

70

58

312610

7[1][2][3][4][5][6][7]3060840701210如何將無(wú)序序列建成堆思考：有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，最后一個(gè)分支結(jié)點(diǎn)的標(biāo)號(hào)是多少？n/270160240

4

30

512

38610

7[1][2][3][4][5][6][7]7060124030810從第n/2個(gè)元素起，至第一個(gè)元素止，進(jìn)行反復(fù)篩選堆30160240

4

70

510

7[1][2][3][4][5][6][7]3060840701210無(wú)序序列建成堆－18

12

3

630160240

4

70

512

810

7[1][2][3][4][5][6][7]3060124070810無(wú)序序列建成堆－1

3

63016040

4

12810

7[1][2][3][4][5][6][7]3060124070810無(wú)序序列建成堆－2

3

6

270

53017040

4

12810

7[1][2][3][4][5][6][7]3070124060810無(wú)序序列建成堆－2

3

6

260

5

7040

4

12810

7[1][2][3][4][5][6][7]3070124060810無(wú)序序列建成堆－3

3

6

2

60

530

1

3040

4

12810

7[1][2][3][4][5][6][7]7030124060810無(wú)序序列建成堆－3

3

6

2

60

570

1

6040

4

12810

7[1][2][3][4][5][6][7]7060124030810無(wú)序序列建成堆－3

3

6

2

5

70

130建堆完畢輸出堆頂元素后，以堆中最后一個(gè)元素替代之將根結(jié)點(diǎn)與左、右子樹(shù)根結(jié)點(diǎn)比較，并與小者交換重復(fù)直至葉子結(jié)點(diǎn)，得到新的堆如何在輸出堆頂元素后調(diào)整，使之成為新堆？篩選堆的重新調(diào)整

6040

4

12810

7[1][2][3][4][5][6][7]7060124030810

3

6

2

30

570

1堆的重新調(diào)整－1堆的重新調(diào)整－1

6040

4

12810

7[1][2][3][4][5][6][7]

3

6

2

30

510

17060124030810707010×

×

60106010104040堆的重新調(diào)整－2

4010

4

12810

7[1][2][3][4][5][6][7]

3

6

2

30

560

160401210308107070×

×

堆的重新調(diào)整－2

4010

4

126010

7[1][2][3][4][5][6][7]

3

6

2

30

58

1840121030601070706060堆的重新調(diào)整－2

3010

4

126010

7[1][2][3][4][5][6][7]

3

6

28

540

1403012108601070706060堆的重新調(diào)整－3

3010

4

126010

7[1][2][3][4][5][6][7]

3

6

28

540

1403012108601070706060堆的重新調(diào)整－3

3010

4

126010

7[1][2][3][4][5][6][7]

3

6

28

58

1830121086010707060604040堆的重新調(diào)整－3

108

4

126010

7[1][2][3][4][5][6][7]

3

6

28

530

1301012886010707060604040堆的重新調(diào)整－4

108

4

126010

7[1][2][3][4][5][6][7]

3

6

28

530

1301012886010707060604040堆的重新調(diào)整－4

1030

4

126010

7[1][2][3][4][5][6][7]

3

6

28

58

18101230860107070606040403030堆的重新調(diào)整－5

1030

4

86010

7[1][2][3][4][5][6][7]

3

6

28

512

11210830860107070606040403030堆的重新調(diào)整－5

1030

4

86010

7[1][2][3][4][5][6][7]

3

6

28

58

18108308601070706060404030301212堆的重新調(diào)整－5

1030

4

86010

7[1][2][3][4][5][6][7]

3

6

28

58

18108308601070706060404030301212堆的重新調(diào)整－5

830

4

86010

7[1][2][3][4][5][6][7]

3

6

28

510

11088308601070706060404030301212堆的重新調(diào)整－6

830

4

86010

7[1][2][3][4][5][6][7]

3

6

28

510

11088308601070706060404030301212堆的重新調(diào)整－6

830

4

86010

7[1][2][3][4][5][6][7]

3

6

28

58

18883086010707060604040303012121010算法分析時(shí)間效率：O(nlog2n)空間效率：O（1）穩(wěn)定性：不穩(wěn)定適用于n較大的情況8.5歸并排序歸并：將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新有序表2-路歸并排序排序過(guò)程初始序列看成n個(gè)有序子序列，每個(gè)子序列長(zhǎng)度為1兩兩合并，得到n/2個(gè)長(zhǎng)度為2或1的有序子序列再兩兩合并，重復(fù)直至得到一個(gè)長(zhǎng)度為n的有序序列為止將兩個(gè)順序表合并成一個(gè)有序表0123 44913659776780AB0123 4567Cijk0123 44913659776780AB0123 4567Cijk70123 44913659776780AB0123 4567Cijk70123 44913659776780AB0123 4567Cijk7130123 44913659776780AB0123 4567Cijk713490123 44913659776780AB0123 4567Cijk713490123 44913659776780AB0123 4567Cijk71349650123 44913659776780AB0123 4567Cijk71349650123 44913659776780AB0123 4567Cijk7134965760123 44913659776780AB0123 4567Cijk7134965760123 44913659776780AB0123 4567Cijk713496576800123 44913659776780AB0123 4567Cijk713496576800123 44913659776780AB0123 4567Cijk71349657680B表的元素都已移入C表，只需將A表的剩余部分移入C表即可0123 44913659776780AB0123 4567Cijk7134965768097例初始關(guān)鍵字：[49][38][65][97][76][13][27]一趟歸并后：[3849][6597][1376][27]二趟歸并后：[38496597][132776]三趟歸并后：[13273849657697]算法分析時(shí)間效率：O(nlog2n)空間效率：O（n）穩(wěn)定性：穩(wěn)定以撲克牌排序?yàn)槔?。每張撲克牌有兩個(gè)“排序碼”：花色和面值。其有序關(guān)系為：

花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A

可以把所有撲克牌排成以下次序：

2,…,

A,

2,…,

A,

2,…,

A,

2,…,

A花色相同的情況下，比較面值。8.6基數(shù)排序前面的排序方法主要通過(guò)關(guān)鍵字值之間的比較和移動(dòng)而基數(shù)排序不需要關(guān)鍵字之間的比較對(duì)52張撲克牌按以下次序排序：2<3<……<A<2<3<……<A<2<3<……<A<2<3<……<A兩個(gè)關(guān)鍵字：花色（<<<）面值（2<3<……<A）并且“花色”地位高于“面值”多關(guān)鍵字排序鏈?zhǔn)交鶖?shù)排序最高位優(yōu)先MSD(MostSignificantDigitfirst)最低位優(yōu)先LSD(LeastSignificantDigitfirst)鏈?zhǔn)交鶖?shù)排序：用鏈表作存儲(chǔ)結(jié)構(gòu)的基數(shù)排序先對(duì)最高位關(guān)鍵字k1（如花色）排序，將序列分成若干子序列，每個(gè)子序列有相同的k1值；然后讓每個(gè)子序列對(duì)次關(guān)鍵字k2（如面值）排序，又分成若干更小的子序列；依次重復(fù)，直至就每個(gè)子序列對(duì)最低位關(guān)鍵字kd排序，就可以得到一個(gè)有序的序列。最高位優(yōu)先法十進(jìn)制數(shù)比較可以看作是一個(gè)多關(guān)鍵字排序最高位優(yōu)先法十位首先依據(jù)最低位排序碼Kd對(duì)所有對(duì)象進(jìn)行一趟排序再依據(jù)次低位排序碼Kd-1對(duì)上一趟排序結(jié)果排序依次重復(fù)，直到依據(jù)排序碼K1最后一趟排序完成，就可以得到一個(gè)有序的序列。最低位優(yōu)先法這種方法不需要再分組，而是整個(gè)對(duì)象組都參加排序最低位優(yōu)先法先決條件：知道各級(jí)關(guān)鍵字的主次關(guān)系知道各級(jí)關(guān)鍵字的取值范圍鏈?zhǔn)交鶖?shù)排序利用“分配”和“收集”對(duì)關(guān)鍵字進(jìn)行排序過(guò)程首先對(duì)低位關(guān)鍵字排序，各個(gè)記錄按照此位關(guān)鍵字的值‘分配’到相應(yīng)的序列里。按照序列對(duì)應(yīng)的值的大小，從各個(gè)序列中將記錄‘收集’，收集后的序列按照此位關(guān)鍵字有序。在此基礎(chǔ)上，對(duì)前一位關(guān)鍵字進(jìn)行排序。初始狀態(tài)：f[i]和e[i]分別為第i個(gè)隊(duì)列的頭指針和尾指針278109063930589184505269008083109589269278063930083184505008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集：505008109930063269278083184589二趟收集：083184589063505269930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269一趟收集008063083109184269278505589930三趟收集：109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]三趟分配063083269278505589505008109930063269278083184589二趟收集設(shè)置10個(gè)隊(duì)列，f[i]和e[i]分別頭指針和尾指針第一趟分配對(duì)最低位關(guān)鍵字（個(gè)位）進(jìn)行，改變記錄的指針值，將鏈表中記錄分配至10個(gè)鏈隊(duì)列中，每個(gè)隊(duì)列記錄的關(guān)鍵字的個(gè)位相同第一趟收集是改變所有非空隊(duì)列的隊(duì)尾記錄的指針域，令其指向下一個(gè)非空隊(duì)列的隊(duì)頭記錄，重新將10個(gè)隊(duì)列鏈成一個(gè)鏈表重復(fù)上述兩步，進(jìn)行第二趟、第三趟分配和收集，分別對(duì)十位、百位進(jìn)行，最后得到一個(gè)有序序列鏈?zhǔn)交鶖?shù)排序步驟重復(fù)執(zhí)行d趟“分配”與“收集”每趟對(duì)n

個(gè)記錄進(jìn)行“分配”，對(duì)rd個(gè)隊(duì)列進(jìn)行“收集”需要增加n+2rd個(gè)附加鏈接指針。n個(gè)記錄每個(gè)記錄有

d

位關(guān)鍵字關(guān)鍵字取值范圍rd(如十進(jìn)制為10)算法分析時(shí)間效率：O(d(n+rd))

空間效率：O(n+rd)穩(wěn)定性：穩(wěn)定8.7外部排序8.7外部排序外部排序的基本過(guò)程１．按可用內(nèi)存大小,利用內(nèi)部排序方法，構(gòu)造若干個(gè)記錄的有序子序列寫(xiě)入外存，通常稱(chēng)這些記錄的有序子序列為“歸并段”;由相對(duì)獨(dú)立的兩個(gè)步驟組成：２．通過(guò)“歸并”，逐步擴(kuò)大(記錄的)有序子序列的長(zhǎng)度，直至外存中整個(gè)記錄序列按關(guān)鍵字有序?yàn)橹埂＠纾杭僭O(shè)有一個(gè)含10,000個(gè)記錄的磁盤(pán)文件，而當(dāng)前所用的計(jì)算機(jī)一次只能對(duì)1,000個(gè)記錄進(jìn)行內(nèi)部排序，則首先利用內(nèi)部排序的方法得到10個(gè)初始?xì)w并段，然后進(jìn)行逐趟歸并。假設(shè)進(jìn)行2路歸并(即兩兩歸并)，則第一趟由10個(gè)歸并段得到5個(gè)歸并段;最后一趟歸并得到整個(gè)記錄的有序序列。第三趟由3個(gè)歸并段得到2個(gè)歸并段;第二趟由5個(gè)歸并段得到3個(gè)歸并段;外部排序的基本方法假設(shè)“數(shù)據(jù)塊”的大小為200，即每一次訪(fǎng)問(wèn)外存可以讀/寫(xiě)200個(gè)記錄。則對(duì)于10,000個(gè)記錄，處理一遍需訪(fǎng)問(wèn)外存100次(讀和寫(xiě)各50次)。分析上述外排過(guò)程中訪(fǎng)問(wèn)外存(對(duì)外存進(jìn)行讀/寫(xiě))的次數(shù)：1)求得10個(gè)初始?xì)w并段需訪(fǎng)問(wèn)外存100次;2)每進(jìn)行一趟歸并需訪(fǎng)問(wèn)外存100次;3)總計(jì)訪(fǎng)問(wèn)外存100+4100=500次外部排序的基本方法外排總的時(shí)間還應(yīng)包括內(nèi)部排序所需時(shí)間和逐趟歸并時(shí)進(jìn)行內(nèi)部歸并的時(shí)間tIO值取決于外存，遠(yuǎn)遠(yuǎn)大于tIS和tmg。外部排序的時(shí)間取決于讀寫(xiě)外存的次數(shù)d。外部排序總時(shí)間=產(chǎn)生初始?xì)w并段的時(shí)間m*tIS

+外存信息讀寫(xiě)時(shí)間d*tIO+內(nèi)部歸并所需時(shí)間s*utmg外部排序的基本方法其中：m：初始?xì)w并段數(shù)目；tis：得到一個(gè)歸并段的內(nèi)排序時(shí)間；d：總的讀、寫(xiě)次數(shù)；tio：一次讀、寫(xiě)的時(shí)間；s：歸并的趟數(shù)；utmg：對(duì)u個(gè)記錄進(jìn)行一趟內(nèi)部歸并排序的時(shí)間。一般地，tio>>tis，tio>>tmg，tio而取決于所用外存,因此，影響外排序效率的主要原因是內(nèi)、外存之間數(shù)據(jù)交換(讀、寫(xiě)外存)。提高效率的主要方法(途徑)有：●

進(jìn)行多路歸并，減少文件歸并的趟