數(shù)據(jù)結(jié)構(gòu)(C語言版)：第3章 排序基礎(chǔ)

第3章排序基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)3.1排序的概念與分類

3.1.1排序的概念

3.1.2排序的分類

3.2直接插入排序 3.3希爾排序 3.4基數(shù)排序

3.4.1多關(guān)鍵字排序

3.4.2基數(shù)排序第3章排序基礎(chǔ)3.1排序的概念與分類含有多個數(shù)據(jù)項的數(shù)據(jù)元素稱為記錄。用作記錄唯一標識的數(shù)據(jù)項稱為關(guān)鍵字域，其值稱為關(guān)鍵字。若關(guān)鍵字唯一標識一個記錄，則稱為主關(guān)鍵字，否則為次關(guān)鍵字。為了與元素類型ElemType區(qū)別，記錄類型定義為RecordType。typedefintKeyType;//關(guān)鍵字類型為整數(shù)類型typedef

struct

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

…… //其它數(shù)據(jù)項}RecordType,RcdType;//記錄類型3.1.1排序的概念排序是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列的一種操作。例如，將下列關(guān)鍵字序列：（175,85,260,63,412,504,840,518,630,950）調(diào)整為有序序列：（63,85,175,260,412,504,518,630,840,950）什么是排序假設含n個記錄的序列為（r1,r2,…,rn） 其相應的關(guān)鍵字序列為

（k1,k2,…,kn）這些關(guān)鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關(guān)系

kp1≤kp2≤…≤kpn按此固有關(guān)系將上式記錄序列重新排列為

（rp1,rp2,…，rpn

） 的操作稱作排序。記錄順序表的類型定義typedef

struct

{RcdType*rcd;//存儲空間基址

intlength;//當前長度

intsize;//存儲容量

}RcdSqList;//記錄的順序表注意：順序表的0號單元閑置或用作哨兵。在后面的討論中，前后文意思清楚的情況下，約定：把“記錄的關(guān)鍵字的大小”和“記錄的關(guān)鍵字的比較”簡稱為“記錄的大小”和“記錄的比較”。將“元素的關(guān)鍵字的大小”和“結(jié)點的關(guān)鍵字大小”簡稱為“元素的大小”和“結(jié)點的大小”。3.1.2排序的分類根據(jù)在排序過程中涉及的存儲器不同，可將排序方法分為兩大類：內(nèi)部排序和外部排序。內(nèi)部排序是指待排序列完全存放在內(nèi)存中所進行的排序過程。外部排序是對大文件的排序，待排序的文件無法一次裝入內(nèi)存，在排序過程中需要在內(nèi)存和外部存儲器之間進行多次數(shù)據(jù)交換

。內(nèi)部排序的分類內(nèi)部排序方法分為五類：交換排序、選擇排序、插入排序、歸并排序和基數(shù)排序。其中交換排序、選擇排序和插入排序是一個逐步擴大記錄的有序序列長度的過程。有序序列區(qū)無序序列區(qū)有序序列區(qū)無序序列區(qū)排序的介紹交換排序是對無序區(qū)中記錄的關(guān)鍵字兩兩進行比較，若逆序則交換，直到關(guān)鍵字之間不存在逆序為止。冒泡排序和快速排序是交換排序中最典型的兩個方法。選擇排序是在無序區(qū)中選出關(guān)鍵字最小的記錄，置于有序區(qū)的最后，直到全部記錄有序。簡單選擇排序和堆排序是選擇排序中最典型的兩個方法。2134521345排序的介紹插入排序是將無序區(qū)中的一個記錄插入至有序區(qū)，使得有序區(qū)的長度加1，直到全部記錄有序。直接插入排序和希爾排序是插入排序中最具代表性的兩個方法。歸并排序是不斷將兩個或兩個以上有序區(qū)合并成一個有序區(qū)，直到全部記錄有序?；鶖?shù)排序是和前面所述各類排序方法完全不同的一種排序方法，不需要進行記錄關(guān)鍵字的比較。21345排序算法的時間復雜度分類內(nèi)部排序方法按時間復雜度分為三類：簡單的排序方法，時間復雜度為O(n2)；先進的排序方法，時間復雜度為O(nlogn)；基數(shù)排序，時間復雜度為O(n)。希爾排序的算法時間復雜度與增量序列有關(guān)，還涉及到一些數(shù)學上尚未解決的難題，其算法時間復雜度不屬于以上類別。每一種排序方法都有各自的優(yōu)缺點，適合于不同的應用場合。為方便起見，若非特意強調(diào)，排序的實施均為非遞減有序（升序）排序。直接插入排序假如8個記錄的關(guān)鍵字序列為（56,68,25,45,90,38,10,72）,每一趟的排序過程可參看下圖：第i趟插入排序?qū)⒂涗汱.rcd[i+1]插入到有序區(qū)L.rcd[1..i]中，插入前需要找到插入位置，移動記錄空出插入位置。45[]45689013直接插入排序

