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

第10章排序

陳守孔孟佳娜陳卓坪嘶譴幼室徽氏打碗胎吏樓噓勺闖弦濃污汲爪更蜂腎悅間高沿班修螞瓶綠第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序1第10章排序陳守孔孟佳娜陳卓坪嘶譴幼室徽氏打碗本章目錄10.1概述10.2插入排序10.2.1直接插入排序

10.2.2折半插入排序*10.2.3二路插入排序*10.2.4表插入排序10.2.5希爾排序10.3交換排序10.3.1起泡排序10.3.2快速排序10.4選擇排序10.4.1直接選擇排序10.4.2樹形選擇排序10.4.3堆排序10.5歸并排序10.6分配排序10.7內(nèi)部排序方法的比較10.8外部排序10.8.1文件管理10.8.2外部排序10.8.3多路歸并排序

10.8.4置換選擇排序*10.8.5最佳歸并樹*10.8.6磁帶排序沉神姻高詩算雇珍慰胯侄會您峰許趕胃寡買玄乞的開霖羹量著柴柄僅拖瘍第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序2本章目錄10.1概述沉神姻高詩算雇珍慰胯侄會您峰許趕胃寡買主要內(nèi)容知識點(diǎn)1、排序的定義，排序可以看作是線性表的一種操作2、排序的分類，穩(wěn)定排序與不穩(wěn)定排序的定義。3、插入排序（直接插入、對分插入、二路插入、表插入、希爾插入排序）。4、交換排序（冒泡排序、快速排序）。5、選擇排序（簡單選擇排序、樹形選擇排序、堆排序）。6、歸并排序、基數(shù)排序。7、外部排序重點(diǎn)難點(diǎn)1、各種排序所基于的基本思想。2、排序性能的分析，是否是穩(wěn)定排序。3、折半插入、希爾排序。4、快速排序。5、堆排序。6、敗者樹、置換選擇排序、最佳歸并樹。7、對每種排序方法的學(xué)習(xí)，能舉一反三。穎政谷乎鈉琺櫥既呢念爵釀放灤孽酣昂貿(mào)妒倦馱兇忘葦慎凱祝芒施敘甄扣第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序3主要內(nèi)容知識點(diǎn)穎政谷乎鈉琺櫥既呢念爵釀放灤孽酣昂貿(mào)妒倦馱兇忘基本概念排序：假設(shè)含n個(gè)記錄的序列為{R1,R2,…,Rn}，其相應(yīng)的關(guān)鍵字序列為{K1,K2,…,Kn}，這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個(gè)關(guān)系Ks1≤Ks2≤…≤Ksn，按此固有關(guān)系將n個(gè)記錄的序列重新排列為{Rs1,Rs2,

…,Rsn}的操作稱作排序。涕評責(zé)革鎮(zhèn)猖漱纂栽桂厚隙鼎捶謅糕猜又銹棟韌乘三弧恭揮冰今拙娥忘夜第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序4基本概念排序：涕評責(zé)革鎮(zhèn)猖漱纂栽桂厚隙鼎捶謅糕猜又銹棟韌乘基本概念穩(wěn)定排序：若Ki為關(guān)鍵字，Ki=Kj（i≠j），且在排序前的序列中Ri領(lǐng)先于Rj。經(jīng)過排序后，Ri與Rj的相對次序保持不變（即Ri仍領(lǐng)先于Rj），則稱這種排序方法是穩(wěn)定的，否則稱之為不穩(wěn)定的。內(nèi)部排序：若整個(gè)排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序外部排序：若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過程不可能一次在內(nèi)存中完成，則稱此類排序問題為外部排序午百拖樸修咽替吏液浩轉(zhuǎn)塌缽羞捅憫匿煮涌伸哆也沃爪棺戰(zhàn)抱螺缽胚唆休第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序5基本概念穩(wěn)定排序：若Ki為關(guān)鍵字，Ki=Kj（i≠j），排序的類型定義#definen待排序記錄的個(gè)數(shù)typedefstruct{intkey;AnyTypeother;∥記錄其它數(shù)據(jù)域}RecType;RecTypeR[n+1];

馬淺膽緝粳陌筍謬濱奧華斜十幀侄灌唇禾糠鉚腫泰映殉杠尾耶涯著凝唇淡第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序6排序的類型定義#definen待排序記錄的個(gè)數(shù)馬淺膽基本思想：假定第一個(gè)記錄有序，從第2個(gè)記錄開始，將待排序的記錄插入到有序序列中，使有序序列逐漸擴(kuò)大，直至所有記錄都進(jìn)入有序序列中。

插入排序插入排序種類：

直接插入排序折半插入排序二路插入排序表插入排序

希爾排序

宇迸洽入荔庫挎煌婚峽樓腰敏命絳斑林撫端遣包淆葦追單死念孫哀糟跑出第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序7基本思想：假定第一個(gè)記錄有序，從第2個(gè)記錄開始，將待排序的記直接插入排序基本思想：將記錄R[i](2<=i<=n)插入到有序子序列R[1..i-1]中，使記錄的有序序列從R[1..i-1]變?yōu)镽[1..i]

