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

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

假設(shè)含n個記錄的序列為{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}成為一個按關(guān)鍵字有序的序列{Rp1,Rp2,…,Rpn}這樣一種操作稱為排序

關(guān)鍵字Ki可以是記錄Ri的主關(guān)鍵字【排序結(jié)果唯一】、次關(guān)鍵字或若干數(shù)據(jù)項的組合【排序結(jié)果不唯一】假設(shè)：(1)在待排序序列中存在兩個(以上)關(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)定的

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

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

KeyType

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

RedType

r[MAXSIZE+1];//r[0]閑置或用作哨兵單元intlength;//順序表長度}SqList;//順序表類型概述插入排序快速排序選擇排序歸并排序基數(shù)排序各種內(nèi)部排序方法的比較討論本講主要內(nèi)容一、直接插入排序方法：將一個記錄插入到已排好序的有序表中，得到一個新的、記錄數(shù)增1的有序表：（1）把序列(R(K1))看成是一個有序的子序列把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//對順序表L作直接插入排序的算法voidInsertSort(SqList&L){//算法10.1for(i=2;i<=L.length;++i)

//"<"時，需將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直接插入排序的時間復(fù)雜度：O(n2)二、其它插入排序直接插入排序適合待排序數(shù)量n很小的情況，若n很大，則不宜采用為此，從減少“比較”和“移動”這兩種操作的次數(shù)考慮，可有以下幾種排序的方法：(1)折半插入排序(2)2-路插入排序(3)表插入排序(4)希爾排序(1)折半插入排序做法：用折半查找的方法找到插入位置

例：在序列{13，27，35，48，65，72}中插入20或603565132748722060//對順序表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;//插入點在低半?yún)^(qū)

elselow=m+1;

//插入點在高半?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折半插入排序的時間復(fù)雜度：O(n2)low(2)希爾排序又稱“縮小增量排序”(DiminishingIncrementSort)希爾排序的基本思想：(1)先將整個待排記錄序列分割成若干子序列(2)分別對這些子序列進行直接插入排序(3)待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序增量序列為：5，3，149

38

65

977613

27

4913

27

49

977649

386513

27

49

97

76

49

386513

27

49

38

65

49

97761327384949657697/*對順序表L作一趟希爾插入排序。本算法對算法10.1作了以下修改：1.前后記錄位置的增量是dk，而不是1；2.r[0]只是暫存單元，不是哨兵。當(dāng)j<=0時，插入位置已找到*/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]對順序表L作希爾排序*/voidShellSort(SqList&L,intdlta[],intt){//算法10.5

for(k=0;k<t;++k)ShellInsert(L,dlta[k]);//一趟增量為dlta[k]的插入排序}//ShellSort希爾排序的時間是所取“增量”序列的函數(shù)，涉及一些數(shù)學(xué)上的尚未解決的難題概述插入排序快速排序選擇排序歸并排序基數(shù)排序各種內(nèi)部排序方法的比較討論本講主要內(nèi)容快速排序是一種借助“交換”進行排序的方法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;}}共進行n-1趟排序，共進行n(n-1)/2次比較T(n)=O(n2)快速排序是對起泡排序的一種改進基本思想：通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠忠徊糠钟涗浀年P(guān)鍵字均比另一部分記錄的關(guān)鍵字小則再分別對這兩部分的記錄繼續(xù)進行排序最后達(dá)到整個序列有序二、快速排序（QuickSort)假設(shè)待排序序列為{L.r[s]，L.r[s+1]，…，L.r[t]}首先任意選取一個記錄(一般為第一個記錄L.r[s])作為樞軸(或支點)(pivot)然后按下述原則重新排列其余記錄：將所有關(guān)鍵字比它小的記錄都安置在樞軸之前將所有關(guān)鍵字比它大的記錄都安置在樞軸之后由此，以該“樞軸”記錄最后所落的位置i作分界線，將序列{L.r[s]，L.r[s+1]，…，L.r[t]}分割成兩個子序列：{L.r[s]，L.r[s+1]，…，L.r[i-1]}和{L.r[i+1]，L.r[i+2]，…，L.r[t]}這個過程稱作一趟快速排序(或一次劃分)4938659776132749i27386597761349

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

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

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

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

27

384965

76

97/*算法10.6(a)交換順序表L中子表L.r[low..high]的記錄，使樞軸記錄到位，并返回其所在位置，此時在它之前(后)的記錄均不大(小)于它*/每交換一對記錄需進行3次記錄移動(賦值)操作！但對樞軸記錄的賦值是多余的！只有在一趟排序結(jié)束low=high的位置才是樞軸的最后位置，改寫該算法！intPartition(SqList&L,intlow,inthigh){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[low]←→L.r[high];//將比樞軸記錄大的記錄交換到高端}returnlow;//返回樞軸位置}//Partition//改進后的算法10.6(b)intPartition(SqList&L,intlow,inthigh){L.r[0]=L.r[low];//用子表的第一個記錄作樞軸記錄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//對順序表L作快速排序//遞歸形式的快速排序算法//對順序表L的子序列L.r[low..high]作快速排序voidQSort(SqList&L,intlow,inthigh){if(low<high){

//長度大于1

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

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

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

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

}}//QSortvoidQuickSort(SqList&L){

