第10章內(nèi)排序10.6基數(shù)排序本章小結(jié)10.1排序的基本概念10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.7各種內(nèi)排序方法的比較和選擇10.1排序的基本概念

所謂排序,就是要整理表中的記錄,使之按關(guān)鍵字遞增(或遞減)有序排列。其確切定義如下：輸入：n個(gè)記錄,R0,R1,…,Rn-1,其相應(yīng)的關(guān)鍵字分別為k0,k1,…,kn-1。輸出：Ri0,Ri1,…,Rin-1,使得ki0≤ki1≤…≤kin-1(或ki0≥ki1≥…≥kin-1)。

當(dāng)待排序記錄的關(guān)鍵字均不相同時(shí),排序的結(jié)果是惟一的,否則排序的結(jié)果不一定惟一。如果待排序的表中,存在有多個(gè)關(guān)鍵字相同的記錄,經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對(duì)次序保持不變,則稱這種排序方法是穩(wěn)定的；反之,若具有相同關(guān)鍵字的記錄之間的相對(duì)次序發(fā)生變化,則稱這種排序方法是不穩(wěn)定的。在排序過程中,若整個(gè)表都是放在內(nèi)存中處理,排序時(shí)不涉及數(shù)據(jù)的內(nèi)、外存交換,則稱之為內(nèi)排序；反之,若排序過程中要進(jìn)行數(shù)據(jù)的內(nèi)、外存交換,則稱之為外排序。待排序的順序表類型的類型定義如下：

typedefintKeyType;/*定義關(guān)鍵字類型*/typedefstruct /*記錄類型*/{ KeyTypekey;/*關(guān)鍵字項(xiàng)*/InfoTypedata;/*其他數(shù)據(jù)項(xiàng),類型為InfoType*/}RecType; /*排序的記錄類型定義*/RecTypeR[N];數(shù)組R中存放著待排序的記錄10.2插入排序

插入排序的基本思想是：每次將一個(gè)待排序的記錄,按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子表中的適當(dāng)位置,直到全部記錄插入完成為止。三種插入排序方法：

(1)直接插入排序

(2)二分插入排序

(2)希爾排序。10.2.1直接插入排序

假設(shè)待排序的記錄存放在數(shù)組R[0..n-1]中,排序過程的某一中間時(shí)刻,R被劃分成兩個(gè)子區(qū)間R[0..i-1]和R[i..n-1],其中：前一個(gè)子區(qū)間是已排好序的有序區(qū),后一個(gè)子區(qū)間則是當(dāng)前未排序的部分,不妨稱其為無序區(qū)。直接插入排序的基本操作是將當(dāng)前無序區(qū)的第1個(gè)記錄R[i]插入到有序區(qū)R[0..i-1]中適當(dāng)?shù)奈恢蒙?使R[0..i]變?yōu)樾碌挠行騾^(qū)。這種方法通常稱為增量法,因?yàn)樗看问褂行騾^(qū)增加1個(gè)記錄。例49386597761327i=2

(3849)6597761327i=3

(384965)97761327i=4

(38496597)761327i=5

(3849657697)1327i=6

(133849657697)27i=1()(133849657697)27jjjjjj977665493827(13273849657697)排序結(jié)果：

0123456voidInsertSort(RecTypeR[],intn)/*對(duì)R[0..n-1]按遞增有序進(jìn)行直接插入排序*/{inti,j; RecTypetemp;for(i=1;i<n;i++){temp=R[i]; j=i-1;/*從右向左在有序區(qū)R[0..i-1]找R[i]的插入位置*/while(j>=0&&temp.key<R[j].key){R[j+1]=R[j];/*將關(guān)鍵字大于R[i].key的記錄后移*/j--; }R[j+1]=temp;/*在j+1處插入R[i]*/}}10.2.2二分插入排序由于插入排序是在一個(gè)有序表中進(jìn)行查找和插入，若查找時(shí)采用二分查找方法，則直接插入排序就變成了二分插入排序。voidInsertSort1(RecTypeR[],intn){inti,j,low,high,mid; RecTypetemp;for(i=1;i<n;i++){temp=R[i];low=0;high=i-1;while(low<=high){mid=(low+high)/2;if(temp.key<R[mid].key)high=mid-1;elselow=mid+1;} for(j=i-1;j>=high+1;j--)R[j+1]=R[j];/*將關(guān)鍵字大于R[i].key的記錄后移*/

R[high+1]=temp;

}}10.2.3希爾排序

