第9章排序9.1排序的基本概念9.2插入排序9.3交換排序9.4選擇排序9.5歸并排序9.6基數(shù)排序*9.7外排序簡介9.8各種內(nèi)排序方法的比較

9.1排序的基本概念

排序是計算機(jī)程序設(shè)計中的一種重要操作，其功能是按照記錄集合中每個記錄的關(guān)鍵字之間所存在的遞增或遞減關(guān)系將該集合中的記錄次序重新排列。排序的主要目的是方便查找，如有序表的折半查找，并且二叉排序樹、B樹和B+樹的構(gòu)造過程本身就是一個排序過程。

如果待排序的記錄序列中Ri和Rj的關(guān)鍵字相同，且在排序之前Ri的位置領(lǐng)先于Rj，若在排序之后Ri的位置仍然領(lǐng)先于Ri，則為穩(wěn)定排序；反之為不穩(wěn)定排序(通常是找出實例來驗證這種不穩(wěn)定關(guān)系)。按照記錄序列存放物理位置的不同又分為內(nèi)排序和外排序。內(nèi)排序的排序過程是在內(nèi)存中進(jìn)行的，而外排序在排序過程中則需要在內(nèi)、外存之間交換信息。此外，按排序的策略不同可以將內(nèi)排序劃分為五種類型：①插入排序；②交換排序；③選擇排序；④歸并排序；⑤基數(shù)排序。

每一種內(nèi)排序均可以在不同的存儲結(jié)構(gòu)上實現(xiàn)。通常待排序的記錄有三種存儲結(jié)構(gòu)：

(1)以一維數(shù)組作為存儲結(jié)構(gòu)：排序過程是對記錄本身進(jìn)行物理重排，即通過比較和判斷，把記錄移到合適的位置上。

(2)以鏈表作為存儲結(jié)構(gòu)：排序過程中無需移動記錄，只要修改指針即可。通常把這類排序稱為表排序。

(3)采用輔助表排序：有的排序方法難以在鏈表上實現(xiàn)卻又要避免排序過程中的記錄移動，這時就可為待排序記錄建立一個輔助表來完成排序。例如，由記錄的關(guān)鍵字和指向記錄的指針?biāo)M成的索引表。這樣，排序過程中只需對這個輔助表的表項進(jìn)行物理重排即可。也即，只移動輔助表項而不移動記錄本身。簡單評判一種排序方法的好壞是困難的，這是因為在不同情況下排序算法的好壞是不一樣的。評價排序方法好壞的標(biāo)準(zhǔn)主要有兩條：一是算法執(zhí)行所需的時間；二是算法執(zhí)行中所需的輔助空間。由于排序是經(jīng)常使用的一種運(yùn)算，故算法執(zhí)行所需的時間是衡量排序方法好壞的重要標(biāo)志。

在介紹排序方法之前，我們先定義記錄的存儲結(jié)構(gòu)及類型如下：

typedefstruct

{

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

OtherTypedata;//其他數(shù)據(jù)項

}RecordType;//記錄類型 9.2插入排序

9.2.1直接插入排序

直接插入排序是一種最簡單的排序方法，其做法是：在插入第i個記錄R[i]時，R[1]、R[2]、…、R[i-1]已經(jīng)排好序，這時將待插入記錄R[i]的關(guān)鍵字R[i].key由后向前依次與關(guān)鍵字R[i-1].key、R[i-2].key、…、R[1].key進(jìn)行比較，從而找到R[i]應(yīng)該插入的位置j，并且由后向前依次將R[i-1]、R[i-2]、…、R[j+1]、R[j]順序后移一個位置(這樣移動可保證每個被移動的記錄信息不被破壞)，然后將R[i]放入到剛剛讓出其位置的原R[j]處。這種插入使得前i個位置上的所有記錄R[1]、R[2]、…、R[i]繼續(xù)保持有序。直接插入排序的算法如下：

voidD_Insert(RecordTypeR[],intn)

{//對n個記錄序列R[1]～R[n]進(jìn)行直接插入排序

inti,j;

for(i=2;i<=n;i++) //進(jìn)行n-1趟排序

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

{//R[i].key小于R[i-1].key時需將R[i]插入到有序序列R[1]～R[i-1]中

R[0]=R[i]; //設(shè)置查找監(jiān)視哨并保存待插入記錄R[i]值

j=i-1;

while(R[j].key>R[0].key)

{/*將關(guān)鍵字值大于R[i].key(即此時的R[0].key)

的所有R[j](j=i-1,i-2,…)順序后移一個記錄位置*/

R[j+1]=R[j];

j--;

}

R[j+1]=R[0];//將R[i](也即此時的R[0])插入到應(yīng)插入的位置上

}

}算法中，R[1]～R[i-1]是有序表，R[i]～R[n]是無序表。i總是指向無序表中的第一個元素位置，而該元素(即R[i])就是本趟要插入到有序表中的元素。外層for循環(huán)i從2變化到n是因為僅有一個記錄的表是有序的(即初始時有序表為R[1]，無序表為R[2]～R[n])，因此，是從R[2]開始直到R[n]逐個向有序表中進(jìn)行插入操作的。也即，外層for循環(huán)共執(zhí)行了n-1趟。內(nèi)層while循環(huán)開始前j總是指向有序表中的最后一個元素位置(即R[i-1])，然后通過“j--”操作由后向前在有序表R[1]～R[i-1]中尋找R[i]應(yīng)該插入的位置，并在查找的同時將關(guān)鍵字大于R[i]關(guān)鍵字的所有記錄都順序后移一個記錄位置。外層for循環(huán)每一趟插入結(jié)束時，有序表已變?yōu)镽[1]～R[i]，無序表則變?yōu)镽[i+1]～R[n]。這時，外層for循環(huán)的“i++”又使i指向縮小后的無序表新的第一個元素位置。這樣，經(jīng)過n-1趟插入排序后，有序表變?yōu)镽[1]～R[n]，無序表則變?yōu)榭?，即此時n個記錄已按關(guān)鍵字有序，插入排序結(jié)束。引入R[0]的作用有兩個：一是保存了記錄R[i]的值，即不至于在記錄后移的操作中失去待插記錄R[i]的值；其二是在while循環(huán)中取代檢查j是否小于1的功能，即防止下標(biāo)越界。也即當(dāng)j為0時，while循環(huán)的判斷條件就變成了“R[0].key>R[0].key”，即終止while循環(huán)。因此，R[0]起到了“監(jiān)視哨”的作用。

圖9-1給出了直接插入排序的排序過程。在圖9-1中，i從2變化到n(n=8)，同時i-1也表示插入的次數(shù)(即排序的趟數(shù))，方括號“[]”中的記錄序列為有序表，方括號“[]”之外的記錄序列為無序表。由圖9-1也可看出：排序前48在48之后，排序后48仍在48之后。故直接插入排序為穩(wěn)定的排序方法。圖9-1直接插入排序過程示意圖從空間效率上看，直接插入排序僅使用了R[0]一個輔助單元，故空間復(fù)雜度為O(1)。從時間效率上看，直接插入排序算法由雙重循環(huán)組成，外層的for循環(huán)進(jìn)行了n-1趟(向有序表中插入第2到第n個記錄)；內(nèi)層while循環(huán)用于確定待插入記錄的具體插入位置并在保證有序情況下空出插入的位置，其主要操作是進(jìn)行關(guān)鍵字的比較和記錄的后移。而比較次數(shù)和后移次數(shù)則取決于待排序列中各記錄關(guān)鍵字的初始序列，可分三種情況討論：