QSort(L,1,L.length);}//QuickSortT(n)=O(nlog2n)快速排序的平均時間為Tavg=knlnn其中：n為待排序序列中記錄的個數(shù)，k為某個常數(shù)就平均時間而言，快速排序是目前被認(rèn)為是最好的一種內(nèi)部排序方法但是：若初始記錄序列按關(guān)鍵字有序或基本有序時，快速排序蛻化為起泡排序，其時間復(fù)雜度為O(n2)從空間上看：之前討論的各種方法，除2-路插入排序外，都只需要一個記錄的附加空間，但快速排序需要一個?？臻g來實現(xiàn)遞歸。概述插入排序快速排序選擇排序歸并排序基數(shù)排序各種內(nèi)部排序方法的比較討論本講主要內(nèi)容10.4選擇排序251608254921490816252521212525160849162108一、簡單選擇排序（SelectSort)2516082549214925012345081625212549252116082525//對順序表L作簡單選擇排序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個記錄交換}}//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;}共進行n-1趟排序，n(n-1)/2次比較時間復(fù)雜度O(n2)TreeSelectionSort，又稱錦標(biāo)賽排序(TournamentSort)該過程可用一棵有n個葉子結(jié)點的完全二叉樹表示

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

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

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

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

for(j=2*s;j<=m;j*=2){//沿key較大的孩子結(jié)點向下篩選//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記住的是兩個“底座”中值較大的那一個的下標(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所放的位置/*對順序表H進行堆排序*/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]中最后一個記錄相互交換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時間復(fù)雜度O(nlog2n)概述插入排序快速排序選擇排序歸并排序基數(shù)排序各種內(nèi)部排序方法的比較討論本講主要內(nèi)容10.5歸并排序（MergingSort）將兩個或兩個以上的有序表組合成一個新的有序表2路歸并：把初始含有n個記錄的序列看成n個長度為1的有序子序列,采用兩兩合并的方法最終合并成一個序列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時間復(fù)雜度：O(nlog2n)//遞歸算法：將SR[s..t]歸并排序為TR1[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//對順序表L作歸并排序voidMergeSort(SqList&L){

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

……………

直到最后按Kd-1排序后，整個序列有序一、多關(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起對記錄排序再根據(jù)Kd-2對記錄排序。。。。。。根據(jù)K0對記錄排序后，

整個序列有序(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ù)排序用分配和收集兩種操作對單關(guān)鍵字進行排序某些單關(guān)鍵字可以看成是若干個關(guān)鍵字復(fù)合而成,如多位數(shù)可以看成是由多個數(shù)字復(fù)合而成的。“分配”：

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

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