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

數(shù)據(jù)結(jié)構(gòu)第10章內(nèi)部排序信息工程學(xué)院衷璐潔概述插入排序快速排序選擇排序歸并排序基數(shù)排序各種內(nèi)部排序方法的比較討論本講主要內(nèi)容一、排序的定義

假設(shè)含n個(gè)記錄的序列為{R1,R2,…,Rn}其相應(yīng)的關(guān)鍵字序列為{K1,K2,…,Kn}需確定1,2,…,n的一種排列p1,p2,…,pn，使其相應(yīng)的關(guān)鍵字滿足如下的非遞減(或非遞增)關(guān)系：

Kp1

≤

Kp2≤

…≤

Kpn即使序列{R1,R2,…,Rn}成為一個(gè)按關(guān)鍵字有序的序列{Rp1,Rp2,…,Rpn}這樣一種操作稱為排序

關(guān)鍵字Ki可以是記錄Ri的主關(guān)鍵字【排序結(jié)果唯一】、次關(guān)鍵字或若干數(shù)據(jù)項(xiàng)的組合【排序結(jié)果不唯一】假設(shè)：(1)在待排序序列中存在兩個(gè)(以上)關(guān)鍵字相等的記錄Ri和Rj，即：Ki=Kj

(1≤i,j≤n，i≠j)

(2)在排序前的序列中Ri領(lǐng)先于Rj

(即：i<j)那么：若排序后Ri仍領(lǐng)先于Rj

，則稱所用的排序方法是穩(wěn)定的；否則，稱所用的排序方法是不穩(wěn)定的

【對(duì)不穩(wěn)定的排序方法，只需舉出一組關(guān)鍵字實(shí)例說明其不穩(wěn)定性即可】二、排序方法的穩(wěn)定性

按排序過程中涉及存儲(chǔ)器的不同，可將排序方法分為兩大類：內(nèi)部排序：待排序記錄存放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器(內(nèi)存)中進(jìn)行的排序過程外部排序：待排序記錄的數(shù)量很大，內(nèi)存一次不能容納全部記錄，還需外存輔助的排序過程三、排序的分類按排序過程中依據(jù)的不同原則大致可分為：按內(nèi)部排序過程所需的工作量分：插入排序交換排序選擇排序歸并排序基數(shù)排序(1)簡(jiǎn)單的排序方法——O(n2)(2)先進(jìn)的排序方法——O(nlog2n)(3)基數(shù)排序——O(d·n)四、內(nèi)部排序方法(1)比較：比較兩個(gè)關(guān)鍵字的大小大多數(shù)排序都需要(2)移動(dòng)：將記錄從一個(gè)位置移到另一個(gè)位置可通過改變記錄的存儲(chǔ)方式避免五、大多數(shù)排序的兩種基本操作排序時(shí)必須移動(dòng)記錄(2)靜態(tài)鏈表存儲(chǔ)——(鏈)表排序排序時(shí)不移動(dòng)記錄，僅需修改指針(3)順序存儲(chǔ)＋地址向量＝地址排序排序時(shí)不移動(dòng)記錄，而是移動(dòng)地址向量中的“地址”排序結(jié)束后再按地址向量中的值調(diào)整記錄的存儲(chǔ)位置六、排序記錄的存儲(chǔ)方式(1)順序存儲(chǔ)待排記錄的數(shù)據(jù)類型：#defineMAXSIZE20//順序表的最大長(zhǎng)度typedefintKeyType;//關(guān)鍵字類型typedefstruct{

KeyType

key;//關(guān)鍵字InfoTypeotherinfo;//其它數(shù)據(jù)項(xiàng)}RedType;//記錄類型typedefstruct{

RedType