(1)最好情況：待排序列已按關(guān)鍵字有序，每趟只需1次比較和0次移動。即：

總比較次數(shù)?=?趟數(shù)?=?n-1次

總移動次數(shù)?=?0次

(2)最壞情況：待排序列已按關(guān)鍵字有序，但為逆序。這時每趟都需要將待插入記錄插入到有序序列的第一個記錄位置，即第i趟操作要將記錄R[i]插入到原R[1]的位置，這需要同前面的i個記錄(包括監(jiān)視哨R[0])進(jìn)行i次關(guān)鍵字的比較，移動記錄的次數(shù)(包括將R[i-1]～R[1]移至R[i]～R[2]，以及初始的R[i]賦給R[0]，和移動結(jié)束時的R[0]賦給R[j+1])為i+1次。即：

(3)平均情況：可取(1)和(2)這兩種極端情況的平均值，即約為。因此，直接插入排序的時間復(fù)雜度為O(n2)。9.2.2折半插入排序

在直接插入排序中，記錄集合被分為有序序列集合{R[1],R[2],…,R[i-1]}和無序序列{R[i],R[i+1],…,R[n]}。并且，排序的基本操作是向有序列R[1]～R[i-1]中插入一個R[i]。由于在有序序列中插入，我們當(dāng)然可以采用折半查找來確定R[i]在有序序列R[1]～R[i-1]中應(yīng)插入的位置，從而減少查找的次數(shù)。實現(xiàn)這種方法的排序稱為折半插入的排序。折半插入排序算法如下：

voidB_InsertSort(RecordTypeR[],intn)

{ //對n個記錄序列R[1]～R[n]進(jìn)行折半插入排序

inti,j,low,high,mid;

for(i=2;i<=n;i++) //進(jìn)行n-1趟排序

{

R[0]=R[i];//設(shè)置查找監(jiān)視哨并保存待插入記錄R[i]的值

low=1,high=i-1;

//設(shè)置初始查找區(qū)間

while(low<=high)

//尋找插入的位置

{

mid=(low+high)/2;

if(R[0].key>R[mid].key)

low=mid+1; //插入位置在右半?yún)^(qū)

else

high=mid-1; //插入位置在左半?yún)^(qū)

}

for(j=i-1;j>=high+1;j--)

//high+1為插入位置，將R[i-1],R[i-2],…,R[high+1]順序后移一個位置

R[j+1]=R[j];

R[high+1]=R[0];//將R[i](現(xiàn)為R[0])放入應(yīng)插入的位置high+1

}

}采用折半插入排序方法可以減少關(guān)鍵字的比較次數(shù)，因為每插入一個記錄需要比較的最大次數(shù)為具有i個結(jié)點(diǎn)(R[0]～R[i-1])的判定樹深度lbi，而外層for循環(huán)執(zhí)行n-1次，故關(guān)鍵字比較次數(shù)的時間復(fù)雜度為O(n?lbn)。而記錄移動的次數(shù)與直接插入排序相同，故時間復(fù)雜度仍為O(n2)。折半插入排序也是一個穩(wěn)定的排序方法。9.2.3希爾(Shell)排序

直接插入排序算法簡單并且有這樣兩個特點(diǎn)：

(1)在n值(待排記錄的個數(shù))較小的時候效率較高。

(2)在n值較大時，若待排序列中記錄按關(guān)鍵字基本有序則效率仍然較高，其時間效率可提高到O(n)。希爾排序又稱“縮小增量排序”，它是根據(jù)直接插入排序的這兩個特點(diǎn)而改進(jìn)的分組插入方法。也即，先將整個待排序列中的記錄按給定的下標(biāo)增量進(jìn)行分組，并對每個組內(nèi)的記錄采用直接插入法排序(由于初始時組內(nèi)記錄較少而排序效率高)，然后減少下標(biāo)增量，即使每組包含的記錄增多，再繼續(xù)對每組組內(nèi)的記錄采用直接插入法排序。依次類推，當(dāng)下標(biāo)增量減少到1時，整個待排序記錄序列已成為一組，但由于此前所做的直接插入排序工作，整個待排序記錄序列已經(jīng)基本有序，此時滿足直接插入排序方法的第(2)個特點(diǎn)。因此，對全體待排序記錄再進(jìn)行一次直接插入排序即完成排序工作且效率較高。圖9-2給出了希爾排序過程的示意圖，所取增量順序依次為d=5、d=3和d=1。圖9-2希爾排序過程示意圖希爾排序算法如下：

voidShellInsert(RecordTypeR[],intn,intd)//希爾排序

{//對R[1]～R[n]中的記錄進(jìn)行希爾排序，d為增量(步長)因子

inti,j;

for(i=d+1;i<=n;i++)

if(R[i].key<R[i-d].key)

{//當(dāng)R[i].key小于前一步長d的R[i-d].key應(yīng)向前尋找其插入的位置

R[0]=R[i];//暫存待插入記錄R[i]的值

for(j=i-d;j>0&&R[0].key<R[j].key;j=j-d)

R[j+d]=R[j];

/*將位于R[i]之前下標(biāo)差值為增量步長的倍數(shù)且關(guān)鍵字大于

R[0].key(即原R[i].key)的所有R[j]都順序后移一個增量步長位置*/

R[j+d]=R[0];//將原R[i]也即此時的R[0]插入到應(yīng)該插入的位置

}

}

voidShellSort(RecordTypeR[],intn)

{//按遞增序列d[0]、d[1]、…、d[t-1]對順序表R[1]～R[n]做希爾排序

intd[10],t,k;

printf(“\n輸入增量因子的個數(shù):\n”);

scanf(“%d”,&t);//輸入增量因子的個數(shù)

printf(“由大到小輸入每一個增量因子:\n”);

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

scanf(“%d”,&d[k]);

//由大到小輸入每一個增量因子

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

ShellInsert(R,n,d[k]);

//按增量因子d[k]對順序表R進(jìn)行一趟希爾排序

}注意，在算法ShellInsert中，實現(xiàn)希爾排序的次序稍微做了一點(diǎn)改動，即并不是先將同一增量步長的一組記錄全部排好后再進(jìn)行下一組記錄的排序，而是由R[d]開始依次掃描到R[n]為止，即對每一個掃描到的R[i]先與位于其前面的R[i-d]進(jìn)行關(guān)鍵字比較，如果R[i].key小于R[i-d].key，則將R[i]暫存與R[0]，然后執(zhí)行內(nèi)層的for循環(huán)。而內(nèi)層的for循環(huán)是完成將R[i].key(即現(xiàn)在的R[0].key)依次與相差一個增量步長d的R[i-d].key、R[i-2d].key……逐一進(jìn)行比較。若小于，則依次將R[i-d]、R[i-2d]……順序后移一個增量步長d的位置；若大于，則此時的j+d位置即為待插入記錄R[i](此時的R[0])的插入位置，這時通過語句“R[j+d]=R[0];”將待插記錄R[i]值放入這個位置。所以，針對圖9-2的初始序列，我們給出了按照ShellInsert算法的第一趟排序過程示意圖(如圖9-3所示)。由圖9-3可知，第一趟的排序結(jié)果完全與圖9-2中的第一趟結(jié)果相同。此外，由圖9-2排序前后48與48所處的位置可知，希爾排序是不穩(wěn)定的排序方法。

