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

基本概念插入排序交換排序選擇排序歸并排序基數(shù)排序外部排序10-1排序的基本概念是記錄中的一個(或多個)字段，如果是

關(guān)鍵碼，則按關(guān)鍵碼排序；排序碼也

可以不是關(guān)鍵碼，則可能有多個記錄具

有相同的排序碼，排序的結(jié)果不惟一。將一個數(shù)據(jù)元素集合或序列重新

排列成一個按數(shù)據(jù)元素某個數(shù)據(jù)

項(xiàng)值有序的序列。排序排序碼穩(wěn)定排序不穩(wěn)定排序內(nèi)排序外排序假設(shè){R0,R1,…,Rn-1}是由n個記錄組成

的文件，{K0,K1,…,Kn-1}是排序碼集合，

假設(shè)Ki=Kj(0<=i,j<=n-1,i≠j)，且在排序

前的序列中Ri領(lǐng)先于Rj(即i<j)，若在排

序后的序列中Ri仍領(lǐng)先于Rj，則稱所用

的排序方法是穩(wěn)定的，否則是不穩(wěn)定的。待排序的記錄在排序過程中全部存放在內(nèi)存

的稱為內(nèi)排序，如果排序過程中需要使用

外存的稱為外排序。排序方法可以分為五種：插入排序、選擇排序、

交換排序、基數(shù)排序和歸并排序。排序中的基本操作：比較關(guān)鍵碼大小和移動記錄。評價(jià)排序算法好壞的標(biāo)準(zhǔn)主要有兩條∶①執(zhí)行算法所需的時(shí)間；②執(zhí)行算法所需要的附加空間。排序的時(shí)間開銷可以用算法執(zhí)行中的比較和移動次數(shù)來表示。10-2插入排序插入排序的基本思想：每步將一個待排序的記錄按其

關(guān)鍵字大小插入到前面已排序表中的適當(dāng)位置，直到

全部插入完為止。直接插入排序假設(shè)待排序的n個記錄{R0,R1,…,Rn-1}存放在數(shù)組中，

直接插入法是在插入記錄Ri(i=1,2…n-1)時(shí)，記錄集合

被劃分為兩個區(qū)間[R0，Ri-1]和[Ri，Rn-1]，其中，

前一個子區(qū)間已經(jīng)排好序，后一個子區(qū)間是當(dāng)前未

排序的部分，將排序碼Ki與Ki-1，Ki-2,…,K0依次比

較，找出應(yīng)該插入的位置，將記錄Ri插入，原位置

的記錄向后順移。例：設(shè)待排序記錄的排序碼為：49，38，65，97，76，13，27，49，請用直接插入排法排序。i=2:[49]38659776132749i=3:[3849]659776132749i=4:[384965]9776132749i=5:[38496597]76132749i=6:[3849657697]132749i=7:[133849657697]27

49i=8:[13273849657697]49i=9:[1327384949657697]typedefstruct{KeyTypekey；

…；}DataType;voidInsertSort(DataTypeR[],intn){intI;for(i=2;i<=n;i++)

if(R[i].key<R[i-1].key){R[0]=R[i];for(j=i-1;R[0].dey<R[j].key;j--)R[j+1]=R[j];R[j+1]=R[0];}}算法分析如下:空間效率：只需要一個記錄的輔助空間。時(shí)間效率：最小比較記錄的次數(shù)為n-1=O(n)；最大比較記錄的次數(shù)為(n+2)(n-1)/2=O(n2)；最小移動記錄的次數(shù)為0次；最大移動記錄的次數(shù)為(n+4)(n-1)/2=O(n2)。

平均情況下，插入記錄大約同前面i/2個記錄進(jìn)行關(guān)鍵碼比較和移動，因此插入排序的時(shí)間復(fù)雜度為O(n2)直接插入排序是穩(wěn)定的排序算法二分法插入排序由于插入排序的基本操作是在有序表中進(jìn)行查找,而

查找的過程是可以用折半查找來實(shí)現(xiàn)的。由此實(shí)現(xiàn)