r[MAXSIZE+1];//r[0]閑置或用作哨兵單元intlength;//順序表長(zhǎng)度}SqList;//順序表類型概述插入排序快速排序選擇排序歸并排序基數(shù)排序各種內(nèi)部排序方法的比較討論本講主要內(nèi)容一、直接插入排序方法：將一個(gè)記錄插入到已排好序的有序表中，得到一個(gè)新的、記錄數(shù)增1的有序表：（1）把序列(R(K1))看成是一個(gè)有序的子序列把R(K2)插入到該序列中,使插入后序列(R(K1),R(K2))有序（2）把R(K3)插入到(R(K1),R(K2))中，使插入后有序（3）重復(fù)（2），直到插入R(Kn)為止。10.2插入排序49，38，65，97，76，13，2749384938496538496597384965769713384965769713273849657697//對(duì)順序表L作直接插入排序的算法voidInsertSort(SqList&L){//算法10.1for(i=2;i<=L.length;++i)

//"<"時(shí)，需將L.r[i]插入有序子表

if(LT(L.r[i].key,L.r[i-1].key)){

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

for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];

//記錄后移

L.r[j+1]=L.r[0];

//插入到正確位置}}//InsertSort[576489]6某趟插入排序:復(fù)制為哨兵j89j64j7j6i直接插入排序的時(shí)間復(fù)雜度：O(n2)二、其它插入排序直接插入排序適合待排序數(shù)量n很小的情況，若n很大，則不宜采用為此，從減少“比較”和“移動(dòng)”這兩種操作的次數(shù)考慮，可有以下幾種排序的方法：(1)折半插入排序(2)2-路插入排序(3)表插入排序(4)希爾排序(1)折半插入排序做法：用折半查找的方法找到插入位置

例：在序列{13，27，35，48，65，72}中插入20或603565132748722060//對(duì)順序表L作折半插入排序voidBInsertSort(SqList&L){//算法10.2for(i=2;i<=L.length;++i){

L.r[0]=L.r[i];//將L.r[i]暫存到L.r[0]low=1;high=i-1;while(low<=high){//在r[low..high]中折半查找有序插入的位置

m=(low+high)/2;//折半

if(LT(L.r[0].key,L.r[m].key))high=m-1;//插入點(diǎn)在低半?yún)^(qū)

elselow=m+1;

//插入點(diǎn)在高半?yún)^(qū)}

for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];

//記錄后移

L.r[high+1]=L.r[0];

//插入}}//BInsertSort[576489]246將L.r[i]暫存于L.r[0]89647low6mhigh折半插入排序的時(shí)間復(fù)雜度：O(n2)low(2)希爾排序又稱“縮小增量排序”(DiminishingIncrementSort)希爾排序的基本思想：(1)先將整個(gè)待排記錄序列分割成若干子序列(2)分別對(duì)這些子序列進(jìn)行直接插入排序(3)待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序增量序列為：5，3，149

38

65

977613

27

4913

27

49

977649

386513

27

49

97

76

49

386513

27

49

38

65

49