希爾排序仍是一種插入排序，其主要特點(diǎn)是每一趟以不同的增量進(jìn)行排序。增量序列可以有各種的取法，但應(yīng)使增量序列的值沒有除1之外的公因子，否則會出現(xiàn)多余的重復(fù)排序。此外，最后一個增量必須是1，否則可能有遺漏的記錄未參加排序而使最終結(jié)果達(dá)不到有序。

一般來說，希爾排序的速度比直接排序快，但希爾排序的效率分析很難，這是因為關(guān)鍵字的比較次數(shù)以及記錄的移動次數(shù)都要依賴于增量因子的選取。在有關(guān)著作里給出了希爾排序的平均比較次數(shù)和平均移動次數(shù)都為n1.3左右。圖9-3采用算法ShellInsert進(jìn)行希爾排序的示意圖 9.3交換排序

9.3.1冒泡排序

對R[1]～R[n]這n個記錄的冒泡排序排序過程是：第一趟從第1個記錄R[1]開始到第n個記錄R[n]為止，對n-1對相鄰的兩個記錄進(jìn)行兩兩比較，若與排序要求相逆，則交換兩者的位置，這樣，經(jīng)過一趟的比較、交換后，具有最大關(guān)鍵值的記錄就被交換到R[n]位置。第二趟從第1個記錄R[1]開始到n-1個記錄R[n-1]為止繼續(xù)重復(fù)上述的比較與交換，這樣，具有次大關(guān)鍵字的記錄就被交換到R[n-1]位置。如此重復(fù)，在經(jīng)過n-1趟這樣的比較和交換后，R[1]～R[n]這n個記錄已按關(guān)鍵字有序。這個排序過程就像一個個往上(往右)冒泡的氣泡，最輕的氣泡先冒上來(到達(dá)R[n]位置)，較重的氣泡后冒上來，因此形象的稱之為冒泡排序。

冒泡排序最多進(jìn)行n-1趟，在某趟的兩兩記錄關(guān)鍵字的比較過程中，如果一次交換都未發(fā)生，則表明R[1]～R[n]中的記錄已經(jīng)有序，這時可結(jié)束排序過程。

冒泡排序算法如下：

voidBubbleSort(RecordTypeR[],intn)

{ //對R[1]~R[n]這n個記錄進(jìn)行冒泡排序

inti,j,swap;

for(i=1;i<n;i++) //進(jìn)行n-1趟排序

{

swap=0; //設(shè)置未發(fā)生交換標(biāo)志

for(j=1;j<=n-i;j++) //對R[1]～R[n-i]記錄進(jìn)行兩兩比較

if(R[j].key>R[j+1].key)

{

//如果R[j].key大于R[j+1].key，則交換R[j]和R[j+1]

R[0]=R[j];

R[j]=R[j+1];

R[j+1]=R[0];

swap=1; //有交換發(fā)生

}

if(swap==0)

break; //本趟比較中未出現(xiàn)交換則結(jié)束排序(已排好)

}

}圖9-4冒泡排序過程示意圖上述冒泡排序算法是從左向右進(jìn)行冒泡排序的，即假定關(guān)鍵字越大，則氣泡越輕。當(dāng)然，也可參考此算法設(shè)計出從右往左的冒泡排序算法(見下面的雙向冒泡排序算法)。

從空間效率上看，冒泡排序僅用了一個輔助單元；從時間效率看，最好的情況是待排序序列已經(jīng)全部有序。這樣冒泡排序在第一趟排序過程中就沒有交換發(fā)生，所以一趟之后即排序結(jié)束。也即，只在第一趟中進(jìn)行了n-1次比較。最壞情況是待排序記錄按逆序排序，所以共需進(jìn)行n-1趟排序，且第i趟需進(jìn)行n-i次比較。所以：因此，冒泡排序的時間復(fù)雜度為O(n2)。交換記錄的次數(shù)與比較記錄的次數(shù)相同，最壞的情況也是發(fā)生在待排序記錄按逆序排列時。

由圖9-4可知，48與48在排序前后的先后次序沒有改變，故冒泡排序是一種穩(wěn)定的排序方法。由圖9-4我們還可以看出：最大關(guān)鍵字82一趟就移到了它最終放置的位置上，而最小關(guān)鍵字11每趟排序僅向前移動了一個位置。也即，如果具有n個記錄的待排序序列已基本有序，但是具有最小關(guān)鍵字的記錄位于序列最后，則采用冒泡排序也仍然需要進(jìn)行n-1趟排序。因此，我們可以采用雙向冒泡排序的方法來解決這一問題。雙向冒泡排序算法如下：

voidDBubbleSort(RecordTypeR[],intn)

{

inti,j,swap=1;

for(i=1;swap!=0;i++)

{

swap=0;

for(j=n-i;j>=i;j--)//從右到左進(jìn)行冒泡排序

if(R[j+1].key<R[j].key)

{

R[0]=R[j];

R[j]=R[j+1];

R[j+1]=R[0];

}

for(j=i+1;j<=n-i;j++)//從左到右進(jìn)行冒泡排序

if(R[j+1].key<R[j].key)

{

R[0]=R[j];

R[j]=R[j+1];

R[j+1]=R[0];

swap=1;//有交換發(fā)生

}

}

}9.3.2快速排序

快速排序是基于交換思想對冒泡排序的一種改進(jìn)的交換排序方法，又稱分區(qū)交換排序?？焖倥判虻幕舅枷胧牵涸诖判蛴涗浶蛄兄?，任取其中一個記錄(通常是第一個記錄)，并以該記錄的關(guān)鍵字作為基準(zhǔn)，經(jīng)過一趟交換之后，所有關(guān)鍵字比它小的記錄都交換到它的左邊，而所有關(guān)鍵字比它大的記錄都交換到它的右邊(注意只是交換而并不排序)，此時，該基準(zhǔn)記錄在有序序列中的最終位置就已確定。然后，再分別對劃分到基準(zhǔn)記錄左右兩部分區(qū)間的記錄序列重復(fù)上述過程，直到每一部分最終劃分為一個記錄時為止，即最終確定了所有記錄各自在有序序列中應(yīng)該放置的位置，這也意味著排序的完成。因此，快速排序的核心操作是劃分。快速排序算法如下：

intPartition(RecordTypeR[],inti,intj) //劃分算法

{//對R[i]～R[j]，以R[i]為基準(zhǔn)記錄進(jìn)行劃分，并返回R[i]在劃分后的正確位置

R[0]=R[i]; //暫存基準(zhǔn)記錄R[i]

while(i<j) //從表(即序列R[i]～R[j])的兩端交替向中間掃描

{

while(i<j&&R[j].key>=R[0].key)

//從右向左掃描查找第一個關(guān)鍵字小于R[0].key的記錄R[j]

j--;

if(i<j) //當(dāng)i<j時，則R[j].key小于R[0].key，將R[j]交換到表的左端

{

R[i]=R[j];

i++;

}

while(i<j&&R[i].key<=R[0].key)

//從左到右掃描查找第一個關(guān)鍵字大于R[0].key的記錄R[i]

i++;

if(i<j) //當(dāng)i<j時，則R[i].key大于R[0].key，將R[i]交換到表的右端

{

R[j]=R[i];

j--;

}

}

R[i]=R[0];//將基準(zhǔn)記錄R[0]送入最終(指排好序時)應(yīng)放置的位置

returni; //返回基準(zhǔn)記錄R[0]最終放置的位置

}

voidQuickSort(RecordTypeR[],ints,intt)