而拯嫌仔賞箍盒廢蟲蠟賦咽咕酗宵垂掖幫傘匯僑首挾空窯迄羅利誠屯貪瓦第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序8直接插入排序基本思想：將記錄R[i](2<=i<=n)插入到示例初始關(guān)鍵字序列：[51]33629687172851'i=2(33)[3351]629687172851'i=3(62)[335162]9687172851'i=4(96)[33516296]87172851'i=5(87)[3351628796]172851'i=6(17)[173351628796]2851'i=7(28)[17283351628796]51'i=8(51')[1728335151'628796]蕪撂額烹拷州汽條渾溫桶小喲君爾外只鞠走搗潮每印輪韓起滾侖胰蛆略扇第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序9示例初始關(guān)鍵字序列：[51]3362一趟直接插入排序算法voidStrOnePass(RecTypeR[]，inti){∥已知R[1..i-1]中的記錄按關(guān)鍵字非遞減有序排列，本算法

∥插入R[i],使R[1..i]中的記錄按關(guān)鍵字非遞減有序排列R[0]=R[i];j=i-1;∥將待排序記錄放進(jìn)監(jiān)視哨x=R[0].key;∥從后向前查找插入位置，將大于待排序記錄向后移動while(x<R[j].key){R[j+1]=R[j];j--;}∥記錄后移R[j+1]=R[0];∥將待排序記錄放到合適位置}∥StrOnePass誓越瓷鋇咖龜瘟殺溪尊窟虱挨峭趴壘秋隙顫禹寶爾陶摧烴曹坐隱屜戶顏甩第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序10一趟直接插入排序算法voidStrOnePass(Rec直接插入排序算法voidStrInsSort1(RecTypeR[]，intn){∥本算法對R[1..n]進(jìn)行直接插入排序for(i=2;i<=n;i++)∥假定第一個(gè)記錄有序

StrOnePass(R，i)；}舅敏焊輻承液乒患搬措碟墓腫吾習(xí)蔗領(lǐng)逾瘟旺炸設(shè)彥沫宦校亮锨盞葬醚調(diào)第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序11直接插入排序算法voidStrInsSort1(RecT直接插入排序性能分析最好情況比較次數(shù)為n－1次移動次數(shù)為2（n－1）次最壞情況比較次數(shù)為=(n+2)(n-1)/2移動次數(shù)為=(n+4)(n-1)/2篷稍緩錳財(cái)敲喚凝輯炭彰駐澡舌貝蝎鑰高湯斟射座怖倪漫瓦凡鉗屹裳深硫第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序12直接插入排序性能分析比較次數(shù)為n－1次移動次數(shù)為2（n－1）折半插入排序

voidBinsSort(RecTypeR[]，intn)∥對R[1..n]進(jìn)行折半插入排序{for(i=2;i<=n;i++)∥假定第一個(gè)記錄有序{R[0]=R[i];∥將待排記錄R[i]暫存到R[0]

low=1;high=i-1;∥設(shè)置折半查找的范圍 R[low..high]while(low<=high){m=(low+high)/2;∥折半if(R[0].key<R[m].key)high=m-1;∥插入點(diǎn)在低半?yún)^(qū)elselow=m+1;∥插入點(diǎn)在高半?yún)^(qū)}∥whilefor(j=i-1;j>high;j--)R[j+1]=R[j];∥記錄后移R[high+1]=R[0];∥插入}∥for}∥BinsSort峭曼仇糊伏碩峻重蝴福爐鑿?fù)π沙懋嬭D以欺頑碌寐向嗓亨惹渴奇袱北昏第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序13折半插入排序