的排序稱為二分法插入排序。二分法插入排序必須采用順序存儲方式。voidB_InsertSort(DataTypeR[],intn){intI;intcow,high,mid;for(i=2;i<=n;i++){R[0]=R[i];low=1;high=i-1;while(low<=high){mid=(low+high)/2;if(R[0].key>R[mid].key)low=mid+1;elsehigh=mid-1;}for(j=i-1;j>=high+1;j--)R[j+1]=R[j];R[high+1]=R[0];}}i=2:[49]38659776132749i=3:[3849]659776132749i=4:[384965]9776132749i=5:[38496597]76132749i=6:[3849657697]132749i=7:[133849657697]2749i=8:[13273849657697]49i=9:[1327384949657697]low=1,high=1low=1,high=2low=1,high=3low=1,high=4low=1,high=5算法分析如下:定位一個關(guān)鍵碼的位置需比較次數(shù)至多為,比較次數(shù)時(shí)間復(fù)雜度為而移動記錄的次數(shù)和直接插入排序相同，

因此時(shí)間復(fù)雜度仍為O(n2)二分插入排序是一個穩(wěn)定的排序方法。表插入排序基本思想：在直接插入的基礎(chǔ)上減少移動次數(shù)，主要

是在記錄中設(shè)置一個指針字段，記錄鏈接成鏈表，初

始時(shí)，鏈表為空，頭結(jié)點(diǎn)指針域置為0，并在頭結(jié)點(diǎn)數(shù)

據(jù)域放比所有記錄關(guān)鍵碼都大的整數(shù)，然后，向鏈表

中插入結(jié)點(diǎn)typedefstruct{DataTypedata;intnext;}NodeType;NodeTypeR[n+1];MAX49386597761327490--------0112030445262738這個有序的鏈表，查找則只能順序查找，而不能隨機(jī)查找若需要，要發(fā)對記錄進(jìn)行重排，使其在物理上有序。012345678voidB_InsertSort(NodeTypeR[],intn){inti,j,p;DataTypeS;j=R[0].next;i=1;while(i<n)if(i==j){j=R[j].next;i++;}elseif(i<j){p=R[j].next;S=R[i];R[i]=R[j];R[j]=S;R[i].next=j;j=p;}elsewhile(j<i)j=R[j].next;}012345678MAX4938659776132749681504723jip134986jip27381jij7p387655jij496970pjip497648jijp659770jijp769708ij希爾排序Shell排序又稱縮小增量排序，排序的基本思想是先取d1<n,

將整個待排記錄分成d1個組，所有距離為d1倍數(shù)的記錄放在同一組中，先在各組進(jìn)行直接插入排序；然后，取d2<d1

重復(fù)上述分組和排序工作；直到di=1為止，就可以完成整個

的排序工作。Shell排序的一個特點(diǎn)是：子序列的構(gòu)成不是簡單“逐段

分割”，而是將相隔某個增量的記錄組成一個子序列。di有各種取法,Shell取D.Knuth取49386597761327495504初始：

d1=10/2=549132738496555970476一趟排序后：

1327495504493865977604273855二趟排序后：13044938274955659776041338494938279776希爾排序是個不穩(wěn)定的排序方法voidShellInsert(DataTypeR[],intdk){inti;for(i=dk+1;i<=n;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];}}voidShellSort(DataTypeR[],intn,intd[],intt){intk;for(k=0;k<t;k++)ShellInsert(R,d[k]);}10-3交換排序交換排序的基本方法是兩兩比較待排序記錄的排序碼，

交換不滿足順序要求的偶對，直到全部滿足為止。冒泡排序的方法是先將序列中的第一個記錄R0與第二個

記錄R1比較，若前者大于后者，則兩個記錄交換位置，

否則不交換;然后,對新的第二個記錄R1與第三個記錄R2

做同樣的處理；依次類推，直到處理完第n-1個記錄和

第n個記錄，從(R0,R1)到(Rn-2,Rn-1)的n-1次比較和交換

過程稱為一次起泡。重復(fù)這樣起泡過程最多n-1次就能完

成排序.冒泡排序voidBubble_Sort(DataTypeR[],intn){inti,j,swap;

for(i=1;i<n;i++){swap=0;for(j=1;j<=n-i;j++)

if(R[j].key>R[j+1].key){R[0]=R[j];R[j]=R[j+1];R[j+1]=R[0];swap=1;}if(swap==0)break;}}13

0449

38

27

49

55

65

97

76041338492749769704

13

38

27

49

49

55

65

76

97

2738最好情況下：移動次數(shù)為0，

比較次數(shù)為n-1最差情況下：比較次數(shù)

穩(wěn)定的排序方法快速排序快速排序基本思想是：通過一趟排序?qū)⒋庞涗浄指?/p>

成獨(dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一

部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)