{

inti;

if(s<t)

{

i=Partition(R,s,t);

//i為基準(zhǔn)記錄的位置并由此將表分為R[s]～R[i-1]和R[i+1]～R[t]兩部分

QuickSort(R,s,i-1);//對表R[s]～R[i-1]進(jìn)行快速排序

QuickSort(R,i+1,t);//對表R[i+1]～R[t]進(jìn)行快速排序

}

}算法Partition完成在給定區(qū)間R[i]～R[j]中一趟快速排序的劃分。具體做法是：設(shè)置兩個搜索指針i和j來指向給定區(qū)間的頭一個記錄和最后一個記錄，并將頭一個記錄作為基準(zhǔn)記錄。首先從j指針開始自右向左搜索關(guān)鍵字比基準(zhǔn)記錄關(guān)鍵字小的記錄(即該記錄應(yīng)位于基準(zhǔn)記錄的左側(cè))，找到后將其交換到i指針處(此時已位于基準(zhǔn)記錄的左側(cè))；然后i指針右移一個位置并由此開始自左向右搜索關(guān)鍵字比基準(zhǔn)記錄關(guān)鍵字大的記錄(即該記錄應(yīng)位于基準(zhǔn)記錄的右側(cè))，找到后將其交換到j(luò)指針處(此時已位于基準(zhǔn)記錄的右側(cè))；接著j指針左移一個位置并繼續(xù)上述自右向左搜索、交換的過程。如此由兩端交替向中間搜索、交換，直到i與j相等，這表明位置i左側(cè)的記錄其關(guān)鍵字都比基準(zhǔn)記錄的關(guān)鍵字小，而j右側(cè)的記錄其關(guān)鍵字都比基準(zhǔn)記錄的關(guān)鍵字大，而i和j所指向的這同一個位置就是基準(zhǔn)記錄最終要放置的位置。在實際搜索中，為了減少數(shù)據(jù)的移動應(yīng)先將基準(zhǔn)記錄暫存于R[0]，待最后確定了基準(zhǔn)記錄的放置位置后，再將暫存于R[0]的基準(zhǔn)記錄放置于此。圖9-5給出了快速排序一趟劃分的示意圖，方框表示基準(zhǔn)記錄的關(guān)鍵字，它只是示意應(yīng)交換的位置，實際中，只有當(dāng)一趟劃分完成時才真正將基準(zhǔn)記錄放入最終確定的位置。圖9-5一趟快速排序示意圖圖9-6用二叉樹描述圖9-5快速排序遞歸調(diào)用的劃分示意圖從空間效率看：快速排序是遞歸的，每層遞歸調(diào)用時的指針和參數(shù)都要用棧來存放。由于遞歸調(diào)用的層數(shù)與上述二叉樹示意的深度一致，因此存儲開銷在理想的情況下為O(lbn)；在最壞情況下，即二叉樹是一個單支樹時空間復(fù)雜度為O(n)。

從時間效率看：對于n個記錄的待排序序列，一次劃分需要約n次關(guān)鍵字的比較，時間效率為O(n)。若設(shè)T(n)為對n個記錄進(jìn)行快速排序所需的時間，則理想情況下每次劃分正好將n個記錄分為等長的子序列，并且每次劃分所需的比較次數(shù)為n-1；則：

T(n)≤n+2T(n/2)

≤n+2(n/2+2T(n/4))=2n+4T(n/4)

≤2n+4(n/4+T(n/8))=3n+8T(n/8)

…………

≤nlbn+nT(1)=O(nlbn)在最壞情況下，每次劃分只得到一個子序列，即時間復(fù)雜度變?yōu)镺(n2)。

快速排序被認(rèn)為是在所有同數(shù)量級(O(nlbn))的排序算法中平均性能最好。但是如果初始記錄序列按關(guān)鍵字有序或基本有序時，快速排序?qū)⑼嘶癁槊芭菖判?，即此時的時間復(fù)雜度上升到O(n2)。因此，通常以“三者取中法”來選取基準(zhǔn)記錄，即將排序區(qū)間的兩端和中間這三個位置上的記錄找其關(guān)鍵字居中的這個記錄作為基準(zhǔn)記錄。此外，由圖9-5看出在排序之前48位于48之后，而一趟排序之后48已位于48之前(但圖9-5待排序列最終結(jié)果48仍在48之后，讀者可以另選一序列5,5,2來驗證其不穩(wěn)定性)。因此，快速排序是一個不穩(wěn)定的排序方法。 9.4選擇排序

9.4.1直接選擇排序

直接選擇排序又稱簡單選擇排序，其實現(xiàn)方法是：第一趟從n個無序記錄中找出關(guān)鍵字最小的記錄與第1個記錄交換(此時第1個記錄為有序)；第二趟從第2個記錄開始的n-1個無序記錄中再選出關(guān)鍵字最小的記錄與第2個記錄交換(此時第1和第2個記錄為有序)……如此下去，第i趟則從第i個記錄開始的n-i+1個無序記錄中選出關(guān)鍵字最小的記錄與第i個記錄交換(此時前i個記錄已有序)，這樣n-1趟后前n-1個記錄已有序，無序記錄只剩一個即第n個記錄，因關(guān)鍵字小的前n-1個記錄已進(jìn)入有序序列，這第n個記錄必為關(guān)鍵字最大的記錄，所以無需交換即n個記錄已全部有序。

直接選擇排序算法如下：

voidSelectSort(RecordTypeR[],intn)

{ //對R[1]～R[n]這n個記錄進(jìn)行選擇排序

inti,j,k;

for(i=1;i<n;i++) //進(jìn)行n-1趟選擇

{

k=i; //假設(shè)關(guān)鍵字最小的記錄為第i個記錄

for(j=i+1;j<=n;j++)

//從第i個記錄開始的n-i+1個無序記錄中選出關(guān)鍵字最小的記錄

if(R[j].key<R[k].key)

k=j; //保存最小關(guān)鍵字記錄的存放位置

if(i!=k) //將找到關(guān)鍵字最小的記錄與第i個記錄交換

{

R[0]=R[k];

R[k]=R[i];

R[i]=R[0];

}

}

}

算法中，R[1]～R[i-1]是有序表；R[i]～R[n]是無序表；i始終指向無序表第一個元素的位置。初始時，i值為1，即有序表為空，而R[1]～R[n]為無序表。內(nèi)層for循環(huán)完成在無序表中找出其中關(guān)鍵字最小的記錄，外層for循環(huán)則通過if語句將這個關(guān)鍵字最小的記錄與無序表的第一個記錄(即R[i])進(jìn)行交換。此時，有序表變?yōu)镽[1]～R[i]，無序表變?yōu)镽[i+1]～R[n]，而外層for循環(huán)的“i++”則使i指向縮小后的無序表新的第一個記錄位置。上述操作共執(zhí)行n-1趟，直到無序表僅剩一個記錄R[n]時為止(R[n]此時已是關(guān)鍵字最大的記錄，故無需交換)，則n個記錄已全部有序。圖9-7直接選擇排序過程示意圖采用直接選擇排序，其記錄的比較次序與記錄的初始排列無關(guān)。在第i趟選擇排序中，內(nèi)層for循環(huán)進(jìn)行了n-(i+1)+1=n-i次比較，即：因此直接選擇排序的時間復(fù)雜度為O(n2)。直接選擇排序移動記錄的次數(shù)較少，最好情況是n個記錄初始即為有序，即移動次數(shù)為0；最壞情況是初始的n個記錄為逆序排列，即每一趟均要執(zhí)行交換操作，所以總的移動次數(shù)為3(n-1)。由圖9-7可知，直接選擇排序是一種不穩(wěn)定的排序方法。9.4.2堆排序