97761327384949657697/*對(duì)順序表L作一趟希爾插入排序。本算法對(duì)算法10.1作了以下修改：1.前后記錄位置的增量是dk，而不是1；2.r[0]只是暫存單元，不是哨兵。當(dāng)j<=0時(shí)，插入位置已找到*/voidShellInsert(SqList&L,intdk){//算法10.4for(i=dk+1;i<=L.length;++i)

//需將L.r[i]插入有序增量子表if(LT(L.r[i].key,L.r[i-dk].key)){

L.r[0]=L.r[i];//暫存在L.r[0]for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk)L.r[j+dk]=L.r[j];//記錄后移，查找插入位置

L.r[j+dk]=L.r[0];//插入}}//ShellInsert/*按增量序列dlta[0..t-1]對(duì)順序表L作希爾排序*/voidShellSort(SqList&L,intdlta[],intt){//算法10.5

for(k=0;k<t;++k)ShellInsert(L,dlta[k]);//一趟增量為dlta[k]的插入排序}//ShellSort希爾排序的時(shí)間是所取“增量”序列的函數(shù)，涉及一些數(shù)學(xué)上的尚未解決的難題概述插入排序快速排序選擇排序歸并排序基數(shù)排序各種內(nèi)部排序方法的比較討論本講主要內(nèi)容快速排序是一種借助“交換”進(jìn)行排序的方法10.3快速排序一、起泡排序（BubbleSort)一趟排序voidBubbleSort(SqList&L){for(i=1;i<n;i++){change=FALSE;for(j=1;j<n-i+1;j++)if(L.r[j].key>L.r[j+1].key){change=TRUE;L.r[j]L.r[j+1];}

if(!change)return;}}共進(jìn)行n-1趟排序，共進(jìn)行n(n-1)/2次比較T(n)=O(n2)快速排序是對(duì)起泡排序的一種改進(jìn)基本思想：通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小則再分別對(duì)這兩部分的記錄繼續(xù)進(jìn)行排序最后達(dá)到整個(gè)序列有序二、快速排序（QuickSort)假設(shè)待排序序列為{L.r[s]，L.r[s+1]，…，L.r[t]}首先任意選取一個(gè)記錄(一般為第一個(gè)記錄L.r[s])作為樞軸(或支點(diǎn))(pivot)然后按下述原則重新排列其余記錄：將所有關(guān)鍵字比它小的記錄都安置在樞軸之前將所有關(guān)鍵字比它大的記錄都安置在樞軸之后由此，以該“樞軸”記錄最后所落的位置i作分界線，將序列{L.r[s]，L.r[s+1]，…，L.r[t]}分割成兩個(gè)子序列：{L.r[s]，L.r[s+1]，…，L.r[i-1]}和{L.r[i+1]，L.r[i+2]，…，L.r[t]}這個(gè)過程稱作一趟快速排序(或一次劃分)4938659776132749i27386597761349

492738499776136549jiiijjijj2738139776496549iji2738134976976549ij27381376976549jj具體實(shí)現(xiàn)：

low=s;high=t;pivotkey=L.r[low].key;(1)從high開始往前找第一個(gè)關(guān)鍵字小于pivotkey的記錄，與樞軸記錄交換

(2)從low開始往后找第一個(gè)關(guān)鍵字大于pivotkey的記錄，與樞軸記錄交換

(3)重復(fù)（1）（2）直到low==high為止此時(shí)樞軸記錄所在的位置i=low=high273813497697654913

27

384965

76

97/*算法10.6(a)交換順序表L中子表L.r[low..high]的記錄，使樞軸記錄到位，并返回其所在位置，此時(shí)在它之前(后)的記錄均不大(小)于它*/每交換一對(duì)記錄需進(jìn)行3次記錄移動(dòng)(賦值)操作！但對(duì)樞軸記錄的賦值是多余的！只有在一趟排序結(jié)束low=high的位置才是樞軸的最后位置，改寫該算法！intPartition(SqList&L,intlow,inthigh){pivotkey=L.r[low].key;//用子表的第一個(gè)記錄作樞軸記錄

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[low]←→L.r[high];//將比樞軸記錄大的記錄交換到高端}returnlow;//返回樞軸位置}//Partition//改進(jìn)后的算法10.6(b)intPartition(SqList&L,intlow,inthigh){L.r[0]=L.r[low];//用子表的第一個(gè)記錄作樞軸記錄pivotkey=L.r[low].key;//樞軸記錄關(guān)鍵字

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;//返回樞軸位置}//Partition//對(duì)順序表L作快速排序//遞歸形式的快速排序算法//對(duì)順序表L的子序列L.r[low..high]作快速排序voidQSort(SqList&L,intlow,inthigh){if(low<high){

//長(zhǎng)度大于1

//將L.r[low..high]一分為二

pivotloc=Partition(L,low,high);//pivotloc是樞軸位置

QSort(L,low,pivotloc-1);//對(duì)低子表遞歸排序

QSort(L,pivotloc+1,high);//對(duì)高子表遞歸排序

}}//QSortvoidQuickSort(SqList&L){