利用“順序查找”實現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”算法的實現(xiàn)要點：14從R[i-1]起向前進行順序查找，監(jiān)視哨設置在R[0]；R[0]=R[i];//設置“哨兵”循環(huán)結(jié)束表明R[i]的插入位置為j+1R[0]jR[i]for(j=i-1;R[0].key<R[j].key;--j);//從后往前找j=i-1插入位置15

對于在查找過程中找到的那些關(guān)鍵字不小于R[i].key的記錄，并在查找的同時實現(xiàn)記錄向后移動；for(j=i-1;R[0].key<R[j].key;--j);

R[j+1]=R[j]R[0]jR[i]j=i-1上述循環(huán)結(jié)束后可以直接進行“插入”插入位置16令i=2，3，…,n,實現(xiàn)整個序列的排序。for(i=2;i<=n;++i)

if(R[i].key<R[i-1].key){在

R[1..i-1]中查找R[i]的插入位置;

插入R[i];

}17voidInsertionSort(RcdSqList&L){//對順序表L作直接插入排序。

for(i=2;i<=L.length;++i)if(L.rcd[i].key<L.rcd[i-1].key){

}}//InsertSortL.rcd[0]=L.rcd[i];//復制為監(jiān)視哨for(j=i-1;L.rcd[0].key<L.rcd[j].key;--j)L.rcd[j+1]=L.rcd[j];//記錄后移L.rcd[j+1]=L.rcd[0];//插入到正確位置算法實現(xiàn)分析(書本上的實現(xiàn))查找插入位置 從有序區(qū)的位置1到i，判斷是否為記錄L.rcd[i+1]的插入位置j，代碼為： j=0;do{j++;}while(L.rcd[j].key<L.rcd[i+1].key);//從前到后查找插入位置移動記錄空出插入位置 將有序區(qū)中從位置i到j的記錄向后移動，空出插入位置j，代碼為： L.rcd[0]=L.rcd[i+1];//先將記錄L.rcd[i+1]保存在空閑的0號單元 k=i+1;do

{k--;L.rcd[k+1]=L.rcd[k];}

while(k>j);//從后到前移動記錄若將判斷插入位置的次序改為從i到1，則可將上述兩步的代碼合并為： L.rcd[0]=L.rcd[i+1]; j=i+1;do{j--;L.rcd[j+1]=L.rcd[j];}while(j>1&&L.rcd[0].key<L.rcd[j-1].key);

//從后到前查找并移動記錄0號單元存放了記錄L.rcd[i+1]，判斷j是否越界的操作“j>1”可以略去。L.rcd[0]起到了邊界監(jiān)視哨的作用，稱為哨兵。直接插入排序voidInsertSort