進(jìn)行排序，以達(dá)到整個序列有序。一趟快速排序的具體做法是：附設(shè)兩個指針i和j,它們的

初值分別是一個序列的第一個和最后一個記錄的位置，

設(shè)樞軸記錄的關(guān)鍵字為temp.key，在首先從j所指位置起

向前搜索直到第一個關(guān)鍵字小于temp.key的記錄和i記錄

交換，然后從i所指位置起向后搜索，找到第一個

關(guān)鍵字大于temp.key的記錄和j記錄互相交換，重復(fù)

交替這兩步直到i=j為止。491438749665849552749ij27iii74jjj8i96jj492714388496596495574ij278ii38j278142738496596495574ij65j55i96j49i658142738495549659674intPartition(DataTypeR[],inti,intj)

{R[0]=R[i];while(i<j){while(i<j&&R[j].key>=R[0].key)j--;if(i<j){R[i]=R[j];i++;}while(i<j&&R[i].key<R[0].key)i++;if(i<j){R[j]=R[i];j--;}}R[i]=R[0];returni;}voidQuick_Sort(DataTypeR[],ints,intt){if(s<t){i=Partition(R,s,t);Quick_Sort(R,s,i-1);Quick_Sort(R,i+1,t);}}voidQuick(DataTypeR[],intn){

Quick_Sort(R,1,n);}快速排序的記錄移動次數(shù)不大于比較次數(shù)，所以，

快速排序的最壞時(shí)間復(fù)雜度應(yīng)為O(n2),最好時(shí)間

復(fù)雜度為O(nlog2n)。4927651483855499674上例中對應(yīng)的遞歸調(diào)用過程的二叉樹快速排序是通常被認(rèn)為同數(shù)量級的排序方法中

平均性能最好的?？焖倥判蚴且粋€不穩(wěn)定排序方法10-4選擇排序每一趟在n-i+1個記錄中選取關(guān)鍵碼最小的記錄作為

有序序列中第i個記錄，直到全部排完。簡單選擇排序基本方法是首先在所有記錄中選出排序碼最小的記錄，

與第一個記錄交換，然后在其余的記錄中再選出排序

碼最小的記錄與第二個記錄交換，以此類推，直到所

有記錄排好序。voidSelect_Sort(DataTypeR[],intn){inti,j,k;

for(i=1;i<n;i++){for(k=i,j=i+1;j<=n;j++)if(R[j].key<R[k].key)k=j;if(i!=k){R[0]=R[k];R[k]=R[i];R[i]=R[0];}}}4938659749132776i=1,k=6[13]38659749492776i=2,k=7[1327]659749493876i=3,k=7[132738]9749496576i=4,k=5[13273849]97496576i=5,k=6…直接選擇排序的比較次數(shù)與文件初始狀態(tài)無關(guān)。直接選擇排序的時(shí)間復(fù)雜度：最好移動次數(shù)為0，最壞移動次數(shù)為3(n-1)=O(n)。比較次數(shù)為n(n-1)/2=樹形選擇排序樹形選擇排序又稱錦標(biāo)賽排序，是一種按照錦標(biāo)賽的

思想進(jìn)行選擇排序的方法。首先對n個記錄的關(guān)鍵字

進(jìn)行兩兩比較，然后在n/2個較小者之間再進(jìn)行兩兩

比較，如此重復(fù)，直至選出最小的記錄為止。493865977613274938651327381313M76M2727由于含有n個子結(jié)點(diǎn)的完全二叉樹的深度為log2n+1，

則在樹形選擇排序中，除了最小數(shù)值之外，每選擇

一個次小數(shù)僅需要進(jìn)行l(wèi)og2n次比較，因此，它的時(shí)

間復(fù)雜度為O(nlogn)。但是，這種排序方法尚有輔

助存儲空間較多、和“最大值”進(jìn)行多余比較等缺點(diǎn)。

為了彌補(bǔ)，威洛姆斯（J.willioms）在1964年提出了

另一種形式的選擇排序——堆排序。堆排序堆的概念：高有n個元素的序列{k1,k2,…,kn},當(dāng)且僅當(dāng)

滿足下述關(guān)系之一，稱這為堆。如果堆中根結(jié)點(diǎn)的排序碼最小，則稱為小根堆；如果堆中根結(jié)點(diǎn)的排序碼最大，則稱為大根堆。堆排序的思想是：首先設(shè)法把原始序列構(gòu)造成一個堆，使得n個元素的最大值處于序列的第一個位置；然后交換序列第一元素(最大值元素)與最后一個元素。再把序列的前n-1個元素組成的子序列構(gòu)成一個新堆，重復(fù)以上步驟，最終整個序列成為有序序列。堆排序的關(guān)鍵是：(1)如何將一個無序序列建成一個堆；