QSort(L,1,L.length);}//QuickSortT(n)=O(nlog2n)快速排序的平均時(shí)間為Tavg=knlnn其中：n為待排序序列中記錄的個(gè)數(shù)，k為某個(gè)常數(shù)就平均時(shí)間而言，快速排序是目前被認(rèn)為是最好的一種內(nèi)部排序方法但是：若初始記錄序列按關(guān)鍵字有序或基本有序時(shí)，快速排序蛻化為起泡排序，其時(shí)間復(fù)雜度為O(n2)從空間上看：之前討論的各種方法，除2-路插入排序外，都只需要一個(gè)記錄的附加空間，但快速排序需要一個(gè)?？臻g來實(shí)現(xiàn)遞歸。概述插入排序快速排序選擇排序歸并排序基數(shù)排序各種內(nèi)部排序方法的比較討論本講主要內(nèi)容10.4選擇排序251608254921490816252521212525160849162108一、簡(jiǎn)單選擇排序（SelectSort)2516082549214925012345081625212549252116082525//對(duì)順序表L作簡(jiǎn)單選擇排序voidSelectSort(SqList&L){for(i=1;i<L.length;++i){//選擇第i小的記錄，并交換到位j=SelectMinKey(L,i);//在L.r[i..L.length]中選擇key最小的記錄if(i!=j)L.r[i]←→L.r[j];//與第i個(gè)記錄交換}}//SelectSortintSelectMinKey(SqListL,intk){//在L.r[k..L.length]中選擇key最小的記錄并返回它的位置

min=L.r[k].key;minp=k;for(i=k+1;i<=L.length;i++)if(L.r[i].key<min){min=L.r[i].key;minp=i;}returnminp;}共進(jìn)行n-1趟排序，n(n-1)/2次比較時(shí)間復(fù)雜度O(n2)TreeSelectionSort，又稱錦標(biāo)賽排序(TournamentSort)該過程可用一棵有n個(gè)葉子結(jié)點(diǎn)的完全二叉樹表示

將葉子結(jié)點(diǎn)中最小關(guān)鍵字改為MAXINT，然后該葉子與其左/右兄弟關(guān)鍵字比較依次修改從葉子到根的路徑上各結(jié)點(diǎn)的關(guān)鍵字值則根結(jié)點(diǎn)為次小記錄不斷重復(fù)，直到葉子結(jié)點(diǎn)均為MAXINT為止。是一種按錦標(biāo)賽的思想進(jìn)行排序的方法首先對(duì)n個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較然后在其中個(gè)較小者之間再進(jìn)行兩兩比較如此重復(fù)，直至選出最小關(guān)鍵字的記錄為止二、樹形選擇排序082108086325212125492516086395a[0]a[1]1621161663252121254925166395a[2]212163632521212549256395a[3]2525636325252549256395a[4]252563632549256395a[5]4949636349496395a[6]6363636395a[7]95959595堆定義如下：

n個(gè)元素的序列{k1,k2,…,kn}當(dāng)且僅當(dāng)滿足如下關(guān)系時(shí)，稱之為堆ki≤k2i（或ki≥k2i）ki≤k2i+1（或ki≥k2i+1）

i=1,2,…,三、堆排序（HeapSort)