對n個關(guān)鍵字序列k1，k2，k3，…，kn，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時就稱為堆。 k2i

k2iki≤

或者ki≥

其中，i=1,2,…

, k2i+1

k2i+1

若將此序列對應(yīng)的一維數(shù)組(即以一維數(shù)組作為此序列的存儲結(jié)構(gòu))看成一棵完全二叉樹，則堆的含義表明：完全二叉樹中所有非終端結(jié)點(diǎn)(非樹葉結(jié)點(diǎn))的關(guān)鍵字均不大于(或不小于)其左、右孩子結(jié)點(diǎn)的關(guān)鍵字。因此在一個堆中，堆頂關(guān)鍵字(即完全二叉樹的根結(jié)點(diǎn))必是n個關(guān)鍵字序列中的最小值(或最大值)，并且堆中任意一棵子樹也同樣是堆。我們將堆頂關(guān)鍵字為最小值的堆稱為小根堆，將堆頂關(guān)鍵字為最大值的堆稱為大根堆。如序列：12，36，24，85，47，30，53，91是一個小根堆，而序列：91，47，85，24，36，53，30，16則是一個大根堆。這兩個堆的完全二叉樹表示和一維數(shù)組存儲表示如圖9-8所示。圖9-8堆及其存儲示意圖堆排序是一種樹形選擇排序，更確切地說是二叉樹形選擇排序。我們以小根堆為例，則堆排序的思想是：對n個待排序的記錄，首先根據(jù)各記錄的關(guān)鍵字按堆的定義排成一個序列(即建立初始堆)，從而由堆頂?shù)玫阶钚￡P(guān)鍵字的記錄，然后將剩余的n-1個記錄再調(diào)整成一個新堆，即又由堆頂?shù)玫竭@n-1個記錄中最小關(guān)鍵字的記錄，如此反復(fù)進(jìn)行出堆和將剩余記錄調(diào)整為堆的過程，當(dāng)堆僅剩下一個記錄出堆時，則n個記錄已按出堆次序排成有序序列。因此，堆排序的過程分為兩步(以小根堆為例，大根堆可類似處理)：

(2)調(diào)整成新堆。

堆頂結(jié)點(diǎn)的關(guān)鍵字輸出后，如何將堆中剩余的n-1個結(jié)點(diǎn)調(diào)整為堆？首先，將堆中序號為n的最后一個結(jié)點(diǎn)與待出堆的序號為1的堆頂結(jié)點(diǎn)(即完全二叉樹的根結(jié)點(diǎn))交換(序號為n的結(jié)點(diǎn)此時用來保存出堆的結(jié)點(diǎn))，這時只需要使序號從1～n-1的結(jié)點(diǎn)滿足堆的定義，即可將由這剩余的n-1個結(jié)點(diǎn)構(gòu)成堆。相對于原來的堆，此時僅堆頂結(jié)點(diǎn)發(fā)生了改變，而其余n-2個結(jié)點(diǎn)的存放位置仍是原來堆中的位置，即這n-2個結(jié)點(diǎn)仍滿足堆的定義，我們只需對這個新的堆頂結(jié)點(diǎn)(顯然不滿足堆的定義)進(jìn)行調(diào)整。也就是說，在完全二叉樹中，只對根結(jié)點(diǎn)進(jìn)行自上而下的調(diào)整。調(diào)整的方法是：將根結(jié)點(diǎn)與左、右孩子結(jié)點(diǎn)中關(guān)鍵字值較小的那個結(jié)點(diǎn)進(jìn)行交換(否則交換后仍不滿足堆的定義)，若與左孩子進(jìn)行交換，則左子樹堆被破壞，且僅左子樹的根結(jié)點(diǎn)不滿足堆的定義；若與右子樹交換，則右子樹的堆被破壞，且僅右子樹的根結(jié)點(diǎn)不滿足堆的定義。繼續(xù)對不滿足堆的定義的子樹進(jìn)行上述交換操作，這種調(diào)整需持續(xù)到葉結(jié)點(diǎn)或者到某結(jié)點(diǎn)已滿足堆的定義為止。堆排序的過程是：對n個關(guān)鍵字序列先將其建成堆(初始堆)，然后執(zhí)行n-1趟堆排序。第一趟先將序號為1的根結(jié)點(diǎn)與序號為n的結(jié)點(diǎn)交換(此時第n個結(jié)點(diǎn)用于存儲出堆結(jié)點(diǎn))，并調(diào)整此時的前n-1個結(jié)點(diǎn)為堆；第二趟先將序號為1的根結(jié)點(diǎn)與序號為n-1的結(jié)點(diǎn)交換(此時第n-1個結(jié)點(diǎn)用于存儲出堆結(jié)點(diǎn))，并調(diào)整此時的前n-2個結(jié)點(diǎn)為堆……第n-1趟將序號為1的根結(jié)點(diǎn)與序號為2的根結(jié)點(diǎn)交換(此時第2個結(jié)點(diǎn)用于存儲出堆結(jié)點(diǎn))。由于此時的待調(diào)整的堆僅為序號為1根結(jié)點(diǎn)故無需調(diào)整，整個堆排序過程結(jié)束。至此，在一維數(shù)組中的關(guān)鍵字已全部有序，但為逆序排列，故需要按升序排序，則建大根堆；需要按降序排列則建小根堆。

以關(guān)鍵字42,33,25,81,72,11為例，通過圖9-9和圖9-10給出堆排序示意圖。圖9-9初始堆建立過程示意圖圖9-10將圖9-9的堆調(diào)整為新堆及堆排序過程為了最終得到一個升序的關(guān)鍵字序列，我們采用大根堆方式，即每次調(diào)整都是與關(guān)鍵字大的孩子結(jié)點(diǎn)進(jìn)行調(diào)整?；诖蟾训亩雅判蛩惴ㄈ缦拢?/p>

voidHeapAdjust(RecordTypeR[],ints,intt) //基于大根堆的堆排序

{/*對R[s]～R[t]除R[s]外均滿足堆的定義，即只對R[s]進(jìn)行調(diào)整使R[s]為根的完全二叉樹成為一個堆*/

inti,j;

R[0]=R[s]; //R[s]暫存于R[0]

i=s;

for(j=2*i;j<=t;j=2*j) //沿關(guān)鍵字較大的孩子向下調(diào)整，先假定為左孩子

{

if(j<t&&R[j].key<R[j+1].key)

j=j+1;//右孩子結(jié)點(diǎn)的關(guān)鍵字大，則沿右孩子向下調(diào)整

if(R[0].key>R[j].key)/*R[0](即R[s])的關(guān)鍵字已大于R[j]的關(guān)鍵字值，即已滿足堆的定義，故不再向下調(diào)整)*/

break;

R[i]=R[j];//將關(guān)鍵字大的孩子結(jié)點(diǎn)R[j]調(diào)整至雙親結(jié)點(diǎn)R[i]

i=j;//定位于孩子結(jié)點(diǎn)繼續(xù)向下調(diào)整

}

R[i]=R[0];

//找到滿足堆定義的R[0](即R[s])放置位置i，將R[s]調(diào)整于此

}

voidHeapSort(RecordTypeR[],intn)