(RcdSqList&L

)設置哨兵查找插入位置，移動記錄空出插入位置插入記錄voidInsertSort(RcdSqList&L){

//對順序表L作直接插入排序。inti,j;for(i=1;i<L.length;++i)

if(L.rcd[i+1].key<L.rcd[i].key){

//需將L.rcd[i+1]插入有序序列L.rcd[0]=L.rcd[i+1];

//先將記錄L.rcd[i+1]保存在空閑的0號單元j=i+1;do

{

j--;

L.rcd[j+1]=L.rcd[j];

//記錄后移}

while(L.rcd[0].key<L.rcd[j-1].key);

//判斷是否需要繼續(xù)移動

L.rcd[j]=L.rcd[0];

//插入

}}0381jii+1254556689010723838直接插入排序算法性能分析排序算法的時間耗費主要與關(guān)鍵字比較和記錄移動的次數(shù)相關(guān)。最好的情況（關(guān)鍵字在記錄序列中順序有序）“比較”的次數(shù)：“比較”的次數(shù)：0“移動”的次數(shù)：“移動”的次數(shù)：直接插入排序的最好情況下時間復雜度為O(n)，最壞情況下時間復雜度為O(n2)。最壞的情況（關(guān)鍵字在記錄序列中逆序有序）直接插入排序只需要一個記錄的輔助空間，其空間復雜度為O(1)。希爾排序希爾排序是將整個待排記錄序列（R1,R2,R3,…,Rn）按增量d劃分成d個子序列，其中第i（1≤i≤d）個子序列為（Ri,Ri+d,Ri+2d,…,Ri+kd）13553876270465494997123456789103.3希爾排序分別對各子序列進行直接插入排序；不斷減小增量d，重復這一過程；直到d減少到1，對整個序列進行一次直接插入排序。增量d的取值序列稱為增量序列?；谠隽啃蛄械慕敌蛱攸c，希爾排序也被稱為“縮小增量排序”。希爾排序?qū)嵗判蛄校?9,38,65,97,76,13,27,49,55,04）第一趟排序的增量d1為5

結(jié)果為（13,27,49,55,04,49,38,65,97,76）

1349273865499755760412345678910希爾排序?qū)嵗诙讼柵判虻脑隽縟2為3結(jié)果為（13,04,49,38,27,49,55,65,97,76）第三趟的增量d3為1，最后結(jié)果為（04,13,27,38,49,49,55,65,76,97）1355387627046549499712345678910希爾排序與直接插入排序直接插入排序每次對相鄰記錄進行比較，記錄最多只移動了一個位置，希爾排序每次對相隔較遠距離（即增量）的記錄進行比較，使得記錄移動時能跨過多個記錄，實現(xiàn)宏觀上的調(diào)整。希爾排序的最后一趟排序（增量為1），序列已基本有序，接近最好情況（微觀調(diào)整）的直接插入排序。可將前面各趟的“宏觀”調(diào)整看成是最后一趟的預處理，實現(xiàn)比只做一次直接插入排序效率更高。

voidShellInsert(RcdSqList&L,intdk){//對順序表L作一趟希爾排序，增量為dk

inti,j;

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

//需將L.rcd[i+dk]插入有序序列L.rcd[0]=L.rcd[i+dk];//暫存在L.rcd[0]j=i+dk;

do{j-=dk;L.rcd[j+dk]=L.rcd[j];//記錄后移

}while(j-dk>0&&L.rcd[0].key<L.rcd[j-dk].key);//判斷是否需要繼續(xù)移動L.rcd[j]=L.rcd[0];//插入

}}一趟希爾排序voidShellInsert(RcdSqList&L,intdk)暫存待插入記錄按增量dk查找插入位置,移動記錄空出插入位置插入記錄049i-3jii+3130449552765389776383827voidShellInsert(RcdSqList&L,intdk){for(i=dk+1;i<=n;++i)

if(L.rcd[i].key<L.rcd[i-dk].key){L.rcd[0]=L.rcd[i];//暫存在R[0]for(j=i-dk;j>0&&L.rcd[0].key<L.rcd[j].key;

j-=dk)L.rcd[j+dk]=L.rcd[j];//記錄后移,查找插入位置

L.rcd[j+dk]=L.rcd[0];//插入

}//if}//ShellInsert希爾排序voidShellSort(RcdSqList&L,intd[],intt){

//按增量序列d[0..t-1]對順序表L作希爾排序

intk;for(k=0;k<t;++k)

ShellInsert(L,d[k]);//一趟增量為d[k]的插入排序

}