希爾排序也是一種插入排序方法,實(shí)際上是一種分組插入方法。其基本思想是：先取定一個(gè)小于n的整數(shù)d1作為第一個(gè)增量,把表的全部記錄分成d1個(gè)組,所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中,在各組內(nèi)進(jìn)行直接插入排序；然后,取第二個(gè)增量d2(＜d1),重復(fù)上述的分組和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹?。一趟分組：49

38

65

97

76

13

27

48

55

4先取組數(shù)d1=5(分5組）取d3=1(1組）三趟分組：134

4838

274955659776三趟排序：4132738484955657697例初始：4938659776132748554一趟排序：13

27

48

55

4

49

38

65

97

76二趟排序：13

4

48

38

27

49

55

65

97

76一趟分組：49

38

65

97

76

13

27

48

55

4取d2=3（分3組）二趟分組：13

27

48

55

4

49

38

65

97

76先取組數(shù)d1=5(分5組）voidShellSort(RecTypeR[],intn)/*希爾排序算法*/{inti,j,d;RecTypetemp;d=n/2; /*d取初值n/2*/while(d>0){for(i=d;i<n;i++)/*將R[d..n-1]分別插入各組當(dāng)前有序區(qū)*/{j=i-d; while(j>=0&&R[j].key>R[j+d].key) {temp=R[j];/*R[j]與R[j+d]交換*/ R[j]=R[j+d];R[j+d]=temp; j=j-d; }}d=d/2; /*遞減增量d*/}}

例10.2設(shè)待排序的表有10個(gè)記錄,其關(guān)鍵字分別為{9,8,7,6,5,4,3,2,1,0}。說明采用希爾排序方法進(jìn)行排序的過程。子序列的構(gòu)成不是簡(jiǎn)單的“逐段分割”，而是將相隔某個(gè)增量的記錄組成一個(gè)子序列希爾排序可提高排序速度分組后n值減小，n2更小，而T(n)=O(n2),所以T(n)從總體上看是減小了關(guān)鍵字較小的記錄跳躍式前移，在進(jìn)行最后一趟增量為1的插入排序時(shí)，序列已基本有序平均時(shí)間復(fù)雜度：與每趟的增量有關(guān)如：

d[t]={n/2,n/4,…,1}O(n1.5)希爾排序是不穩(wěn)定的最后一個(gè)增量值必須為1希爾排序特點(diǎn)10.3交換排序

交換排序的基本思想：兩兩比較待排序記錄的關(guān)鍵字,發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)行交換,直到?jīng)]有反序的記錄為止。

兩種交換排序:(1)冒泡排序

(2)快速排序10.3.1冒泡排序

冒泡排序的基本思想是：

通過無序區(qū)中相鄰記錄關(guān)鍵字間的比較和位置的交換,使關(guān)鍵字最小的記錄如氣泡一般逐漸往上“漂浮”直至“水面”。整個(gè)算法是從最下面的記錄開始,對(duì)每?jī)蓚€(gè)相鄰的關(guān)鍵字進(jìn)行比較,且使關(guān)鍵字較小的記錄換至關(guān)鍵字較大的記錄之上,使得經(jīng)過一趟冒泡排序后,關(guān)鍵字最小的記錄到達(dá)最上端,接著,再在剩下的記錄中找關(guān)鍵字次小的記錄,并把它換在第二個(gè)位置上。依次類推,一直到所有記錄都有序?yàn)橹?。?938659776132730

初始關(guān)鍵字1327

4938

65977630

第二趟1327304938659776

第三趟13273038

49657697

第四趟12345678從下往上掃描1349386597762730第一趟voidBubbleSort(RecTypeR[],intn){inti,j; RecTypetemp;for(i=0;i<n-1;i++){for(j=n-1;j>i;j--) /*比較找本趟最小關(guān)鍵字的記錄*/if(R[j].key<R[j-1].key)//相鄰記錄的比較

{ temp=R[j];/*R[j]與R[j-1]進(jìn)行交換*/ R[j]=R[j-1]; R[j-1]=temp; }}}

例10.3設(shè)待排序的表有10個(gè)記錄,其關(guān)鍵字分別為{9,8,7,6,5,4,3,2,1,0}。說明采用冒泡排序方法進(jìn)行排序的過程。

在有些情況下,在第i(i＜n-1)趟時(shí)已排好序了,但仍執(zhí)行后面幾趟的比較。實(shí)際上,一旦算法中某一趟比較時(shí)不出現(xiàn)記錄交換,說明已排好序了,就可以結(jié)束本算法。為此,改進(jìn)冒泡排序算法如下：