{

inti; //對R[1～]R[n]這n個記錄進(jìn)行堆排序

for(i=n/2;i>0;i--) /*將完全二叉樹非終端結(jié)點(diǎn)按

R[n/2],R[n/2-1],…,R[1]的順序建立初始堆*/

HeapAdjust(R,i,n);

for(i=n;i>1;i--) //對初始堆進(jìn)行n-1趟堆排序

{

R[0]=R[1]; //堆頂?shù)腞[1]與堆底的R[i]交換

R[1]=R[i];

R[i]=R[0];

HeapAdjust(R,1,i-1); //將未排序的前i-1個結(jié)點(diǎn)重新調(diào)整為堆

}

} 9.5歸并排序

前面介紹的插入排序、交換排序和選擇排序這三類排序方法都是將無序的記錄序列按關(guān)鍵字的大小排成一個有序序列。而歸并排序則是將兩個或兩個以上的有序序列合并成一個有序序列的過程。將兩個有序序列合并(歸并)成一個有序序列稱為二路歸并排序；將n個有序序列歸并成一個有序序列稱為n路歸并排序。在此，以二路歸并為例來討論歸并排序，因為二路歸并最為簡單和常用。二路歸并的思想是：只有一個記錄的表總是有序的，故初始時將n個待排序記錄看成是n個有序表(每個有序表的長度為1，即僅有一個記錄)，然后開始第1趟兩路歸并，即將第1個表同第2個表歸并，第3個表同第4個表歸并……若最后僅剩一個表，則不參加歸并。這樣得到的個長度為2(最后一個表的長度可能為1)的有序表。然后進(jìn)行第2趟歸并，即將第1趟得到的有序表繼續(xù)進(jìn)行兩兩歸并，從而得到個長度為4(最后一個表的長度可能小于4)的有序表。依此類推，直到第趟歸并，就得到了長度為n的有序表。因此，可以將長度為n的無序表對半分成兩個無序子表，并對每一個無序子表繼續(xù)進(jìn)行對半拆分為兩個子表的工作，直到每個子表的長度為1，這樣就形成了長度為1的有序子表(表長為1時為有序表)，然后從第一個子表開始對相鄰子表進(jìn)行兩兩合并的工作，即將兩個有序子表合并為一個有序子表。這種兩兩合并的工作一直持續(xù)到合并為一個長度為n的有序表時為止。而兩兩合并的過程恰是前面將一個子表不斷對分為兩個子表工作的逆過程，因此拆分與合并工作均可以在一個遞歸函數(shù)里完成，即在遞歸的逐層調(diào)用中完成將一個子表拆分成兩個子表的工作，而在遞歸的逐層返回中完成將兩個有序子表合并成一個有序子表的工作。二路歸并遞歸算法如下：

voidMerge(RecordTypeR[],RecordTypeR1[],ints,intm,intt)//一趟二路歸并

{//將有序表R[s]～R[m]及R[m+1]～R[t]合并為一個有序表R1[s]～R1[t]

inti,j,k;

i=s;

j=m+1;

k=s;

while(i<=m&&j<=t)

//將兩個有序表的記錄按關(guān)鍵字大小收集到表R1中使表R1也為有序表

if(R[i].key<=R[j].key)

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

else

R1[k++]=R[j++];

while(i<=m)//將第一個有序表未收集完的記錄收集到有序表R1中

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

while(j<=t)//將第二個有序表未收集完的記錄收集到有序表R1中

R1[k++]=R[j++];

}

voidMSort(RecordTypeR[],RecordTypeR1[],ints,intt)//遞歸方式的歸并排序

{//將無序表R[s]～R[t]歸并為一個有序表R1[s]～R1[t]

intm;

RecordTypeR2[MAXSIZE];

if(s==t)

R1[s]=R[s];

else

{

m=(s+t)/2; //找到無序表R[s]～R[t]的中間位置

MSort(R,R2,s,m);

//遞歸地將無序表的前半個表R[s]～R[m]歸并為有序表R2[s]～R2[m]

MSort(R,R2,m+1,t);

//遞歸地將無序表后半個表R[m+1]～R[t]歸并為有序表R2[m+1]～R2[t]

Merge(R2,R1,s,m,t); /*進(jìn)行一趟將有序表R2[s]～R2[m]和R2[m+1]～R2[t]

歸并到有序表R1[s]～R1[t]的操作*/

}

}若將一個存于一維數(shù)組R[1]～R[n]中的記錄排成有序序列，則可用下面的語句調(diào)用二路歸并的遞歸算法實現(xiàn)：MSort(R,R1,1,n);其中，R和R1分別為RecordType類型長度為n+1的一維數(shù)組，而n為已知常數(shù)。二路歸并排序遞歸算法實現(xiàn)的過程是：像一棵二叉樹一樣，首先將無序表R[1]～R[n]通過函數(shù)MSort中的兩條MSort語句對半分為第二層的兩個部分。由于是遞歸調(diào)用，在沒有執(zhí)行將兩個有序子表歸并為一個有序子表的函數(shù)調(diào)用語句Merge之前，又遞歸調(diào)用MSort函數(shù)再次將第二層的每一部分繼續(xù)對半拆分。依此類推，這種遞歸調(diào)用拆分的過程持續(xù)到每一部分只有一個記錄時為止，然后逐層返回執(zhí)行每一層還未執(zhí)行的Merge函數(shù)調(diào)用語句，而該語句則是將兩個部分合二為一，并且在合并(歸并)中使其成為有序表(每一部分只有一個記錄時即為有序，因此是將兩個有序表合并為一個有序表的過程)。由于每一次將一個表對半分為兩個子表操作的語句(即兩個MSort函數(shù)調(diào)用語句)其后面都有一個將兩個有序子表合并為一個有序子表的語句(即Merge函數(shù)調(diào)用語句)，因此將兩個表合二為一的歸并恰好與前面的一分為二對應(yīng)，也即最終正好歸并為一個長度為n的有序表。圖9-11二路歸并排序遞歸調(diào)用中對半拆分的示意圖在二路歸并排序的遞歸過程中，當(dāng)一分為二到一個記錄(可看成葉結(jié)點(diǎn))時，一分為二過程結(jié)束，而合二為一的排序過程開始，故合二為一的過程則由葉結(jié)點(diǎn)開始逐層返回并進(jìn)行兩兩歸并，一直持續(xù)到根結(jié)點(diǎn)為止，即最終歸并為一個有n個記錄的有序表。這個合二為一的過程恰好是前面一分為二的逆過程。圖9-12給出了二路歸并排序遞歸過程中合二為一的示意圖，方括號“[]”表示其間的記錄是一個有序表。圖9-12二路歸并示意圖二路歸并算法的遞歸形式看起來簡單，但因遞歸形式開銷較大而適用性較差，所以最好采用非遞歸算法。下面我們介紹二路歸并的非遞歸算法。

二路歸并的非遞歸算法仍然采用二路歸并的基本思想：即將n個記錄的無序表R[1]～R[n]看做是n個表長為1的有序子表，然后對相鄰的兩個有序子表兩兩合并到表R1[1]～R1[n]中。當(dāng)一趟歸并結(jié)束后，有序子表的長度k是原子表長度的2倍。接下來開始第二趟對相鄰兩個有序子表的兩兩歸并，這種歸并一直持續(xù)到有序子表的長度k不小于表長n為止則歸并排序結(jié)束。因為表長未必是2的整數(shù)冪，所以最后一個子表的長度并不能保證恰好為k，也不能保證每趟歸并時都有偶數(shù)個有序子表，這些都要在一趟排序中予以考慮。針對這些情況的處理原則是：