希爾排序的時間復雜度分析希爾排序的時間復雜度分析是一個復雜的問題，因為它的時間復雜度是所取增量序列的函數(shù)，這涉及到一些數(shù)學上尚未解決的難題。有研究指出，當增量序列為d[k]=2t-k+1-1時，希爾排序的時間復雜度為O(n1.5)，其中t為排序趟數(shù)，1≤k≤t≤?log2(n+1)?。排序的穩(wěn)定性假設ki=kj(1≤i≤n,1≤j≤n,i≠j)，且在排序前的序列中ki領(lǐng)先于kj(即i<j)。若在排序后的序列中ki仍領(lǐng)先于kj，則稱所用的排序方法是穩(wěn)定的；否則，排序方法是不穩(wěn)定的。從希爾排序的例子可見，序列有兩個49，后一個49在排序后排到了49前面，因此希爾排序是不穩(wěn)定的排序算法。3.4基數(shù)排序前面介紹的排序方法都基于關(guān)鍵字比較，而基數(shù)排序不需要比較關(guān)鍵字?；鶖?shù)排序借鑒多關(guān)鍵字排序的思想，把關(guān)鍵字看成由多個關(guān)鍵字復合而成。3.4.1多關(guān)鍵字排序一般情況下，多關(guān)鍵字排序的定義為：假設含有n個記錄的序列為（r1,r2,…,rn）每個記錄ri含有m個關(guān)鍵字（ki0，ki1，…，kim-1），如果對于序列中任意兩個記錄ri

和rj（1≤i<j≤n）都滿足下列有序關(guān)系： （ki0，ki1，…，kim-1）<（kj0，kj1，…，kjm-1）則稱記錄序列對這m個關(guān)鍵字有序。其中k0被稱作最主位關(guān)鍵字，km-1被稱作最次位關(guān)鍵字；(a0,a1,…,am-1)<(b0,b1,…,bm-1)是指必定存在l，使得：當s=0,…,l-1時，as=bs，

而al<bl。實現(xiàn)多關(guān)鍵字排序策略高位優(yōu)先排序先按最主位關(guān)鍵字k0進行排序，得到若干子序列，其中每個子序列中的記錄都含相同的k0值；接著分別就每個子序列按關(guān)鍵字k1進行排序，致使k1值相同的記錄構(gòu)成長度更短的子序列；依次重復，直至就當前得到的各個子序列按km-1