voidBubbleSort(RecTypeR[],intn){inti,j,exchange;RecTypetemp;for(i=0;i<n-1;i++){exchange=0; for(j=n-1;j>i;j--) /*比較,找出最小關(guān)鍵字的記錄*/if(R[j].key<R[j-1].key) {temp=R[j];R[j]=R[j-1];R[j-1]=temp;

exchange=1; } if(exchange==0)return;/*中途結(jié)束算法*/}}空間復(fù)雜度：S(n)=O(1)算法評(píng)價(jià)時(shí)間復(fù)雜度最好情況（正序）：只需一趟掃描即可比較次數(shù)：n-1移動(dòng)次數(shù)：0最壞情況（逆序）比較次數(shù)：移動(dòng)次數(shù)：T(n)=O(n2)起泡排序：比較和交換在相鄰單元中進(jìn)行，移動(dòng)幅度僅一個(gè)單元，致使比較和移動(dòng)次數(shù)較多；每經(jīng)過一趟起泡，無序序列的長(zhǎng)度只縮小1。設(shè)想：若能在經(jīng)過一趟排序，使無序序列的長(zhǎng)度縮小一半，則必能加快排序的速度。10.3.2快速排序

快速排序是由冒泡排序改進(jìn)而得的,它的基本思想是：在待排序的n個(gè)記錄中任取一個(gè)記錄(通常取第一個(gè)記錄，稱為基準(zhǔn)記錄),把該記錄放入適當(dāng)位置后,數(shù)據(jù)序列被此記錄劃分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的記錄放置在前一部分,所有比它大的記錄放置在后一部分,并把該記錄排在這兩部分的中間(稱為該記錄歸位),這個(gè)過程稱作一趟快速排序。之后對(duì)所有的兩部分分別重復(fù)上述過程,直至每部分內(nèi)只有一個(gè)記錄為止。簡(jiǎn)而言之,每趟使表的第一個(gè)元素放入適當(dāng)位置,將表一分為二,對(duì)子表按遞歸方式繼續(xù)這種劃分,直至劃分的子表長(zhǎng)為1。快速排序過程例如:初始關(guān)鍵字序列

5，6，3，1，2，7R[]:012345選第一個(gè)元素為基準(zhǔn)元素第一趟快速排序：（2，1，3），5，（6，7）第二趟快速排序：（1），2，（3），5，6，（7）i:基準(zhǔn)位置[0..i-1][i+1..n-1][i]結(jié)束條件：待排區(qū)間只有一個(gè)記錄或無記錄R[]:012345一次劃分

初始關(guān)鍵字：4938659776132750ij基準(zhǔn)元素temp=49ji

完成一趟排序：(273813)49(76976550)分別進(jìn)行快速排序：(13)27(38)49(5065)76(97)快速排序結(jié)束：13273849506576974927ijijij4965ji1349ij4997ij調(diào)整過程中的基準(zhǔn)位置并不重要，因此，為了減少記錄的移動(dòng)次數(shù)，應(yīng)先將基準(zhǔn)記錄“移出”，待求得基準(zhǔn)記錄應(yīng)在的位置之后(此時(shí)i=j),再將基準(zhǔn)記錄歸位。一趟劃分實(shí)現(xiàn)過程voidQuickSort(RecTypeR[],ints,intt)/*對(duì)R[s]至R[t]的元素進(jìn)行快速排序*/{inti=s,j=t; RecTypetemp;if(s<t)/*區(qū)間內(nèi)至少存在一個(gè)元素的情況*/{ temp=R[s]; /*用區(qū)間的第1個(gè)記錄作為基準(zhǔn)*/ while(i!=j) /*從兩端交替向中間掃描,直至i=j為止*/ {while(j>i&&R[j].key>temp.key)j--; if(i<j)/*表示找到這樣的R[j],R[i]、R[j]交換*/ {R[i]=R[j];i++;}while(i<j&&R[i].key<temp.key)i++; if(i<j)/*表示找到這樣的R[i],R[i]、R[j]交換*/ {R[j]=R[i];j--;} } R[i]=temp;QuickSort(R,s,i-1);/*對(duì)左區(qū)間遞歸排序*/QuickSort(R,i+1,t);/*對(duì)右區(qū)間遞歸排序*/}}劃分