(1)若最后一次歸并的第二個子表長度不足一個子表的長度k時，則置第二個子表的長度為n-1。

(2)若最后一次歸并已不足一個子表時，只需將這子表中的記錄依次復(fù)制到暫存數(shù)組R1即可。二路歸并的非遞歸算法如下：

voidMerge(RecordTypeR[],RecordTypeR1[],intk,intn)//一趟二路歸并

{ //R1為歸并中使用的暫存數(shù)組

inti,j,l1,u1,l2,u2,m;

//l1、l2和u1、u2分別為進(jìn)行歸并的兩個有序子表的上、下界

l1=0; //初始時l1為第一個有序子表的下界值0

m=0; //m為數(shù)組R1的存放指針

while(l1+k<n) //歸并中的兩個子表其第一個子表長度為k時

{

l2=l1+k; //l2指向歸并中第二個子表的開始處

u1=l2-1; //u1指向歸并中第一個子表的末端(與第二個子表相鄰)

if(l2+k-1<n)

u2=l2+k-1; //u2指向歸并中第二個子表的末端

else

u2=n-1; //歸并中第二個子表為最后一個子表且長度小于k

for(i=l1,j=l2;i<=u1&&j<=u2;m++)

//兩個有序子表歸并為一個有序子表且暫存于R1

if(R[i].key<=R[j].key)

R1[m]=R[i++];

else

R1[m]=R[j++];

while(i<=u1) //第二個子表已歸并完，將第一個子表的剩余記錄復(fù)制到R1中

R1[m++]=R[i++];

while(j<=u2) //第一個子表已歸并完，將第二個子表的剩余記錄復(fù)制到R1中

R1[m++]=R[j++];

l1=u2+1; //將l1調(diào)整到下兩個未歸并子表的開始處繼續(xù)進(jìn)行歸并

}

for(i=l1;i<n;i++,m++)//歸并到僅剩一個子表且長度又小于k時

R1[i]=R[i]; //直接復(fù)制該子表中的記錄到R1中

}

voidMergeSort(RecordTypeR[],intn)

//非遞歸方式的歸并排序

{//將無序表R[s]～R[t]歸并為一個有序表R1[s]～R1[t]

inti,k;

RecordTypeR1[MAXSIZE];

k=1;//初始時待歸并的有序子表長度均為1

while(k<n)//整個表未歸并為一個有序表時(子表長度k小于n)繼續(xù)歸并

{

Merge(R,R1,k,n); //對所有子表進(jìn)行一趟二路歸并

for(i=0;i<n;i++)

//將暫存于R1的一趟歸并結(jié)果復(fù)制到R中

R[i]=R1[i];

k=2*k; //一趟歸并后有序子表長度是原子表長度的2倍

}

}二路歸并排序的非遞歸算法由于需要與表(數(shù)組)R等長的輔助空間R1，所以空間復(fù)雜度為O(n)。但是，二路歸并排序的遞歸算法由于在函數(shù)MSort中定義了一個長度為n的局部數(shù)組R2，即遞歸調(diào)用MSort的次數(shù)約為一個滿二叉樹的結(jié)點(diǎn)個數(shù)(表R的長度n，相當(dāng)于n個葉子結(jié)點(diǎn)，即滿二叉樹約有2n-1個結(jié)點(diǎn))且每次調(diào)用MSort都產(chǎn)生一個長度為n的數(shù)組R2。也即，二路歸并排序的遞歸算法所用的輔助空間約為n×(2n-1)，因此空間復(fù)雜度為O(n2)。注意，這一點(diǎn)與其他數(shù)據(jù)結(jié)構(gòu)教材講述的不同，其他教材認(rèn)為二路歸并排序遞歸算法的空間復(fù)雜度仍為O(n)，有些數(shù)據(jù)結(jié)構(gòu)的教材在二路歸并排序遞歸算法中并不使用局部數(shù)組，但用C語言編程不采用局部數(shù)組就無法實現(xiàn)二路歸并排序。對n個記錄的表，將這n個記錄看做是葉結(jié)點(diǎn)，并將兩兩歸并生成的子表看做它們的父結(jié)點(diǎn)，則歸并過程是一個由葉結(jié)點(diǎn)向上生成一棵二叉樹直至到根結(jié)點(diǎn)的過程。所以歸并趟數(shù)約等于二叉樹的高度減1，即。每趟歸并需移動記錄n次，故時間復(fù)雜度為O(nlbn)。

歸并排序是一種穩(wěn)定的排序方法。

9.6基數(shù)排序

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

前面討論的排序中每個記錄都只有一個關(guān)鍵字，而在有些情況下，排序過程中會用到一個記錄里的多個關(guān)鍵字，這種排序稱為多關(guān)鍵字排序。

我們以撲克牌的排序來說明多關(guān)鍵字排序。根據(jù)撲克牌的花色和面值這兩個屬性，可以將一副撲克牌的排序看做是對其花色和面值這兩種關(guān)鍵字進(jìn)行排序的問題。當(dāng)然，要判斷兩張撲克牌的大小，就要對兩張牌的這兩個關(guān)鍵字組合進(jìn)行判斷。通常的判斷方法是：先比較兩張牌的花色，花色大的一張牌為大；如果花色相同則面值大的一張牌為大。例如，我們規(guī)定花色和面值由小到大的順序為①花色：黑桃＜梅花＜方塊＜紅心；

②面值：2＜3＜…＜10＜J＜Q＜K＜A。

根據(jù)上述定義關(guān)鍵字的大小就可以決定兩張撲克牌的大小，如：方塊8＜紅心2，紅心2＜紅心6等?；ㄉ侵麝P(guān)鍵字，面值是次關(guān)鍵字，只有花色相同時比較面值才有意義。

根據(jù)對關(guān)鍵字選擇順序的不同，可以有兩種排序方法。第一種方法采用如下四個步驟：

(1)按面值的不同給出13個編號桶(2號，3號，…，k號，A號)，并根據(jù)面值的不同將所有牌分配到這13個編號桶中，即每個桶包含4種不同的花色但面值相同的牌，這一過程稱之為分配。

(2)按2號，3號，…，k號，A號的次序收集13個桶中的牌(收集后已按面值升序排列)，這一過程稱之為收集。

(3)按花值不同給出4個編號桶(黑桃，梅花，方塊，紅心)，并將剛收集的牌按花色依次分配到這4個桶中。注意，排在開頭的面值為2的牌先放入桶(在桶的下面)，排在最后面的面值為A的牌最后入桶(在桶上面)，此時每個桶已按面值由小到大的次序放入了同一花色的13張牌。這一過程又稱之為分配。

(4)按紅心、方塊、梅花、黑桃的次序收集4個桶中的牌就完成了對撲克牌的排序過程(該過程仍稱之為收集)。因為按紅心、方塊、梅花、黑桃的次序收集，則牌的花色將是黑桃在前而紅心在最后(排列為收集次序的逆序)，而每個桶是先取出A、最后取出2，即2排列在前面而A排列在最后，故最終收集的排列順序為

黑桃2,…,黑桃A,梅花2,…,梅花A,方塊2,…,方塊A,紅心2,…,紅心A

這正是我們所要求的升序排列，這一種方法也被稱為最次位優(yōu)先法。與上述方法相反的排序方法是第二種最主位優(yōu)先法：即先按花色分配到4個桶中，然后再收集，將收集的牌再次分配到按面值不同的13個桶中，最后收集這13個桶中的牌則可完成排序。即最終收集的排列順序為