(2)如何把“去掉”了最大值元素后的序列

調(diào)整剩余元素為一個新的堆。構(gòu)造初始堆是指把整個記錄從R1到Rn調(diào)整為一個大根堆。

完全二叉樹中，所有序號i>n/2的結(jié)點(diǎn)都是葉結(jié)點(diǎn)，以這

些結(jié)點(diǎn)為根的子樹均已是堆，只需依次將以序號

n/2,n/2-1,…,1結(jié)點(diǎn)為根的子樹調(diào)整為堆即可。

用篩選法為以Ri為根的完全二叉樹建堆，若Ri的左右子樹

都是堆，可以把Ri與其左右子樹根結(jié)點(diǎn)R2i+1,R2i+2中最大者

交換位置。若交換位置后破壞了子樹的堆特性，則再對這

棵子樹重復(fù)交換過程，直到以Ri為根結(jié)點(diǎn)的子樹成為堆。VoidheapAdjust(DataTypeR[],ints,intt){inti,j;DataTyperc;rc=R[s];i=s;for(j=2*i;j<=t;j=2*j){if(j<t&&R[j].key<R[j+1].key)j=j+1;if(rc.key>R[j].key)break;R[i]=R[j];i=j;}R[i]=rc;}05615948191126150105rcij61ij48ij1505voidHeapSort(DataTypeR[],intn){intI;for(i=n/2;i>0;i--)HeapAdjust(R,i,n);for(i=n;i>1;i--){R[0]=R[1];R[1]=R[i];R[i]=R[0];HeapAdjust(R,1,i-1);}}初始序列為26,5,77,1,61,11,59,15,48,19，請用堆排序法排序。（1）初始完全二叉樹(2)調(diào)整序號為5的結(jié)點(diǎn)(3)調(diào)整序號為4的結(jié)點(diǎn)(4)調(diào)整序號為3的結(jié)點(diǎn)(5)調(diào)整序號為2的結(jié)點(diǎn)(6)調(diào)整序號為1的結(jié)點(diǎn)(7)結(jié)點(diǎn)77與結(jié)點(diǎn)5互換(8)重建堆(9)結(jié)點(diǎn)61與結(jié)點(diǎn)1互換(10)重建堆(11)結(jié)點(diǎn)59與結(jié)點(diǎn)05互換(12)重建堆(13)結(jié)點(diǎn)48與結(jié)點(diǎn)1互換(14)重建堆(15)結(jié)點(diǎn)26與結(jié)點(diǎn)1互換(16)重建堆(17)結(jié)點(diǎn)19與結(jié)點(diǎn)5互換(18)重建堆(19)結(jié)點(diǎn)15與結(jié)點(diǎn)1互換(20)重建堆堆排序的時(shí)間耗費(fèi)主要在構(gòu)造初始堆，以及排序中去掉

最大元素后重建堆兩部分。初始建堆共調(diào)用HeapAdjust函數(shù)n/2次，每次將一個Ri(i<n/2)

為根的子樹樹調(diào)整為堆。個結(jié)點(diǎn)的完全二叉樹，其深度的結(jié)點(diǎn)層數(shù)依次為：0,1,1,2,2,2,…,h-1。

個，以它為根的子樹深度為h-m。第m層上結(jié)點(diǎn)數(shù)最多為HeapAdjust算法的每層上與兩個子女和排序碼值進(jìn)行比較，

所以在m層上結(jié)點(diǎn)執(zhí)行初始建堆最多比較2(h-m)次，第m層

所有子樹建堆最多比較次數(shù)為第一部分初始建堆總的比較次數(shù)為排序中每去掉最大元素后需要重建堆。重建堆需要與

排序碼的比較次數(shù)為第二部分排序中重建堆比較花費(fèi)總次數(shù)為整個堆排序總的比較次數(shù)為結(jié)點(diǎn)移動的次數(shù)小于比較次數(shù)，故總的時(shí)間復(fù)雜度。堆排序是不穩(wěn)定的!歸并排序的基本思想是把待排序的文件分成若干個子文件，

先將每個子文件內(nèi)的記錄排序，再將已排序的子文件合并，