例10.4設(shè)待排序的表有10個(gè)記錄,其關(guān)鍵字分別為{6,8,7,9,0,1,3,2,4,5}。說明采用快速排序方法進(jìn)行排序的過程。算法評(píng)價(jià)時(shí)間復(fù)雜度最好情況（每次總是選到中間值作基準(zhǔn)）T(n)=O(nlog2n)最壞情況（每次總是選到最小或最大元素作基準(zhǔn)）T(n)=O(n2)空間復(fù)雜度：需?？臻g以實(shí)現(xiàn)遞歸最壞情況：S(n)=O(n)一般情況：S(n)=O(log2n)平均：T(n)=O(nlog2n)10.4選擇排序

選擇排序的基本思想是：每一趟從待排序的記錄中選出關(guān)鍵字最小的記錄,順序放在已排好序的子表的最后,直到全部記錄排序完畢。

兩種選擇排序方法：

(1)直接選擇排序(或稱簡(jiǎn)單選擇排序)(2)堆排序10.4.1直接選擇排序

直接選擇排序的基本思想是：第i趟排序開始時(shí),當(dāng)前有序區(qū)和無序區(qū)分別為R[0..i-1]和R[i..n-1](0≤i＜n-1),該趟排序則是從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄R[k],將它與無序區(qū)的第1個(gè)記錄R[i]交換,使R[0..i]和R[i+1..n-1]分別變?yōu)樾碌挠行騾^(qū)和新的無序區(qū)。

因?yàn)槊刻伺判蚓褂行騾^(qū)中增加了一個(gè)記錄,且有序區(qū)中的記錄關(guān)鍵字均不大于無序區(qū)中記錄的關(guān)鍵字,即第i趟排序之后R[0..i]的所有關(guān)鍵字小于等于R[i+1..n-1]中的所有關(guān)鍵字,所以進(jìn)行n-1趟排序之后有R[0..n-2]的所有關(guān)鍵字小于等于R[n-1].key,也就是說,經(jīng)過n-1趟排序之后,整個(gè)表R[0..n-1]遞增有序。例初始：[49386597761327]kjjjjjjkki=01349一趟：13

[386597764927]i=1kkjjjjj2738二趟：13

27

[6597764938]三趟：13

27

38[97764965]四趟：13

27

38

49[769765]五趟：13

27

38

49

65

[9776]六趟：13

27

38

49

65

76[97]排序結(jié)束：13

27

38

49

65

76

97實(shí)現(xiàn)過程voidSelectSort(RecTypeR[],intn){inti,j,k;RecTypetemp;for(i=0;i<n-1;i++) /*做第i趟排序*/{k=i; for(j=i+1;j<n;j++)/*在[i..n-1]中選key最小的R[k]*/ if(R[j].key<R[k].key) k=j;/*k記下的最小關(guān)鍵字所在的位置*/ if(k!=i)/*交換R[i]和R[k]*/ {temp=R[i];R[i]=R[k];R[k]=temp;}}}

例10.5設(shè)待排序的表有10個(gè)記錄,其關(guān)鍵字分別為{6,8,7,9,0,1,3,2,4,5}。說明采用直接選擇排序方法進(jìn)行排序的過程。算法評(píng)價(jià)時(shí)間復(fù)雜度記錄移動(dòng)次數(shù)最好情況：0(已正序的紀(jì)錄不用移動(dòng))最壞情況：3(n-1)每趟均需交換比較次數(shù)：空間復(fù)雜度：S(n)=O(1)T(n)=O(n2)10.4.2堆排序堆排序是一樹形選擇排序,它的特點(diǎn)是,在排序過程中,將R[1..n]看成是一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu),利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系,在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大(或最小)的記錄。

堆的定義:堆是滿足下列性質(zhì)的數(shù)列{k1,k2,…，kn}：或若將此數(shù)列看成是一棵順序存儲(chǔ)的完全二叉樹:則堆或是空樹或是滿足下列特性的完全二叉樹：根結(jié)點(diǎn)的值小于(或大于)左/右子樹根結(jié)點(diǎn)的值。分別稱作小根堆或大根堆。例（96，83，27，38，11，9）例（13，38，27，50，76，65，49，97）962791138831327384965765097堆頂元素k1必為序列中n個(gè)元素的最小值或最大值96832738119012345696279113883初始大根堆存儲(chǔ)結(jié)構(gòu)內(nèi)存中962791138839279611388383279611389832796119381127968393811279683938382796839119279683381127996833811調(diào)整實(shí)現(xiàn)過程將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中大者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)；得到新大根堆；27996833811927968338111127968338992796833811911273883960123456