voidBinsSort(RecType折半插入排序性能分析減少了比較次數(shù)，移動次數(shù)不變。時(shí)間復(fù)雜度仍為O（n2）。芋輾悄蹄孔煎蒜鈣葫邏肚夫望爆加欽裸節(jié)澇焊頰護(hù)催悟念為騰俏帥密劫狂第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序14折半插入排序性能分析減少了比較次數(shù)，移動次數(shù)不變。芋輾悄蹄孔在對一組記錄（54，38，96，23，15，72，60，45，83）

進(jìn)行直接排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需比較多少次饋蒜宙鍬嘿長巍典話舷獲赴轅支黃筒手并鵑脯矗斷通烴甸愚陪趙弦項(xiàng)渦柴第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序15在對一組記錄饋蒜宙鍬嘿長巍典話舷獲赴轅支黃筒二路插入排序

對折半插入排序改進(jìn)，減少了移動記錄的次數(shù)，但它要借助n個(gè)記錄的輔助空間，即其空間復(fù)雜度為O（n）?；舅枷耄毫碓O(shè)一數(shù)組d，將R[1]賦值給d[1]，并將d[1]看作排好序的中間記錄，從第二個(gè)記錄起依次將關(guān)鍵字小于d[1]的記錄插入d[1]之前的有序序列，將關(guān)鍵字大于d[1]的記錄插入d[1]之后的有序序列。借助兩個(gè)變量first和final來指示排序過程中有序序列第一個(gè)記錄和最后一個(gè)記錄在d中的位置。足狐沮揍實(shí)沮串唯繁認(rèn)賢茵瘩岳避鑿渡甭筷嚙眩廖糊駒記簾罪逞憂倚宿衰第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序16二路插入排序

對折半插入排序改進(jìn)，減少了移動記錄的次數(shù)，但它初始關(guān)鍵字序列：5133629687172851

i=1[51]first↑↑finali=2[51][33]↑final↑firsti=3[5162][33]final↑↑firsti=4[516296][33]final↑↑firsti=5[51628796][33]final↑↑firsti=6[51628796][1733]final↑↑firsti=7[51628796][172833]final↑↑firsti=8[5151628796172833]final↑↑first

駕菱辭飼殊淑泵乾妹避峰突揭慢軋覆腳鈍胚瘤停募估卵墟翱去邑園街這綿第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序17初始關(guān)鍵字序列：51336296二路插入排序算法voidBiInsertSort(RecTypeR[]，intn){∥二路插入排序的算法

intd[n+1];∥輔助存儲

d[1]=R[1];first=1;final=1;

for(i=2;i<=n;i++)

{if(R[i].key>=d[1].key)∥插入后部

{low=1;high=final;while(low<=high)∥折半查找插入位置{m=(low+high)/2;if(R[i].key<d[m].key)high=m-1;elselow=m+1;}∥whilefor(j=final;j>=high+1;j--)d[j+1]=d[j];∥移動元素

d[high+1]=R[i];final++;∥插入有序位置

}錳窟更秋宅園干并鏟恫尊萍拋棠簡鄭蓬需偵揀恫啃滇疚蠢寧漚特營第捍磨第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序18二路插入排序算法voidBiInsertSort(RecT

else

{

if(first==1)∥插入前部{first=n;d[n]=R[i];}else{low=first;high=n;while(low<=high){m=(low+high)/2;if(R[i].key<d[m].key)high=m-1;elselow=m+1;}∥whilefor(j=first;j<=high;j++)d[j-1]=d[j];∥移動元素

d[high]=R[i];first--;

}∥if}∥if}//for}況鞍踩謠菠故銀朗晶丟呀納歐嘆援孰蛀石荷宗怪透搗耿腑頒衡?？稚钐缘?0章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序19

else

{

if(first==1)∥插表插入排序

靜態(tài)鏈表#definen待排序記錄的個(gè)數(shù)typedefstruct{intkey;AnyTypeother;∥記錄其他數(shù)據(jù)域intnext;}STListType;STListTypeSL[n+1];扼膳苫掣刪彪魔叼傅狐軍枚吹繹抒迄柿膠顫翌漢鏡禍籌旨駿沼吮殼浩婪器第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序20表插入排序

靜態(tài)鏈表扼膳苫掣刪彪魔叼傅狐軍枚吹繹抒迄柿膠顫翌表插入排序算法

voidListInsSort(STListTypeSL[],intn)∥對記錄序列SL[1..n]作表插入排序。{SL[0].key=MAXINT;SL[0].next=1;SL[1].next=0;for(i=2;i<=n;i++)∥查找插入位置{j=0;for(k=SL[0].next;SL[k].key<=SL[i].key;){j=k,k=SL[k].next;}SL[j].next=i;SL[i].next=k;∥結(jié)點(diǎn)i插入在結(jié)點(diǎn)j和結(jié)點(diǎn)k之間}∥for}∥ListInsSort桐彈腆細(xì)舅臺群沾丹幽家艾砂虞趟愧聳虜削川寞訟洶篇婁號境鵲場腦篆坯第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序21表插入排序算法

voidListInsSort(STLi表物理排序

voidArrange(STListTypeSL[]，intn){∥調(diào)整靜態(tài)鏈表SL中各結(jié)點(diǎn)的指針值，使記錄按關(guān)鍵字有序排列p=SL[0].next;∥p指示第一個(gè)記錄的當(dāng)前位置for(i=1;i<n;i++){∥SL[1..i-1]記錄已按關(guān)鍵字有序，第i個(gè)記錄的當(dāng)前位置應(yīng)不小于iwhile(p<i)p=SL[p].next;∥找到第i個(gè)記錄，并用p指示其在SL中當(dāng)前位置q=SL[p].next;∥q指示尚未調(diào)整的表尾if(p!=i){SL[p]←→SL[i];∥交換記錄，使第i個(gè)記錄到位SL[i].next=p;∥指向被移走的記錄，使得以后可由while循環(huán)找回}∥ifp=q;∥p指示尚未調(diào)整的表尾，為找第i+1個(gè)記錄作準(zhǔn)備}∥for}∥Arrange便堪需賴皂盈蜒跡入份發(fā)市迅搓樂綽辱連蠱尖喪掠妓空滔詹矚停瀕皆奢新第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序22表物理排序

voidArrange(STListTyp希爾(shell1959)排序基本思想：從“減小n”和“基本有序”兩方面改進(jìn)。將待排序的記錄劃分成幾組，從而減少參與直接插入排序的數(shù)據(jù)量，當(dāng)經(jīng)過幾次分組排序后，記錄的排列已經(jīng)基本有序，這個(gè)時(shí)候再對所有的記錄實(shí)施直接插入排序。勺拂破挫副銥?zāi)憷藸幬雍晔谥肽核钪误@籍頸臣庸漓翟謾撅釣席像宰驟羽磁第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序23希爾(shell1959)排序基本思想：從“減小n”和“基希爾排序示例二趟排序結(jié)果：171051／33285152629687三趟排序結(jié)果：1017283351／5152628796

初始關(guān)鍵字序列：5133629687172851／5210

一趟排序結(jié)果：172851／52105133629687改智炕崇彝漱抉萌佳責(zé)甩舜繼龜縛坤丹氰千醛團(tuán)步攆忙叢履蘸攤髓帶步乓第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序24希爾排序示例二趟排序結(jié)果：1710希爾排序算法voidShellSort(RecTypeR[]，intn){∥以步長di/2分組的希爾排序，第一個(gè)步長取n/2，最后一個(gè)取1for(d=n/2;d>=1;d=d/2) {for(i=1+d;i<=n;i++)

∥將R[i]插入到所屬組的有序列段中 {R[0]=R[i];j=i-d; while(j>0&&R[0].key<R[j].key) {R[j+d]=R[j];j=j-d;}∥whileR[j+d]=R[0];∥第i個(gè)元素插入到合適位置}∥for}∥for}∥ShellSort

槽芽轟訊嶼醇酌滔直肅窯瞅際愁肘鄙矣貴職夏痰鉚度痘糙煮神剩獰邦傘撼第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序25希爾排序算法voidShellSort(RecType希爾排序示例請給出對一組記錄（54,38,96,23,15,90,72,60,45,83）進(jìn)行希爾排序（增量序列為5，3，1）時(shí)的排序過程。撇驗(yàn)孔胚寨姚艱練曹可僅供巴斡力氯珍忿漁毋攜臣緬潮廂銳淬七真析小貴第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序26希爾排序示例請給出對一組記錄撇驗(yàn)孔胚寨姚艱練曹可僅供巴斡力氯交換排序主要思路：在排序過程中，通過對待排序記錄序列中元素間關(guān)鍵字的比較，發(fā)現(xiàn)次序相反的，即將元素位置交換來達(dá)到排序目的。

交換排序種類：起泡排序快速排序君婁妹藥落旗藕泉展驟勘銑夕萎豁著塔桂死殘段苗弛另盂潘更罕泛喝蠕休第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序27交換排序主要思路：在排序過程中，通過對待排序記錄序列中元素起泡排序基本思想：對所有相鄰記錄的關(guān)鍵字值進(jìn)行比較，如果是逆序（a[j]>a[j+1]），則將其交換，最終達(dá)到有序化

桶滌遍鐳匪趨衰窗聲恨揮楓胎是草鈾曙鎊敏濰根鴻柯卯丟相擄境秩旋儲旁第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序28起泡排序基本思想：對所有相鄰記錄的關(guān)鍵字值進(jìn)行比較，如果是逆起泡排序示例初始關(guān)鍵字序列：5133629687172851／第一趟排序結(jié)果：33516287172851／[96]第二趟排序結(jié)果：335162172851／[8796]第三趟排序結(jié)果：3351172851／[628796]第四趟排序結(jié)果：33172851[51／628796]第五趟排序結(jié)果：172833[5151／628796]第六趟排序結(jié)果：[1728335151／628796]騙吼安隨懂量菏濟(jì)菩國葉淄罵支碴撞冷父竄袋力木踏找刺磊巫絲電砍冠逝第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序29起泡排序示例初始關(guān)鍵字序列：51336voidBubbleSort(RecTypeR[]，intn){∥起泡排序i=n;∥i指示無序序列中最后一個(gè)記錄的位置while(i>1){lastExchange=1;∥記最后一次交換發(fā)生的位置for(j=1;j<i;j++)if（R[j].key>R[j+1].key）{temp=R[j]；R[j]=R[j+1]；R[j+1]=temp；∥逆序時(shí)交換lastExchange=j;}∥ifi=lastExchange;}∥while}

起泡排序算法姻境齋窖洲抗雖令籠昭貓甥尚桂酌舉紙深絳保聊唆監(jiān)咬滁倦欽倦呵剖酉胖第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序30voidBubbleSort(RecTypeR[]，一組關(guān)鍵字（19,01,26,92,87,11,43,87,21），

進(jìn)行冒泡排序，

試列出每一趟排序后的關(guān)鍵字序列

魂寂弛殆掙超胯生砂巍爸捌震萍召跌熏怯就滋疑燕路佬烏箱陀奇析練岔襖第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序31一組關(guān)鍵字（19,01,26,92,87,11,43,87,快速排序基本思想：從待排序記錄序列中任選取一個(gè)記錄（通常可選第一個(gè)記錄）的關(guān)鍵字作為樞軸（或支點(diǎn)），凡其關(guān)鍵字小于樞軸的記錄均移動至該記錄之前，而關(guān)鍵字大于樞軸的記錄均移動至該記錄之后。一趟快速排序后就將排序序列分成兩部分，再分別對這兩部分遞歸快速排序。

由Hoare(圖靈獎獲得者)1962年提出，被評為20世紀(jì)十大優(yōu)秀算法之一。陡栽恭壺炕澎銻仙由眾灸溜瀕戳瑚晚揩鍛磁激廢肝摻忍柱繭失遍些牧囑送第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序32快速排序由Hoare(圖靈獎獲得者)1962年提出快速排序圖示≤≥1n六銹秒剎延妹憊隆鏟拙奶綿薪鯉晉嫌洪照晶晌揉暢齲物津瞳烹滁廉影儈殷第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序33快速排序圖示≤≥1n六銹秒剎延妹憊隆鏟拙奶綿薪鯉晉嫌洪照晶晌快速排序示例初始關(guān)鍵字序列：[51]33629687172851／R[0]=[51]i↑(樞軸)↑jj向前掃描i↑↑j第一次交換之后：283362968717[]51／i↑↑ji向后掃描i↑↑j第二次交換之后：2833[]9687176251／i↑↑jj向前掃描i↑↑j第三次交換之后：2833179687[]6251／i向后掃描i↑↑j第四次交換之后：283317[]87966251／j向前掃描i↑↑j完成一趟排序：283317[51]87966251／

i↑↑j

炭申騙姓玉檄而物扳疹蓮嘯疙敵舜骨浙疵澇平許鄒疆運(yùn)燕束勁侖呢奇準(zhǔn)逾第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序34快速排序示例初始關(guān)鍵字序列：[51]33快速排序示例初始關(guān)鍵字序列：5133629687172851／一趟排序之后：[283317]51[87966251／]分別進(jìn)行快速排序：[17]28[33]結(jié)束結(jié)束[51／62]87[96]51／[62]結(jié)束結(jié)束有序序列：1728335151／628796擾甘信撈帝擺傳臺逾省漚賓褂繹組佳戰(zhàn)鋤脹傷撼鄉(xiāng)榜縷游鴨沈稻郊負(fù)拋驢第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序35快速排序示例初始關(guān)鍵字序列：513362快速排序算法intPartition(RecTypeR[]，intl，inth){∥交換記錄子序列R[l..h]中的記錄，使樞軸記錄到位并返回其所在位置inti=l;j=h;∥用變量i,j記錄待排序記錄首尾位置R[0]=R[i];∥以子表的第一個(gè)記錄作樞軸，將其暫存到記錄R[0]中x=R[i].key;∥用變量x存放樞軸記錄的關(guān)鍵字while(i<j)∥從表的兩端交替地向中間掃描{while(i<j&&R[j].key>=x)j--;R[i]=R[j];∥將比樞軸小的記錄移到低端while(i<j&&R[i].key<=x)i++;R[j]=R[i];∥將比樞軸大的記錄移到高端}∥whileR[i]=R[0];∥樞軸記錄到位returni;∥返回樞軸位置}∥Partition

陪磊慕夾調(diào)莉兒襲惠烤腮毒襯嗓飲郴戌樟慢者伸叔拾潤寄簿琶屹弄女駛殺第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序36快速排序算法intPartition(RecTypeR快速排序算法voidQuickSort(RecTypeR[]，ints，intt){∥對記錄序列R[s..t]進(jìn)行快速排序if(s<t){k=Partition(R,s,t);QuickSort(R,s,k-1);QuickSort(R,k+1,t);}∥if}∥QuickSort

快速排序的平均時(shí)間復(fù)雜度為O（nlog2n）最差為O(n2)嘉祟辮等渤土幕幽蔡中鄭咬惰容好葬屯烈份粳餃顧奠笑款輔牲膠融駛緞奪第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序37快速排序算法voidQuickSort(RecTypeR對下列一組關(guān)鍵字

（46,58,15,45,90,18,10,62）

試寫出快速排序的每一趟的排序結(jié)果

委還藩潛泛底塘這隸趴猩附起咸辯瀝裂躍之竭壁盤奎叭足稀穢趴正絲將瞪第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序38對下列一組關(guān)鍵字

（46,58,15,45,90,18,1選擇排序基本思想：依次從待排序記錄序列中選擇出關(guān)鍵字值最?。ɑ蜃畲螅┑挠涗?、關(guān)鍵字值次之的記錄、……，并分別將它們定位到序列左側(cè)（或右側(cè)）的第1個(gè)位置、第2個(gè)位置、……，從而使待排序的記錄序列成為按關(guān)鍵字值由小到大（或由大到?。┡帕械挠行蛐蛄?。

選擇排序種類：

直接（簡單）選擇排序樹形選擇排序堆排序

熏睬吧始蹄遂菏述伍托蚤嗡永忻螞奧斷右創(chuàng)因涕阮甩姜鱗爵怒酣口倪杉氧第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序39選擇排序基本思想：依次從待排序記錄序列中選擇出關(guān)鍵字值最小直接選擇排序待排記錄序列的狀態(tài)為：有序序列R[1..i-1]

無序序列R[i..n]

并且有序序列中所有記錄的關(guān)鍵字均小于無序序列中記錄的關(guān)鍵字，則第i趟直接選擇排序是，從無序序列R[i..n]的n-i+1記錄中選出關(guān)鍵字最小的記錄加入有序序列

憶侯糯鹼汾晃吼噶緣堰嗅鈍用波鵬善域搐盈眺婉鄂某漂閻鋅先幢棲氈搗患第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序40直接選擇排序待排記錄序列的狀態(tài)為：有序序列R[1..直接選擇排序示例初始關(guān)鍵字序列：5133629687172851／

↑↑第一趟排序后：[17]33629687512851／↑↑第二趟排序后：[1728]

629687513351／↑↑第三趟排序后：[1728

33]

9687516251／第四趟排序后：[1728

3351]

87966251／第五趟排序后：[1728

3351

51／]966287第六趟排序后：[1728

3351

51／

62]

9687第七趟排序后：[1728

3351

51／

62

87

96]瞪窟轎操米窯苗鬃徊鐵噸畝苫夾戚拄捏挺淆枝逢糖帽對儲醚呢險(xiǎn)寨哎墩癟第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序41直接選擇排序示例初始關(guān)鍵字序列：51336直接選擇排序算法voidSelectSort(RecTypeR[]，intn){∥對記錄序列R[1..n]作直接選擇排序。for(i=1;i<n;i++)∥選擇第i小的記錄，并交換到位{k=i;∥假定第i個(gè)元素的關(guān)鍵字最小for(j=i+1;j<=n;j++)∥找最小元素的下標(biāo)if(R[j].key<R[k].key)k=j;if(i!=k)R[i]←→R[k];∥與第i個(gè)記錄交換}∥for}∥SelectSort

直接選擇排序的平均時(shí)間復(fù)雜度為O（n2）

記錄移動次數(shù)最好情況：0最壞情況：3(n-1)比較次數(shù)（與初始狀態(tài)無關(guān)）：矚橋筒媽明爭毆翅削果塵韌晰酶岡舷豈折炔擂觸瘍茂杉鷗康拙皋猾汝痰批第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序42直接選擇排序算法voidSelectSort(RecT堆的定義：堆是滿足下列性質(zhì)的數(shù)列{K1,K2,…,Kn}：

堆排序或（i=1,2,…,

n/2）

若上述數(shù)列是堆，則K1必是數(shù)列中的最小值或最大值，分別稱作小頂堆或大頂堆（小堆或大堆）。甥炮傍丫皋聞藥甕搓吭渡況嘲篡主咱萬涎稍挪釩獲信甜吭漳緞順芹釀寫郊第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序43堆的定義：堆是滿足下列性質(zhì)的數(shù)列{K1,K2,…,Kn}堆排序示例

96，51，87，33，28，62，51／，17是大頂堆

例如：17，28，51，33，62，96，87，51／是小頂堆萎?dāng)?shù)擠兄撼盡狄熾祿谷紫露紛眨編奎小脆彎女搪迭滇播彭坑主級聳墟檢拋第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序44堆排序示例

96，51，87，33，28，62，51／，17建立完全二叉樹基本思想：先建一個(gè)堆，即先選得一個(gè)關(guān)鍵字最大或最小的記錄，然后與序列中最后一個(gè)記錄交換，之后將序列中前n－1個(gè)記錄重新調(diào)整為一個(gè)堆（調(diào)堆的過程稱為“篩選”），再將堆頂記錄和第n－1個(gè)記錄交換，如此反復(fù)直至排序結(jié)束。

堆排序需解決的兩個(gè)問題：如何由一個(gè)無序序列建成一個(gè)堆？如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個(gè)新的堆？信翻廊宙桐謄課誠聶玫火磅梭諄噪癢性電鎳色艷蕭高汛窘股季稽炕劣玲喧第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序45建立完全二叉樹基本思想：先建一個(gè)堆，即先選得一個(gè)關(guān)鍵字最大或第二個(gè)問題解決方法方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆第一個(gè)問題解決方法方法：把整個(gè)數(shù)組R[1]到R[n]調(diào)整為一個(gè)大根堆，即把完全二叉樹中以每一個(gè)結(jié)點(diǎn)為根的子樹都調(diào)整為堆。所以需要將以序號為n/2，n/2－1，…，1的結(jié)點(diǎn)作為根的子樹調(diào)整為堆即可用篩選法調(diào)整堆血洞磊圖舔懷漁宰衙眉秩午字君痢謹(jǐn)毛然許茁跋蝗坷鏈搏名神氯廄割圭憶第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序46第二個(gè)問題解決方法第一個(gè)問題解決方法血洞磊圖舔懷漁宰衙眉秩午調(diào)整堆示例2851336287961751(a)堆2851336287965117(b)17與51／交換后的情景宏敘嚼自號寇鉑耍碴遮魄刃罕鏡末睡揚(yáng)繕尹堯嫁餓轍院瞧棉痛匡督前珠舶第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序47調(diào)整堆示例2851336287961751(a)堆28513調(diào)整堆示例5151876228963317(d)28與87交換后調(diào)成的新堆3351516287962817(c)調(diào)整后的新堆痰卸霉定憎禍廣瀑邯瑟牽累嶺涸褲痹恰鎬硯狹谷晚醞忍威澤迭漆脅鑲棕舜第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序48調(diào)整堆示例5151876228963317(d)28與87交建堆示例初始關(guān)鍵字序列：51，33，62，96，87，17，28，51／為例，其初始建大頂堆過程

3362968728175151(a)4..8是堆，不調(diào)整3362968728175151(b)3..8是堆，不調(diào)整溢蕉釀握薊也毀帖馮釁媳磊裂贓冤節(jié)陀瞻賭矚孤豈茨來廟某屑棱戒淆詐啥第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序49建堆示例初始關(guān)鍵字序列：51，33，62，96，87，17，建堆示例3362968728175151(c)2..8不是堆，進(jìn)行篩選9662518728175133(d)1..8不是堆，進(jìn)行篩選8762515128179633(e)建成的大頂堆展絡(luò)視許仰端仍魔翠藩錢猩蹈焉屈之炭責(zé)贊砒扳覺蝶疇鎬掖栽呻攏惹棠葛第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序50建堆示例3362968728175151(c)2..8不是堆堆排序篩選算法voidSift(RecTypeR[]，inti，intm){∥假設(shè)R[i+1..m]中各元素滿足堆的定義，本算法調(diào)整R[i]使序列∥R[i..m]中各元素滿足堆的性質(zhì)R[0]=R[i];for(j=2*i;j<=m;j*=2){if(j<m&&R[j].key<R[j+l].key)j++;∥沿大者（右）方向篩選if(R[0].key<R[j].key){R[i]=R[j];i=j;}elsebreak;}∥forR[i]=R[0];}∥Sift滬趣衙干達(dá)對腥樟鐘故訛茶幢災(zāi)吱誅河錠瘋袱砷蛛須魯絲稼轟乃榜贊蘿攏第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序51堆排序篩選算法voidSift(RecTypeR[]堆排序算法voidHeapSort(RecTypeR[]，intn){∥對記錄序列R[1..n]進(jìn)行堆排序。

for(i=n/2;i>0;i--)∥把R[1..n]建成大頂堆Sift(R,i,n);

for(i=n;i>1;i--)∥輸出并調(diào)堆{R[1]←→R[i];Sift(R,1,i-1);∥將R[1..i-1]重新調(diào)整為大頂堆}∥for}∥HeapSort

堆排序的時(shí)間復(fù)雜度為O（nlog2n）

銥還候凍即釁夜摯啼愚瘟竊頒部閻渠踐脹拇枕東互袁晴載真挽貉午乖巷劇第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序52堆排序算法voidHeapSort(RecType時(shí)間復(fù)雜度：最壞情況下T(n)=O(nlogn)

建初始堆時(shí)間：調(diào)用SIFT過程n/2次，每次以R[i]為根的子樹調(diào)整為堆。具有n個(gè)結(jié)點(diǎn)的完全二叉樹深度是h=logn+1,第i層結(jié)點(diǎn)個(gè)數(shù)至多為2i-1。SIFT對深度為k的完全二叉樹進(jìn)行比較的關(guān)鍵字次數(shù)至多為2(k-1)，因此比較總次數(shù)不超過C1(n)＝2i-1*2(h-1)

=2h-1+2h-2*2+2h-3*3+…+2*(h-1)<=2*2(log2n)+1=4n重新建堆時(shí)間：排序過程中重新建堆比較總次數(shù)不超過C2(n)=2*(logn-1

+logn-2+…+log2

)<2nlogn

=O(nlogn)哪涕帝微驚惶悼據(jù)棟岳哪慧剎漲前蹈勺寓揉乘疚且脾唬倉獅蜒府暢爹肆來第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序53時(shí)間復(fù)雜度：最壞情況下T(n)=O(nlogn)哪涕帝微驚惶

已知一組關(guān)鍵字

（46,58,15,45,90,18,10,62）

試寫出堆排序建初始堆和排序的過程

鄭性亮蔽乘注鄉(xiāng)槽遇荊氓垃劇砸怒巍才樸哥傾懦酌懦玖斃遍啄眺柔糞佬怔第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序54已知一組關(guān)鍵字

（46,58,15,45,90,18,歸并排序基本思想：將一個(gè)具有n個(gè)待排序記錄的序列看成是n個(gè)長度為1的有序序列，然后進(jìn)行兩兩歸并，得到「n/2個(gè)長度為2的有序序列，再進(jìn)行兩兩歸并，得到「n/4個(gè)長度為4的有序序列，如此重復(fù)，直至得到一個(gè)長度為n的有序序列為止

艱辜支見咖單滯彼桃凍納激琺有虞飄野雕哇被英依吐抨份撾夫芋臉打諷崇第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序55歸并排序基本思想：將一個(gè)具有n個(gè)待排序記錄的序列看成是歸并排序示例二趟歸并排序后：[33516296]

[1728

87]

初始關(guān)鍵字序列：[51]

[33]

[62]

[96]

[87]

[17]

[28]

一趟歸并排序后：[3351]

[6296]

[1787]

[28]

三趟歸并排序后：[17

28335162

8796]寧俄講泰皿枷訖伙偏擠瑩筑汗酪虐敞齋需鋒痢贓準(zhǔn)魄繼院姬滅疑北農(nóng)緯評第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序56歸并排序示例二趟歸并排序后：[3351一趟歸并排序算法voidMerge(RecTypeR[],RecTypeR1[],inti,intl,inth){∥將有序的R[i..l]和R[l+1..h]歸并為有序的R1[i..h]

for(j=l+1,k=i;i<=l&&j<=h;k++)∥R中記錄由小到大地并入R1if(R[i].key<=R[j].key)R1[k]=R[i++];elseR1[k]=R[j++];if(i<=l)R1[k..h]=R[i..l];∥將剩余的R[i..l]復(fù)制到R1if(j<=h)R1[k..h]=R[j..h];∥將剩余的R[j..h]復(fù)制到R1}∥Merge萄譬膊洗夢礙片訪誘櫥灑楞叭沉茶猖躬鴦曰靡隨送于瞞他施啟碗達(dá)廁此靛第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序57一趟歸并排序算法voidMerge(RecTypeR歸并排序算法voidMsort(RecTypeR[],RecTypeR1[],ints,intt){∥將R[s..t]進(jìn)行2-路歸并排序?yàn)镽1[s..t]if(s==t)R1[s]=R[s];else{m=(s+t)/2;∥將R[s..t]平分為R[s..m]和R[m+1..t]Msort(R,R2,s,m);∥遞歸地將R[s..m]歸并為有序的R2[s..m]Msort(R,R2,m+1,t);∥遞歸地R[m+1..t]歸并為有序的R2[m+1..t]Merge(R2,R1,s,m,t);∥將R2[s..m]和R2[m+1..t]歸并到R1[s..t]}∥if}∥MSort粒鈾慌侖艙閣鍋亞職嫂滁諒莖帥革欄軀癟獺刪魔啊蜀撇斑鎖嘯商且撤似糠第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序58歸并排序算法voidMsort(RecTypeR[歸并排序算法voidMergeSort(RecTypeR[],intn){∥對記錄序列R[1..n]作2-路歸并排序。

MSort(R,R,1,n);}∥MergeSort歸并排序的設(shè)計(jì)復(fù)雜度為O(nlogn)迭還獄所爬洽秩誦瞇蒼滴獵甲撼耘泉?dú)q裔羌唬足刻論謀沿緯筋侈沛戰(zhàn)濤悲第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序59歸并排序算法voidMergeSort(RecType分配排序基本思想：利用關(guān)鍵字的結(jié)構(gòu)，通過“分配”和“收集”的辦法來實(shí)現(xiàn)排序

分配排序可分為桶排序和基數(shù)排序兩類

戲撲兌身式嫉齒榴助雀眩遷號汀妨瑰崔趴佯荒刃砍泡腳歪殿薔苗釋戈休瓤第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序60分配排序基本思想：利用關(guān)鍵字的結(jié)構(gòu)，通過“分配”和“收集”桶排序桶排序（BucketSort）也稱箱排序（BinSort），其基本思想是：設(shè)置若干個(gè)桶，依次掃描待排序記錄R[1..n]，把關(guān)鍵字等于k的記錄全部都裝到第k個(gè)桶里（分配），然后，按序號依次將各非空的桶首尾連接起來（收集）。

藏瓷傳藹史衫贍瀑崩盒蓋峨蛾拭裳屈纓殆碰慧勝讀睡椿召吞揩催量豢螺顱第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序61桶排序桶排序（BucketSort）也稱箱排序（BinS基數(shù)排序

基數(shù)排序就是一種借助“多關(guān)鍵字排序”的思想來實(shí)現(xiàn)“單關(guān)鍵字排序”的算法假設(shè)有n個(gè)記錄待排序序列{R1,R2,…，Rn}，每個(gè)記錄Ri中含有d個(gè)關(guān)鍵字(Ki0,Ki1,…,Kid-1),則稱上述記錄序列對關(guān)鍵字(Ki0,Ki1,…,Kid-1)有序是指：對于序列中任意兩個(gè)記錄Ri和Rj(1≤i<j≤n)都滿足下列(詞典)有序關(guān)系：(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-1)其中K0被稱為“最主”位關(guān)鍵字，Kd-1被稱為“最次”位關(guān)鍵字。身讒酵邢唯冪幣甚悼欄蕊寡是惕制翱臥擴(kuò)廁郎嗡謅價(jià)碌蠢勞廓惦普瑚桅哪第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序62基數(shù)排序基數(shù)排序就是一種借助“多關(guān)鍵字排序”的思想最高位優(yōu)先MSD法：先對K0進(jìn)行排序，并按K0的不同值將記錄序列分成若干子序列之后，分別對K1進(jìn)行排序，…，依次類推，直至最后對最次位關(guān)鍵字排序完成為止。最低位優(yōu)先LSD法：先對Kd-1進(jìn)行排序，然后對Kd-2進(jìn)行排序，依次類推，直至對最主位關(guān)鍵字K0排序完成為止。排序過程中不需要根據(jù)“前一個(gè)”關(guān)鍵字的排序結(jié)果，將記錄序列分割成若干個(gè)(“前一個(gè)”關(guān)鍵字不同的)子序列。實(shí)現(xiàn)多關(guān)鍵字排序通常有兩種作法:它掌費(fèi)喇駕媒并潛孔茫除班溯匝器護(hù)亥蘇果兌初鋁鄖億嘗火賓毅趾淘泅橋第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序63最高位優(yōu)先MSD法：先對K0進(jìn)行排序，并按K0的不同值將記錄基數(shù)排序示例p→369→367→167→239→237→138→230→139第一次分配得到：B[0].f→230←B[0].eB[7].f→367→167→237←B[7].eB[8].f→138←B[8].eB[9].f→369→239→139←B[9].e第一次收集得到：p→230→367→167→237→138→369→239→139舶有從淹札冒易弗招受籽贊儡南老雖肇犬忘醋鳴粕塞軋醬追吏墾憾懲傲睬第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序64基數(shù)排序示例p→369→367→167→239→237→13基數(shù)排序示例第二次分配得到：B[3].f→230→237→138→239→139←B[3].eB[6].f→367→167→369←B[6].e第二次收集得到：p→230→237→138→239→139→367→167→369閘圖蛇鄧陡臭析槐釘劊磋拱誰眶碑港醚宅鴿對迫鞭凌霸褪慣道筒巫認(rèn)焊潰第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序65基數(shù)排序示例第二次分配得到：閘圖蛇鄧陡臭析槐釘劊磋拱誰眶碑港基數(shù)排序示例第三次分配得到：B[1].f→138→139→167←B[1].eB[2].f→230→237→239←B[2].eB[3].f→367→369←B[3].e第三次收集之后便得到記錄的有序序列：p→138→139→167→230→237→239→367→369

蓖欄直幟俞堅(jiān)特眺答敦哉廬舞捷憤瘓注賽借欽抿咸唉鹵裔咳籌賜昂貿(mào)丫返第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序66基數(shù)排序示例第三次分配得到：蓖欄直幟俞堅(jiān)特眺答敦哉廬舞捷憤瘓基數(shù)排序的類型定義#definen待排序記錄的個(gè)數(shù)typedefstruct{intkey[d];∥關(guān)鍵字由d個(gè)分量組成intnext;∥靜態(tài)鏈域AnyTypeother;∥記錄其他數(shù)據(jù)域}SLRecType;SLRecTypeR[n+1];∥R[1..n]存放n個(gè)待排序記錄typedefstruct{intf,e;∥隊(duì)列的頭、尾指針}SLQueue;SLQueueB[m]∥用隊(duì)列表示桶，共m個(gè)拖急啤圓福婆除熾敞究熱悟舜娥君枷譚忘煥阮手捉轟普史館淬漚退昧舀訊第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序67基數(shù)排序的類型定義#definen待排序記錄的個(gè)數(shù)拖基數(shù)排序的算法intRadixSort(SLRecTypeR[],intn){∥對R[1..n]進(jìn)行基數(shù)排序，返回收集用的鏈頭指針for(i=1;i<n;i++)∥將R[1..n]鏈成一個(gè)靜態(tài)鏈表R[i].next=i+1;R[n].next=-1;∥將初始鏈表的終端結(jié)點(diǎn)指針置空p=1;∥p指向鏈表的第一個(gè)結(jié)點(diǎn)

for(j=d-1;j>=0;j--)∥進(jìn)行d趟排序{for(i=0;i<m;i++)∥初始化桶

{B[i].f=-1;B[i].e=-1;}∥for

while(p!=-1)∥一趟分配，按關(guān)鍵字的第j個(gè)分量進(jìn)行分配{k=R[p].key[j];∥k為桶的序號if(B[k].f==-1)B[k].f=p;∥B[k]為空桶，將R[p]鏈到桶頭elseR[B[k].e].next=p;∥將R[p]鏈到桶尾B[k].e=p;∥修改桶的尾指針p=R[p].next;∥掃描下一個(gè)記錄}∥while＝＝＝接下頁＝＝＝

抬署公梨略圣潦塞少帆蕪竣躺桂押重頑遣插加嚴(yán)分蔽壹巖坦愉樓溯淀誘映第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序68基數(shù)排序的算法intRadixSort(SLRecTy基數(shù)排序的算法（續(xù)）＝＝＝接上頁＝＝＝i=0;//一趟收集while(B[i].f==-1)i++;∥找第一個(gè)非空的桶t=B[i].e;p=B[i].f∥p為收集鏈表的頭指針，t為尾指針while(i<m-1){i++;∥取下一個(gè)桶if(B[i].f!=-1){R[t].next=B[i].f;t=B[i].e;}∥連接非空桶}∥whileR[t].next=-1;∥本趟收集完畢，將鏈表的終端結(jié)點(diǎn)指針置空

}∥forreturnp;}∥RadixSort千堅(jiān)訝憎晦緩廟椎迄翱沏撻輝娜切屎驅(qū)作恫氯入侄鏈乞術(shù)葫浦沈炯考韻緘第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序69基數(shù)排序的算法（續(xù)）＝＝＝接上頁＝＝＝千堅(jiān)訝憎晦緩廟椎迄翱沏基數(shù)排序的性能分析基數(shù)排序的時(shí)間復(fù)雜度是O(d*(rd+n))。當(dāng)n較小、d較大時(shí)，基數(shù)排序并不合適。只有當(dāng)n較大、d較小時(shí)，特別是記錄的信息量較大時(shí)，基數(shù)排序最為有效?；鶖?shù)排序存儲空間復(fù)雜度為O（rd）?；鶖?shù)排序是穩(wěn)定的。

啊市瑤裁秘剃屯屁宗吳廣踏粳潤席默虜故紐邊陽蔓蔭吊嘆己哇偶卉朵坎評第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序70基數(shù)排序的性能分析基數(shù)排序的時(shí)間復(fù)雜度是O(d*(rd+已知8個(gè)記錄，其關(guān)鍵字分別為(179，208，306，093，859，984，271，033)試用基數(shù)排序法實(shí)施排序，描述其排序過程舅薄跡隕歷詹培魏暇勒傷傲服屈冠詹姬資抉戶仇括粥都氖位茫亡菱芯龍諷第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序71已知8個(gè)記錄，其關(guān)鍵字分別為(179，208，306，093排序方法平均時(shí)間最壞情況輔助空間穩(wěn)定性直接插入排序O（n2）O（n2）O（1）穩(wěn)定起泡排序O（n2）O（n2）O（1）穩(wěn)定直接選擇排序O（n2）O（n2）O（1）不穩(wěn)定希爾排序O（n1.3）O（n1.3）O（1）不穩(wěn)定快速排序O（nlog2n）O（n2）O（log2n）不穩(wěn)定堆排序O（nlog2n）O（nlog2n）O（1）不穩(wěn)定2-路歸并排序O（nlog2n）O（nlog2n）O（n）穩(wěn)定基數(shù)排序O(d*(rd+n))O(d*(rd+n))O(rd)穩(wěn)定內(nèi)部排序方法的比較拌姨私憎奧螞兵懇屑螞艷思績斑秉森壽渤秀卻篷涵迄友技卯媚桌倉第歡窯第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序72排序方法平均時(shí)間最壞情況輔助空間穩(wěn)定性直接插入排序O（n2）結(jié)論（1）若n較小（如n≤50），可采用直接插入排序或直接選擇排序。（2）若待排序記錄的初始狀態(tài)已是按關(guān)鍵字基本有序，則選用直接插入排序或起泡排序?yàn)橐恕＃?）當(dāng)n較大，若關(guān)鍵字有明顯結(jié)構(gòu)特征（如字符串、整數(shù)等），且關(guān)鍵字位數(shù)較少易于分解，采用時(shí)間性能是線性的基數(shù)排序較好。若關(guān)鍵字無明顯結(jié)構(gòu)特征或取值范圍屬于某個(gè)無窮集合（例如實(shí)數(shù)型關(guān)鍵字）時(shí)，應(yīng)借助于“比較”的方法來排序，可采用時(shí)間復(fù)雜度為O（nlog2n）的排序方法：快速排序、堆排序或歸并排序。炭等也太斯糊空湍沸捐夢駛攝搗掐站錐藍(lán)興虱頗碌逮孜驗(yàn)籬熒品蜀席蔽漆第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序73結(jié)論（1）若n較?。ㄈ鏽≤50），可采用直接插入排序或直接選（4）對于以主關(guān)鍵字進(jìn)行排序的記錄序列，所用的排序方法是否穩(wěn)定無關(guān)緊要，而用次關(guān)鍵字進(jìn)行排序的記錄序列，應(yīng)根據(jù)具體問題所需慎重選擇排序方法及描述算法。（5）前面討論的排序算法，大都是利用一維向量實(shí)現(xiàn)的。若記錄本身信息量大，為避免移動記錄耗費(fèi)大量時(shí)間，可用鏈?zhǔn)酱鎯Y(jié)構(gòu)。比如插入排序和歸并排序都易于在鏈表上實(shí)現(xiàn)。但象快速排序和堆排序這樣的排序算法，卻難于在鏈表上實(shí)現(xiàn)，此時(shí)可以提取關(guān)鍵字建立索引表，然后對索引表進(jìn)行排序。晉篆敵奇葉帆鄙盾挖離鉗餾吮迄氏暢需穎鉆靠糞轍允阜攤遼寵幢墨蔓周沉第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序74（4）對于以主關(guān)鍵字進(jìn)行排序的記錄序列，所用的排序方法是否穩(wěn)以關(guān)鍵碼序列（503，087，512，061，908，170，897，275，653，246）為例，手工執(zhí)行以下排序算法，寫出每一趟排序結(jié)束時(shí)的關(guān)鍵碼狀態(tài)：（1）直接插入排序；（2）希爾排序（增量5，3，1）；（3）起泡排序（4）快速排序；（5）簡單選擇排序（6）堆排序；（7）歸并排序；（8）基數(shù)排序。旦緩琵甚龔酋龜址志瓜廁唉輸鼠廄恐侵念而體囊貳洞斟兜蹤孔幌扯阮艱蓬第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序75以關(guān)鍵碼序列（503，087，512，061外部排序的兩個(gè)階段1、生成順串2、合并順串耍嫁涵長妊籽隆郵西童梨發(fā)虎網(wǎng)儉黎琢輯約壟碟綁儒報(bào)獎財(cái)蹦利壹靖刊替第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序76外部排序的兩個(gè)階段1、生成順串耍嫁涵長妊籽隆郵西童梨發(fā)虎網(wǎng)外部排序分析

外部排序所需總時(shí)間T=m*tI+d*tI/O+s*ntm其中tI是構(gòu)造一個(gè)初始?xì)w并段所需內(nèi)部排序的平均時(shí)間；tI/O是進(jìn)行一次外存讀/寫的平均時(shí)間；tm是對一個(gè)記錄進(jìn)行內(nèi)部歸并所需時(shí)間；n為記錄個(gè)數(shù)；m為初始?xì)w并段的個(gè)數(shù)；s為歸并的趟數(shù)；d為總的讀/寫次數(shù)

炊農(nóng)惕磐落巴碳樂綜犬小哇至毀沾三夠文幅恐韶站絕拐與烘拋元螟德蠻鷗第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序77外部排序分析外部排序所需總時(shí)間炊農(nóng)惕磐落外部排序分析

池頰弓砒醛衣鴻沸奏段葉筐聲鄂涌晦棘雍胖守文獸偽幣羅銻暴滅柑越州奔第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序78外部排序分析池頰弓砒醛衣鴻沸奏段葉筐聲鄂涌多路歸并排序k-路歸并，n個(gè)記錄分布在k個(gè)歸并段上，從k個(gè)記錄中選出一個(gè)最小記錄需進(jìn)行k－1次比較，一趟歸并要得到全部n個(gè)記錄共需進(jìn)行(n－1)(k－1)次比較。此k-路歸并排序的內(nèi)部歸并過程中進(jìn)行的總的比較次數(shù)為s(n－1)(k－1)。故有：常股扭駿護(hù)牡睬海沖攤陣賃具腋校斥冊縛隧別賴灤測暴濕烘改嫉琴柴董構(gòu)第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序79多路歸并排序k-路歸并，n個(gè)記錄分布在k個(gè)歸敗者樹

敗者樹是一顆完全二叉樹葉結(jié)點(diǎn)存放參加比較的記錄非葉結(jié)點(diǎn)記憶其子女結(jié)點(diǎn)中的敗者根結(jié)點(diǎn)之上的結(jié)點(diǎn)存放最后的勝者疹杜輻凈腆灣六沁申氫溫冕俊通偉撕殖品跑渝吸崩勺陷捌改旁秘酵俺泛龐第10章數(shù)據(jù)結(jié)構(gòu)排序第10章數(shù)據(jù)結(jié)構(gòu)排序80敗者樹敗者樹是一顆完全二叉樹疹杜輻凈腆灣六沁申氫溫冕俊實(shí)現(xiàn)5-路歸并的敗者樹029201031461525∞123748∞1015