進行從小到大進行排序；最后由這些子序列依次相連所得序列便是排序的最后結(jié)果。低位優(yōu)先排序先按最低位關(guān)鍵字進行排序；接著按次低位關(guān)鍵字實施排序；最后按最主位關(guān)鍵字進行排序。與高位優(yōu)先排序不同，其排序過程中不產(chǎn)生子序列，每趟都是對整個序列進行排序。實例現(xiàn)需要學生實施多關(guān)鍵字的排序，其中年級、班別和學號為關(guān)鍵字序列，且年級為最主位關(guān)鍵字。若采用低位優(yōu)先排序法，先按學號進行排序接著按班別進行排序最后按年級進行排序低位優(yōu)先排序必須使用穩(wěn)定的排序算法黃紅張晗4444黃紅張晗基數(shù)排序?qū)⒂涗浀年P(guān)鍵字看成由m個關(guān)鍵字復合而成，每個關(guān)鍵字可能取r個值，則只要從最低位關(guān)鍵字起，先按關(guān)鍵字的不同值將記錄“分配”到r個子序列，再按從小到大將各子序列依次首尾相接“收集”在一起，如此重復m趟，最終完成整個記錄序列的排序。按這種方法實現(xiàn)的排序稱為基數(shù)排序。(其中基數(shù)r指的是“關(guān)鍵字”的取值范圍)假設關(guān)鍵字k是十進制數(shù)，即r=10，且其值都在0到999的范圍內(nèi)，則可把k中的每一位數(shù)字看成一個關(guān)鍵字，即認為k由三個關(guān)鍵字（k0,k1,k2）組成，其中k0是個位數(shù)，k1是十位數(shù)，k2是百位數(shù)。若關(guān)鍵字k是字符串，則可把字符串中的每一個字母看成一個關(guān)鍵字，即r=26?；鶖?shù)排序的實現(xiàn)方法鏈式基數(shù)排序在鏈式存儲結(jié)構(gòu)中實現(xiàn)。在每一趟排序中，分配是按相應關(guān)鍵字的取值將記錄加入到r個不同的隊列；收集是從小到大依次將r個隊列首尾相接成一個鏈表。計數(shù)基數(shù)排序在順序存儲結(jié)構(gòu)中實現(xiàn)。在每一趟排序中，分配是對相應關(guān)鍵字的每種取值計數(shù)（即統(tǒng)計r個子序列的長度），確定每個子序列的起始位置；收集是根據(jù)各子序列的起始位置將記錄復制到合適位置。計數(shù)基數(shù)排序數(shù)據(jù)類型定義typedefstruct{

KeysType*keys;//關(guān)鍵字

……//其它數(shù)據(jù)項}KeysRcdType;//基數(shù)排序中的記錄類型typedefstruct{KeysRcdType*rcd;//0號位置做哨兵intlength;

//順序表長度intsize;//順序表容量intdigitNum;

//關(guān)鍵字位數(shù)intradix;//關(guān)鍵字基數(shù)}KeysSqList;

//順序表類型計數(shù)基數(shù)排序的實現(xiàn)引入三個數(shù)組數(shù)組count用于統(tǒng)計關(guān)鍵字的r種取值的個數(shù)。count[i]是對值i的計數(shù)；數(shù)組pos用于確定各子序列的起始位置。pos[i]是值為i的子序列的起始位置。數(shù)組rcd1與rcd類型相同。在各趟收集中，第一趟從數(shù)組rcd收集到rcd1，第二趟從rcd1收集到rcd，如此交替進行，若總趟數(shù)為奇數(shù)，最后還需將排序結(jié)果從數(shù)組rcd1復制回rcd。舉例對關(guān)鍵字為（337,332,132,267,262,164,260,167）的8個記錄序列需進行三趟“分配”和“收集”完成低位優(yōu)先的計數(shù)基數(shù)排序。第一趟對個位數(shù)排序，首先用數(shù)組count對個位數(shù)的每種取值計數(shù)，共有1個0、3個2、1個4和3個7，其余均為0個。利用count數(shù)組統(tǒng)計第i個關(guān)鍵字各種取值的個數(shù)：

for(j=0;j<L.radix;++j)count[j]=0;//初始化

for(k=1;k<=n;k++)count[rcd[k].keys[i]]++;//對各種取值計數(shù)70000121227234101732舉例利用count數(shù)組的結(jié)果，依次計算個位數(shù)從0到9的關(guān)鍵字存儲的起始位置，存入數(shù)組pos。pos[0]=1;

for(j=1;j<L.radix;++j)pos[j]=pos[j-1]+count[j-1];1225566699count[0]count[1]count[2]count[9]……pos[0]=1pos[2]=pos[1]+count[1]pos[9]=pos[8]+count[8]=pos[0]+count[0]pos[1]舉例第一趟收集由337的個位數(shù)7取得其起始位置pos[7]的值6，將337放入rcd1[6]中，并將pos[7]加1，令pos[7]指向下一個個位數(shù)為7的記錄應放入的位置。由332的個位數(shù)2取得其起始位置pos[2]的值2，將332放入rcd1[2]中，并將pos[2]加1。收集的代碼for(k=1;k<=n;++k){

//收集j=rcd[k].keys[i];rcd1[pos[j]++]=rcd[k];

//復制記錄,對應的起始位置加1

}256789345612256699337332167260164262267132rcdposrcd1337332132267262164260167第二趟分配與收集第二趟對數(shù)組rcd1進行分配第二趟收集，將記錄從數(shù)組rcd1收集到rcd41666663330035rcd12

6

01

3

22583

3

22

6

21

6

463

3

73472

6

791

6

711144999countposrcd第三趟分配與收集第三趟對數(shù)組rcd進行分配第三趟收集，將記錄從數(shù)組rcd收集到rcd1由于趟數(shù)為奇數(shù)，需將數(shù)組rcd1復制回rcd。90011132223332011479999993

3

21

6

78rcd1

3

223

3

742

6

052

6

261

6

432

6

77countposrcd1一趟計數(shù)基數(shù)排序voidRadixPass(KeysRcdTypercd[],KeysRcdTypercd1[],intn,inti,

intcount[],intpos[],intradix){

intk,j;for(k=1;k<=n;k++)count[rcd[k].keys[i]]++;//對各種取值計數(shù)

pos[0]=1;for(j=1;j<radix;++j)pos[j]=count[j-1]+pos[j-1];//求起始位置

for(k=1;k<=n;++k){

//收集

j=rcd[k].keys[i];

rcd1[pos[j]++]=rcd[k];//復制記錄