堆排序的關(guān)鍵是構(gòu)造堆,這里采用篩選算法建堆：假若完全二叉樹的某一個(gè)結(jié)點(diǎn)i對(duì)于它的左子樹、右子樹已是堆,接下來需要將R[2i].key與R[2i+1].key之中的最大者與R[i].key比較,若R[i].key較小則交換,這有可能破壞下一級(jí)的堆。于是繼續(xù)采用上述方法構(gòu)造下一級(jí)的堆。直到完全二叉樹中結(jié)點(diǎn)i構(gòu)成堆為止。對(duì)于任意一棵完全二叉樹,從i=n/2到1,反復(fù)利用上述思想建堆。大者“上浮”,小者被“篩選”下去。其調(diào)整堆的算法sift()如下：voidsift(RecTypeR[],intlow,inthigh)//對(duì)R[low..high]進(jìn)行篩選{inti=low,j=2*i;/*R[j]是R[i]的左孩子*/

RecTypetemp=R[i];while(j<=high){if(j<high&&R[j].key<R[j+1].key)j++;if(temp.key<R[j].key){R[i]=R[j];/*將R[j]調(diào)整到雙親結(jié)點(diǎn)位置上*/ i=j; /*修改i和j值,以便繼續(xù)向下篩選*/ j=2*i; } elsebreak; /*篩選結(jié)束*/}R[i]=temp; /*被篩選結(jié)點(diǎn)的值放入最終位置*/}

有了調(diào)整堆的函數(shù),利用該函數(shù),將已有堆中的根與最后一個(gè)葉子交換,進(jìn)一步恢復(fù)堆,直到一棵樹只剩一個(gè)根為止。實(shí)現(xiàn)堆排序的算法如下：voidHeapSort(RecTypeR[],intn)//對(duì)R[1..n]做堆排序{inti; RecTypetemp;for(i=n/2;i>=1;i--) /*循環(huán)建立初始堆*/sift(R,i,n);for(i=n;i>=2;i--)/*進(jìn)行n-1次循環(huán),完成推排序*/{ temp=R[1];/*將第一個(gè)元素同當(dāng)前區(qū)間內(nèi)R[1]對(duì)換*/ R[1]=R[i];R[i]=temp; sift(R,1,i-1);/*篩選R[1]結(jié)點(diǎn),得到i-1個(gè)結(jié)點(diǎn)的堆*/}}

例10.6設(shè)待排序的表有10個(gè)記錄,其關(guān)鍵字分別為{6,8,7,9,0,1,3,2,4,5}。說明采用堆排序方法進(jìn)行排序的過程。堆排序過程：98978998978966565645645634563456222堆排序的時(shí)間復(fù)雜度為O(nlog2n)建初始堆所需比較次數(shù)較多，以后各趟只需對(duì)堆頂元素進(jìn)行篩選，所以堆排序?qū)較大的文件十分有效。10.5歸并排序

歸并排序是多次將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。最簡(jiǎn)單的歸并是直接將兩個(gè)有序的子表合并成一個(gè)有序的表。

將兩個(gè)有序表直接歸并為一個(gè)有序表的算法Merge()：0123 45674913659776780R0123 4567R1ijkMERGE(rectypeR[],intlow,intmid,inthigh)lowmidmid+1high7jk13ik49ik65ik76jk4913659776780R0123 4567R1ijk713496576800123 45674913659776780R0123 4567R1ijk71349657680將剩余的R[i..mid]復(fù)制到R10123 4567lowmidmid+1high4913659776780R0123 4567R1ijk71349657680970123 4567lowmidmid+1highvoidMerge(RecTypeR[],intlow,intmid,inthigh){RecType*R1;inti=low,j=mid+1,k=0;/*k是R1的下標(biāo),i、j分別為第1、2段的下標(biāo)*/R1=(RecType*)malloc((high-low+1)*sizeof(RecType));while(i<=mid&&j<=high) if(R[i].key<=R[j].key)/*將第1段中的記錄放入R1中*/ {R1[k]=R[i];i++;k++;} else/*將第2段中的記錄放入R1中*/ {R1[k]=R[j];j++;k++;}有序子序列R[low..mid]有序子序列R[mid+1..high]

有序序列R1[low..high] while(i<=mid)/*將第1段余下部分復(fù)制到R1*/ {R1[k]=R[i];i++;k++;}while(j<=high)/*將第2段余下部分復(fù)制到R1*/ {R1[k]=R[j];j++;k++;}for(k=0,i=low;i<=high;k++,i++)/*將R1復(fù)制回R中*/ R[i]=R1[k];

free(R1);}voidMergePass(RecTypeR[],intlength,intn){inti;for(i=0;i+2*length-1<n;i=i+2*length)/*歸并length長(zhǎng)的兩相鄰子表*/ Merge(R,i,i+length-1,i+2*length-1);if(i+length-1<n)/*余下兩個(gè)子表,后者長(zhǎng)度小于length*/ Merge(R,i,i+length-1,n-1); /*歸并這兩個(gè)子表*/}MergePass()實(shí)現(xiàn)了一趟歸并