黑桃2,梅花2,方塊2,紅心2,黑桃3,梅花3,…,黑桃A,梅花A,方塊A,紅心A

假定在n個記錄的排序表中，每個記錄包含d個關(guān)鍵字{k1,k2,k3,…,kd}，則稱記錄序列對關(guān)鍵字{k1,k2,k3,…,kd}有序，即對于記錄序列中的任意兩個記錄R[i]和R[j](1≤i＜j≤n)都滿足下列有序關(guān)系：多關(guān)鍵字排序按照從最次位關(guān)鍵字到最主位關(guān)鍵字，或從最主位關(guān)鍵字到最次位關(guān)鍵字的順序逐次排序，即分為如下兩種方法：

(1)最次位優(yōu)先(LSD)法：先從最次位關(guān)鍵字kd開始分組，同一組中記錄其關(guān)鍵字kd相等，然后將各組連接(收集)起來，再按kd-1進(jìn)行分組和收集。此后，對后面的關(guān)鍵字繼續(xù)這樣的分組和收集，直到按最主位關(guān)鍵字k1進(jìn)行分組和收集后便得到一個有序序列。撲克牌按面值﹑花色的第一種排序方法即為LSD法。

(2)最主位優(yōu)先(MSD)法：先按k1進(jìn)行分組和收集，再按k2進(jìn)行分組和收集，直到按最次關(guān)鍵字kd1進(jìn)行分組和收集后便得到一個有序序列。撲克牌按花色、面值的第二種排序方法即為MSD法。

如果排序的結(jié)果要求以最主位關(guān)鍵字為主關(guān)鍵字，則采用最次位優(yōu)先法(如撲克牌的第一種排序)；如果排序的結(jié)果要求以最次位關(guān)鍵字為主關(guān)鍵字，則采用最主位優(yōu)先法(如撲克牌的第二種排序)。9.6.2鏈?zhǔn)交鶖?shù)排序

如果將關(guān)鍵字拆分為若干項，每項作為一個“關(guān)鍵字”，則對單關(guān)鍵字的排序可按多關(guān)鍵字排序方法進(jìn)行。比如關(guān)鍵字為3位的整數(shù)，可以每位對應(yīng)一項拆分為3個關(guān)鍵字；又如關(guān)鍵字由5個字符組成的字符串，可以將每個字符對應(yīng)一項拆分為5個關(guān)鍵字。這樣拆分后，每個關(guān)鍵字都在相同的權(quán)值范圍內(nèi)(對數(shù)字是0～9，對字符則是'a'～'z')，我們稱這樣的關(guān)鍵字可能出現(xiàn)的權(quán)值范圍為“基”并記作r。上述取數(shù)字為關(guān)鍵字的“基”為10，取字符為關(guān)鍵字的“基”為26。根據(jù)這一特性，采用LSD法排序較為方便?；鶖?shù)排序的思想是：根據(jù)基r的大小設(shè)立r個隊列，隊列的編號分別為0、1、2、…、r-1。對于無序的n個記錄，首先從最低位關(guān)鍵字開始，將這n個記錄“分配”到r個隊列中，然后由小到大將各隊列中的記錄再依次“收集”起來，這稱為一趟排序。第一趟排序后，n個記錄已按最低位關(guān)鍵字有序。然后再按次最低關(guān)鍵字把剛收集起來的n個記錄再“分配”到r個隊列中，重復(fù)上述“分配”與“收集”過程，直到對最高位關(guān)鍵字再進(jìn)行一趟“分配”和“收集”后，則n個記錄已按關(guān)鍵字有序。為了減少記錄移動的次數(shù)，基數(shù)排序中的隊列可以采用鏈表作為存儲結(jié)構(gòu)，并用r個鏈隊列作為分配隊列，鏈隊列設(shè)有兩個指針，分別指向鏈隊列的隊頭和隊尾。關(guān)鍵字相同的記錄放入到同一個鏈隊列中，而收集則總是將各鏈隊列按關(guān)鍵字大小順序鏈接起來。這種結(jié)構(gòu)下的排序稱為鏈?zhǔn)交鶖?shù)排序。用靜態(tài)鏈表(即一維數(shù)組)存放待排序的n個記錄，則基數(shù)排序算法如下：

typedefstruct

{

intkey; //單關(guān)鍵字

intkeys[d_MAX]; //存放拆分后的各關(guān)鍵字項，d_MAX為關(guān)鍵字項的最大長度值

intnext; //指向下一記錄的指針

chardata;

}RecType;

voidRadixSort(RecTypeR[],intd,intc1,intct)

{//對R[1]～R[n]進(jìn)行基數(shù)排序，d為關(guān)鍵字項數(shù)，c1～ct為基數(shù)(即權(quán)值)的范圍

inti,j,k,m,p,t,f[Radix_MAX],e[Radix_MAX];//Radix_MAX為基數(shù)的最大長度值

p=1; //由R[1]開始

for(i=0;i<d;i++) //進(jìn)行d趟分配與收集

{

for(j=c1;j<=ct;j++) //分配前清空隊頭指針

f[j]=0;

while(p!=0)//未分配到最后一個記錄R[n]，其標(biāo)記為R[n].next等于0

{

k=R[p].keys[i]; //k為R[p]中第i項關(guān)鍵字值

if(f[k]==0) //第k個隊列是否為空

f[k]=p; //R[p]作為第k個隊列的隊頭結(jié)點(diǎn)插入

else

R[e[k]].next=p; //將R[p]鏈到第k個隊列的隊尾結(jié)點(diǎn)

e[k]=p; //第k個隊列的隊尾指針e[k]指向新的隊尾結(jié)點(diǎn)

p=R[p].next;//取出排在R[p]之后的記錄繼續(xù)分配

}

j=c1; //收集c1～ct個隊列上的記錄

while(f[j]==0) //j隊列為空時繼續(xù)查找下一個非空隊列

j++;

p=f[j];t=e[j]; //找到第一個非空隊列使p指向隊頭，t指向隊尾

while(j<ct) //未收集完最后一個隊列時則繼續(xù)收集

{

j++; //使j指向后一個隊列

if(f[j]!=0) //后一個隊列不為空時

{

R[t].next=f[j];//將后一個隊列的隊頭鏈到前一個隊列的隊尾

t=e[j];

//使t指向這后一個隊列的隊尾繼續(xù)進(jìn)行對下一個隊列的收集

}

R[t].next=0;

//收集完畢置最后一個記錄R[t]為收集隊列的隊尾標(biāo)志

}

m=p; //以下輸出本趟收集的鏈隊列記錄

printf("%5d",R[m].key);

do

{

m=R[m].next;

printf("%5d",R[m].key);

}while(R[m].next!=0);

printf("\n");

}

}

voidDistKeys(RecTypeR[],intn,intd,intc1,intct)

{

inti,j,k;

for(i=1;i<=n;i++)

{

R[i].next=i+1; //將記錄R[1]～R[n]先鏈成一個鏈隊列

k=R[i].key; //取出R[i]的單關(guān)鍵字

for(j=0;j<d;j++)

{

R[i].keys[j]=k%(ct+1); /*將R[i]的單關(guān)鍵字key分離為多關(guān)鍵字

存于R[i].keys[0]～R[i].keys[d]*/

k=k/(ct+1);

}

}

R[n].next=0;//置最后一個記錄