得到完全排序的文件。10-5歸并排序假設(shè)初始的序列含有n個記錄，可以看成n個有序的子序列，

每個子序列的長度為1，然后兩兩歸并，得到個長度為

2或1的有序子序列；再兩兩歸并，如此重復(fù)直到得到一個

長度為n的有序序列為止。這種排序方法稱為二路歸并排序。voidMerge(DataTypeR[],DataTypeR1[],ints,intm,intt)

{inti,j,k;i=s;j=m+1;k=s;while(i<=m&&j<=t)

if(R[i].key<R[j].key){R1[k]=R[i];k++;i++;}else{R1[k]=R[j];k++;j++;

}while(i<=m)

{R1[k]=R[i];k++;i++;}

while(j<=t){R1[k]=R[j];k++;j++;

}}voidMergePass(DataTypeR[],DataTypeR1[],intlen,intn)

{inti;for(i=1;i+2*len-1<n;i=i+2*len)Merge(R,R1,i,i+len-1,i+2*len-1)if(i+len-1<n)Merge(R,R1,i,i+len-1,n);elseif(i<=n)while(i<=n)R1[i++]=R[i+1];}歸并排序的迭代算法VoidMergeSort(DataTypeR[],intn){DataTypeR1[MAXNUM];intlen;len=1;while(len<n){MergePass(R,R1,len,n)len=2*len;MergePass(R1,R,len,n);}}歸并排序的遞歸算法voidMSort(DataTypeR[],DataTypeR1[],ints,intt){intm;if(s==t)R1[s]=R[s];else{m=(s+t)/2;MSort(R,R1,s,m);MSort(R,R1,m+1,t);Merge(R1,R,s,m,t);}}voidMergeSort(DataTypeR[],intn){DataTypeR1[MAXNUM];MSort(R,R1,1,n);}25

57

48

37

12

82

75

29

16

255737481282297516253748571229758216122529374857758216121625293748577582算法分析：時(shí)間復(fù)雜度：空間復(fù)雜度:和待排記錄等量的空間。

二路歸并算法是穩(wěn)定的。一般情況下很少用于內(nèi)部排序。10-6基數(shù)排序基數(shù)排序?qū)儆诜峙渑判?，分配排序的思想是把排序碼

分解成若干部分，然后通過對各個部分排序碼的分別

排序，最終達(dá)到整個排序碼的排序?；鶖?shù)排序是采用“分配”與“收集”的辦法，用對多關(guān)鍵碼

進(jìn)行排序的思想實(shí)現(xiàn)對單關(guān)鍵碼進(jìn)行排序的方法。多關(guān)鍵碼排序1.以撲克牌排序?yàn)槔?。每張撲克牌有兩個“關(guān)鍵碼”：

花色和面值。其有序關(guān)系為：花色：梅花<方塊<紅心<黑桃面值：2<3<4<5<6<7<8<9<10<J<Q<K<A

可以先按花色排序，之后再按面值排序；

也可以先按面值排序，再按花色排序。文件中任一記錄R[i]的關(guān)鍵字均由d個分量

構(gòu)成。

若這d個分量中每個分量都是一個獨(dú)立的關(guān)鍵字，則文件是多

關(guān)鍵字的(如撲克牌有兩個關(guān)鍵字：點(diǎn)數(shù)和花色)；設(shè)單關(guān)鍵字的每個分量的取值范圍均是：

C0≤kj≤Crd-1(0≤j<d)

可能的取值個數(shù)rd稱為基數(shù)。

基數(shù)排序的基本思想是：從低位到高位依次對

Kj(j=d-1，d-2，…，0)進(jìn)行箱排序。在d趟箱排

序中，所需的箱子數(shù)就是基數(shù)rd，這就是“基數(shù)

排序"名稱的由來。

2781090639305891845052690080830123456789q.e0123456789q.fq[0].e2781090639305891845050830082699300630831845052780081095892690123456789q.e0123456789q.f9300630831845052780081095892695050081099300632692780831845890123456789q.e0123456789q.f505008109930063269278083184589008063083109184269278505589930#defineKEY_NUM…#defineRADIX…#defineMAX_SPACE…Typedefstruct{KeyTypekeys[KEY_NUM];InfoTypeotheritems;intnext;}NodeType;Typedefstruct{intf;inte;}Q_Node;TypedefQ_NodeQueue[RADIX];voidDistribute(NodeTypeR[],inti,Queueq){intj;for(j=0;j<RADIX;j++)