二路歸并排序算法如下：voidMergeSort(RecTypeR[],intn) /*自底向上的二路歸并算法*/{ intlength; for(length=1;length<n;length=2*length) MergePass(R,length,n);}

例10.7設(shè)待排序的表有8個(gè)記錄,其關(guān)鍵字分別為{18,2,20,34,12,32,6,16}。說明采用歸并排序方法進(jìn)行排序的過程。歸并排序的時(shí)間復(fù)雜度為O(nlog2n)10.6基數(shù)排序前面所討論的排序算法均是基于關(guān)鍵字之間的比較來實(shí)現(xiàn)的,而基數(shù)排序是通過“分配”和“收集”過程來實(shí)現(xiàn)排序,是一種借助于多關(guān)鍵字排序的思想對(duì)單關(guān)鍵字排序的方法。

一般地,記錄R[i]的關(guān)鍵字R[i].key是由d位數(shù)字組成,即kd-1kd-2…k0,每一個(gè)數(shù)字表示關(guān)鍵字的一位,其中kd-1為最高位,k0是最低位,每一位的值都在0≤ki＜r范圍內(nèi),其中,r稱為基數(shù)。例如,對(duì)于二進(jìn)制數(shù)r為2,對(duì)于十進(jìn)制數(shù)r為10。基數(shù)排序有兩種：最低位優(yōu)先和最高位優(yōu)先。最低位優(yōu)先的過程是：先按最低位的值對(duì)記錄進(jìn)行排序,在此基礎(chǔ)上,再按次低位進(jìn)行排序,依此類推。由低位向高位,每趟都是根據(jù)關(guān)鍵字的一位并在前一趟的基礎(chǔ)上對(duì)所有記錄進(jìn)行排序,直至最高位,則完成了基數(shù)排序的整個(gè)過程。

以r為基數(shù)的最低位優(yōu)先排序的過程是：假設(shè)線性表由結(jié)點(diǎn)序列a0,a1,…,an-l構(gòu)成,每個(gè)結(jié)點(diǎn)aj的關(guān)鍵字由d元組組成,其中0≤kji≤r-1(0≤j＜n,0≤i≤d-1)。在排序過程中,使用r個(gè)隊(duì)列Q0,Q1,…,Qr-1。排序過程如下：對(duì)i=0,1,…,d-1,依次做一次“分配”和“收集”(其實(shí)就是一次穩(wěn)定的排序過程)。分配：開始時(shí),把Q0,Q1,…,Qr-1各個(gè)隊(duì)列置成空隊(duì)列,然后依次考察線性表中的每一個(gè)結(jié)點(diǎn)aj(j=0,1,…,n-1),如果aj的關(guān)鍵字k=k,就把a(bǔ)j放進(jìn)Qk隊(duì)列中。收集：把Q0,Q1,…,Qr-1各個(gè)隊(duì)列中的結(jié)點(diǎn)依次首尾相接,得到新的結(jié)點(diǎn)序列,從而組成新的線性表。#defineMAXE20 /*線性表中最多元素個(gè)數(shù)*/#defineMAXR10 /*基數(shù)的最大取值*/#defineMAXD8 /*關(guān)鍵字位數(shù)的最大取值*/typedefstructnode{chardata[MAXD]; /*記錄的關(guān)鍵字定義的字符串*/structnode*next;}RecType;voidRadixSort(RecType*&p,intr,intd)/*p為待排序序列鏈表指針,r為基數(shù),d為關(guān)鍵字位數(shù)*/{ RecType*head[MAXR],*tail[MAXR],*t;/*定義各鏈隊(duì)的首尾指針*/ inti,j,k; for(i=d-1;i>=0;i--) /*從低位到高位做d趟排序*/ /*123以“3