若用一個(gè)一維數(shù)組存放滿足此關(guān)系的序列，把這個(gè)一維數(shù)組看成是一棵完全二叉樹，則堆對(duì)應(yīng)的完全二叉樹中所有非終端結(jié)點(diǎn)的值均大于或均小于其左右孩子的值。小頂堆大頂堆大頂堆/大根堆堆排序（從小到大）方法：（1）由一個(gè)無序的序列建成一個(gè)堆（2）輸出堆頂?shù)淖钚≈担?）剩余的元素建成一個(gè)新的堆（4）重復(fù)（2）（3）093811962783小頂堆/小根堆30854712243691534938659776132749輸出13后,用序列中最后一個(gè)記錄代替根結(jié)點(diǎn)篩選為小頂堆堆頂元素與它的左右子樹根結(jié)點(diǎn)比較：（1）若右子樹根<左子樹根<堆頂根結(jié)點(diǎn)與右子樹根交換（2）若左子樹根<右子樹根<堆頂根結(jié)點(diǎn)與左子樹根交換這個(gè)調(diào)整過程稱為篩選1338497697276549973849762765492738497649659749386597761327497627496538974913496538977649659749273813對(duì)一個(gè)無序序列建立堆也是篩選過程,篩選從第個(gè)記錄開始（1）初建堆首先將序列表示成完全二叉樹的形式從第個(gè)記錄開始調(diào)整，假設(shè)要建大頂堆4997657649273813初建堆（大頂堆）完成499765764927381349386576492797134976654938279713（2）堆排序重新調(diào)整成堆第1趟堆排序完成將堆頂與序列中未排序的最后一個(gè)元素互換497665493827971349276549387697134965274938769713第2趟堆排序完成將堆頂與序列中未排序的最后一個(gè)元素互換重新調(diào)整成堆496527493876971349132749387697651349274938769765第3趟堆排序完成將堆頂與序列中未排序的最后一個(gè)元素互換重新調(diào)整成堆134927493876976549132749387697654949273813769765第4趟堆排序完成重新調(diào)整成堆將堆頂與序列中未排序的最后一個(gè)元素互換494927381376976549132738497697654938271349769765第5趟堆排序完成重新調(diào)整成堆將堆頂與序列中未排序的最后一個(gè)元素互換493827134976976549273813497697654913382749769765建大頂堆，排序結(jié)果為從小到大將堆頂與序列中未排序的最后一個(gè)元素互換無調(diào)整，第6趟堆排序完成無調(diào)整，第7趟堆排序完成/*已知H.r[s..m]中記錄的關(guān)鍵字除H.r[s].key之外均滿足堆的定義，本函數(shù)調(diào)整H.r[s]的關(guān)鍵字，使H.r[s..m]成為一個(gè)大頂堆(對(duì)其中記錄的關(guān)鍵字而言)*/typedefSqListHeapType;voidHeapAdjust(HeapType&H,ints,intm){rc=H.r[s];

for(j=2*s;j<=m;j*=2){//沿key較大的孩子結(jié)點(diǎn)向下篩選//j為key較大的記錄的下標(biāo)if(j<m&<(H.r[j].key,H.r[j+1].key))++j;if(!LT(rc.key,H.r[j].key))break;//rc應(yīng)插入在位置s上H.r[s]=H.r[j];s=j;}H.r[s]=rc;//插入}//HeapAdjust從下標(biāo)s處開始調(diào)整左側(cè)“底座”j記住的是兩個(gè)“底座”中值較大的那一個(gè)的下標(biāo)如果rc大于H.r[j].key，那么無需調(diào)整（大頂堆），直接退出循環(huán)把H.r[j]放到H.r[s]中；s下移到j(luò)處，準(zhǔn)備下一次可能的調(diào)整最終rc所放的位置/*對(duì)順序表H進(jìn)行堆排序*/voidHeapSort(HeapType&H){

for(i=H.length/2;i>0;--i)

//把H.r[1..H.length]建成大頂堆

HeapAdjust(H,i,H.length);

//將堆頂記錄和當(dāng)前未經(jīng)排序子序列Hr[1..i]中最后一個(gè)記錄相互交換for(i=H.length;i>1;--i)

{

H.r[1]←→H.r[i];

HeapAdjust(H,1,i-1);//將H.r[1..i-1]重新調(diào)整為大頂堆}}//HeapSort時(shí)間復(fù)雜度O(nlog2n)概述插入排序快速排序選擇排序歸并排序基數(shù)排序各種內(nèi)部排序方法的比較討論本講主要內(nèi)容10.5歸并排序（MergingSort）將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表2路歸并：把初始含有n個(gè)記錄的序列看成n個(gè)長(zhǎng)度為1的有序子序列,采用兩兩合并的方法最終合并成一個(gè)序列21252593627208371654492521254962930872163754082125

254962729316375408162125

253749546272932125

254908627293163754//算法10.12將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]voidMerge(RcdTypeSR[],RcdType&TR[],inti,intm,intn){//將SR中記錄由小到大地并入TRfor(j=m+1,k=i;i<=m&&j<=n;++k){if(LQ(SR[i].key,SR[j].key))TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i<=m)TR[k..n]=SR[i..m];//將剩余的SR[i..m]復(fù)制到TRif(j<=n)TR[k..n]=SR[j..n];//將剩余的SR[j..n]復(fù)制到TR}//Merge時(shí)間復(fù)雜度：O(nlog2n)//遞歸算法：將SR[s..t]歸并排序?yàn)門R1[s..t]voidMSort(RcdTypeSR[],RcdType&TR1[],ints,intt){

if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;//將SR[s..t]平分為SR[s..m]和SR[m+1,t]

MSort(SR,TR2,s,m);//遞歸地將SR[s..m]歸并為有序的TR2[s..m]

MSort(SR,TR2,m+1,t);//遞歸地將SR[m+1..t]歸并為有序的TR2[m+1..t]

Merge(TR2,TR1,s,m,t);//將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t]}}//MSort//對(duì)順序表L作歸并排序voidMergeSort(SqList&L){

MSort(L.r,L.r,1,L.length);}//MergeSort概述插入排序快速排序選擇排序歸并排序基數(shù)排序各種內(nèi)部排序方法的比較討論本講主要內(nèi)容與前述方法完全不同的一種排序方法！前面的排序方法主要通過關(guān)鍵字間的比較和移動(dòng)記錄來實(shí)現(xiàn)的！基數(shù)排序不需要進(jìn)行關(guān)鍵字間的比較，它是一種借助多關(guān)鍵字的排序思想對(duì)單邏輯關(guān)鍵字進(jìn)行排序的方法10.6基數(shù)排序（RadixSorting）最高位優(yōu)先法MSD：先按關(guān)鍵字K0排序，將序列分成若干個(gè)子序列每個(gè)子序列記錄的K0均相等然后在每個(gè)子序列中按K1排序按K1值把子序列分成更小的子序列

……………

直到最后按Kd-1排序后，整個(gè)序列有序一、多關(guān)鍵字排序(1,1),(2,4),(1,3),(3,2),(4,4),(2,3),(4,3),(3,4)(1,1),(1,3),(2,4),(2,3),(3,2),(3,4),(4,4),(4,3)(1,1),(3,2),(1,3),(2,3),(4,3),(2,4),(3,4),(4,4)最低位優(yōu)先法LSD：根據(jù)最次關(guān)鍵字Kd-1起對(duì)記錄排序再根據(jù)Kd-2對(duì)記錄排序。。。。。。根據(jù)K0對(duì)記錄排序后，

整個(gè)序列有序(1,1),(2,4),(1,3),(3,2),(4,4),(2,3),(4,3),(3,4)(1,1),(3,2),(1,3),(2,3),(4,3),(2,4),(4,4),(3,4)(1,1),(1,3),(2,3),(2,4),(3,2),(3,4),(4,3),(4,4)二、鏈?zhǔn)交鶖?shù)排序用分配和收集兩種操作對(duì)單關(guān)鍵字進(jìn)行排序某些單關(guān)鍵字可以看成是若干個(gè)關(guān)鍵字復(fù)合而成,如多位數(shù)可以看成是由多個(gè)數(shù)字復(fù)合而成的?！胺峙洹保?/p>

按關(guān)鍵字把不同的記錄送到不同的隊(duì)列中“收集”：

按某種順序把不同隊(duì)列中的記錄集中起來614921485637738101