2023學(xué)年完整公開(kāi)課版排序

第8章排序8.1概述8.2插入排序8.3交換排序8.4選擇排序8.5歸并排序8.6基數(shù)排序8.7各種內(nèi)部排序方法比較1.直接插入排序2.折半插入排序3.希爾排序1.冒泡排序2.快速排序1.簡(jiǎn)單選擇排序2.樹(shù)型選擇排序3.堆排序8.1概述排序：有n個(gè)記錄的序列{R1，R2，…，Rn}，其相應(yīng)關(guān)鍵字的序列是{K1，K2，…，Kn}，相應(yīng)的下標(biāo)序列為1，2，…，n。通過(guò)排序，要求找出當(dāng)前下標(biāo)序列1，2，…，n的一種排列p1，p2，…，pn，使得相應(yīng)關(guān)鍵字滿足如下的非遞減（或非遞增）關(guān)系，即：Kp1≤Kp2≤…≤Kpn，這樣就得到一個(gè)按關(guān)鍵字有序的記錄序列：{Rp1，Rp2，…，Rpn}。內(nèi)部排序與外部排序：根據(jù)排序時(shí)數(shù)據(jù)所占用存儲(chǔ)器的不同，可將排序分為兩類。一類是整個(gè)排序過(guò)程完全在內(nèi)存中進(jìn)行，稱為內(nèi)部排序；另一類是由于待排序記錄數(shù)據(jù)量太大，內(nèi)存無(wú)法容納全部數(shù)據(jù)，排序需要借助外部存儲(chǔ)設(shè)備才能完成，成為外部排序。穩(wěn)定排序與不穩(wěn)定排序：上面所說(shuō)的關(guān)鍵字Ki可以是記錄Ri的主關(guān)鍵字，也可以是次關(guān)鍵字，甚至可以是記錄中若干數(shù)據(jù)項(xiàng)的組合。若Ki是主關(guān)鍵字，則任何一個(gè)無(wú)序的記錄序列經(jīng)排序后得到的有序序列是唯一的；若Ki是次關(guān)鍵字或是記錄中若干數(shù)據(jù)項(xiàng)的組合，得到的排序結(jié)果將是不唯一的，因?yàn)榇判蛴涗浀男蛄兄写嬖趦蓚€(gè)或兩個(gè)以上關(guān)鍵字相等的記錄。假設(shè)Ki=Kj(1≤i≤n，1≤j≤n，i≠j)，若在排序前的序列中Ri領(lǐng)先于Rj(即i<j)，經(jīng)過(guò)排序后得到的序列中Ri仍領(lǐng)先于Rj，則稱所用的排序方法是穩(wěn)定的；反之，當(dāng)相同關(guān)鍵字的領(lǐng)先關(guān)系在排序過(guò)程中發(fā)生變化者，則稱所用的排序方法是不穩(wěn)定的。在排序過(guò)程中，一般進(jìn)行兩種基本操作：（1）比較兩個(gè)關(guān)鍵字的大小；（2）將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。本章主要討論在向量結(jié)構(gòu)上各種排序方法的實(shí)現(xiàn)。為了討論方便，假設(shè)待排記錄的關(guān)鍵字均為整數(shù)，均從數(shù)組中下標(biāo)為1的位置開(kāi)始存儲(chǔ)，下標(biāo)為0的位置存儲(chǔ)監(jiān)視哨，或空閑不用。typedefintKeyType;typedefstruct{

KeyTypekey;

OtherTypeother_data;

}RecordType;8.2插入排序

8.2.1直接插入排序8.2.2折半插入排序8.2.3希爾排序8.2.1直接插入排序直接插入排序是一種最基本的插入排序方法。其基本操作是將第i個(gè)記錄插入到前面i-1個(gè)已排好序的記錄中，具體過(guò)程為：將第i個(gè)記錄的關(guān)鍵字Ki順次與其前面記錄的關(guān)鍵字Ki-1，Ki-2，…K1進(jìn)行比較，將所有關(guān)鍵字大于Ki的記錄依次向后移動(dòng)一個(gè)位置，直到遇見(jiàn)一個(gè)關(guān)鍵字小于或者等于Ki的記錄Kj，此時(shí)Kj后面必為空位置，將第i個(gè)記錄插入空位置即可。完整的直接插入排序是從i=2開(kāi)始，也就是說(shuō)，將第1個(gè)記錄視為已排好序的單元素子集合，然后將第二個(gè)記錄插入到單元素子集合中。i從2循環(huán)到n，即可實(shí)現(xiàn)完整的直接插入排序。圖8.1直接插入排序的例子。A)

{48

}

62

35

77

55

14

35

98

B)

{48

62}

35

77

55

14

35

98

C)

{35

48

62}

77

55

14

35

98

D)

{35

48

62

77}

55

14

35

98

E)

{35

48

55

62

77

}

14

35

98

F)

{14

35

48

55

62

77

}

35

98

G)

{14

35

35

48

55

62

77

}

98

H)

{14

35

35

48

55

62

77

98

}

假設(shè)待排序記錄存放在r[1..n]之中，為了提高效率，我們附設(shè)一個(gè)監(jiān)視哨r[0]，使得r[0]始終存放待插入的記錄。監(jiān)視哨的作用有兩個(gè)：一是備份待插入的記錄，以便前面關(guān)鍵字較大的記錄后移；二是防止越界.具體算法描述如下：void

InsSort(RecordType

r[],intlength)/*對(duì)記錄數(shù)組r做直接插入排序，length為數(shù)組的長(zhǎng)度*/{

for(

i=2;

i<length;

i++

){r[0]=r[i];

j=i-1;

/*將待插入記錄存放到監(jiān)視哨r[0]中*/while(r[0].key<r[j].key)

/*尋找插入位置*/

{r[j+1]=r[j];

j=j-1;

}r[j+1]=r[0];

/*將待插入記錄插入到已排序的序列中*/}}/*

InsSort

*/算法描述算法分析該算法的要點(diǎn)是：①使用監(jiān)視哨r[0]臨時(shí)保存待插入的記錄。②從后往前查找應(yīng)插入的位置。③查找與移動(dòng)用同一循環(huán)完成。直接插入排序算法分析：首先從空間角度來(lái)看，它只需要一個(gè)輔助空間r[0]。從時(shí)間耗費(fèi)角度來(lái)看，主要時(shí)間耗費(fèi)在關(guān)鍵字比較和移動(dòng)元素上。直接插入排序的時(shí)間復(fù)雜度為T(mén)(n)=O(n2)，空間復(fù)雜度為S(n)=O(1)。直接插入排序方法是穩(wěn)定的排序方法。直接插入排序算法簡(jiǎn)便，比較適用于待排序記錄數(shù)目較少且基本有序的情況。當(dāng)待排記錄數(shù)目較大時(shí)，直接插入排序的性能就不好

8.2.2折半插入排序在直接插入排序中，我們采用順序查找法來(lái)確定記錄的插入位置。由于（R1，R2，…，Ri-1）是有序子文件，我們可以采用折半查找法來(lái)確定R1的插入位置，這種排序稱為折半插入排序。其算法可寫(xiě)出如下：算法描述void

BinSort(RecordType

r[],intlength)/*對(duì)記錄數(shù)組r進(jìn)行折半插入排序，length為數(shù)組的長(zhǎng)度*/{for(

i=2

;i<=length;++i){x=r[i];low=1;

high=i-1;

while(low<=high)

/*確定插入位置*/{mid=(low+high)/2;

if(

x.key<r[mid].key

)

high=mid-1;else

low=mid+1;}for(

j=i-1

;j>=low;--j)

r[j+1]=r[j];

/*

記錄依次向后移動(dòng)*/r[low]=x;

/*插入記錄*/}}/*BinSort*/算法分析采用折半插入排序法，可減少關(guān)鍵字的比較次數(shù)。每插入一個(gè)元素，需要比較的次數(shù)最大為折半判定樹(shù)的深度，如插入第i個(gè)元素時(shí)，設(shè)i=2j,則需進(jìn)行l(wèi)og2i次比較，因此插入n-1個(gè)元素的平均關(guān)鍵字的比較次數(shù)為O(nlog2n)。雖然折半插入排序法與直接插入排序法相比較，改善了算法中比較次數(shù)的數(shù)量級(jí)，但其并未改變移動(dòng)元素的時(shí)間耗費(fèi)，所以折半插入排序的總的時(shí)間復(fù)雜度仍然是O(n2)。8.2.3希爾排序希爾排序（Shell’sMethod）又稱“縮小增量排序”（DiminishingIncrementSort），是由D.L.Shell在1959年提出來(lái)的。希爾排序的基本思想是：先將待排序記錄序列分割成若干個(gè)“較稀疏的”子序列，分別進(jìn)行直接插入排序。經(jīng)過(guò)上述粗略調(diào)整，整個(gè)序列中的記錄已經(jīng)基本有序，最后再對(duì)全部記錄進(jìn)行一次直接插入排序。具體實(shí)現(xiàn)時(shí)，首先選定兩個(gè)記錄間的距離d1，在整個(gè)待排序記錄序列中將所有間隔為d1的記錄分成一組，進(jìn)行組內(nèi)直接插入排序，然后再取兩個(gè)記錄間的距離d2<d1，在整個(gè)待排序記錄序列中，將所有間隔為d2的記錄分成一組，進(jìn)行組內(nèi)直接插入排序，直至選定兩個(gè)記錄間的距離dt=1為止，此時(shí)只有一個(gè)子序列，即整個(gè)待排序記錄序列。圖8.2希爾排序過(guò)程的實(shí)例void

ShellInsert(RecordTyper[],intlength，

int

delta)/*對(duì)記錄數(shù)組r做一趟希爾插入排序，length為數(shù)組的長(zhǎng)度,delta為增量*/{

for(i=1+delta；i<=length；i++)

/*

1+delta為第一個(gè)子序列的第二個(gè)元素的下標(biāo)*/

if(r[i].key<r[i-delta].key)

{

r[0]=r[i]；

/*

備份r[i]

(不做監(jiān)視哨)*/

for(j=i-delta；j>0&&r[0].key<r[j].key；j-=delta)

r[j+delta]=r[j]；

r[j+delta]=r[0]；}}/*ShellInsert*/算法描述void

ShellSort(RecordTyper[],intlength)/*對(duì)記錄數(shù)組r做希爾排序，length為數(shù)組r的長(zhǎng)度,delta為增量數(shù)組，n為delta[]的長(zhǎng)度*/{

for(i=0；i<=n-1；++i)

ShellInsert(r，Length,delta[i])；}算法描述續(xù)算法分析希爾排序的分析是一個(gè)復(fù)雜的問(wèn)題，因?yàn)樗臅r(shí)間耗費(fèi)是所取的“增量”序列的函數(shù)。到目前為止，尚未有人求得一種最好的增量序列。但大量研究也得出了一些局部的結(jié)論。在排序過(guò)程中，相同關(guān)鍵字記錄的領(lǐng)先關(guān)系發(fā)生變化，則說(shuō)明該排序方法是不穩(wěn)定的。8.3交換排序8.3.1冒泡排序8.3.2快速排序8.3.1冒泡排序冒泡排序是一種簡(jiǎn)單的交換類排序方法，它是通過(guò)相鄰的數(shù)據(jù)元素的交換，逐步將待排序序列變成有序序列的過(guò)程。冒泡排序的基本思想是：從頭掃描待排序記錄序列，在掃描的過(guò)程中順次比較相鄰的兩個(gè)元素的大小。以升序?yàn)槔涸诘谝惶伺判蛑?，?duì)n個(gè)記錄進(jìn)行如下操作：若相鄰的兩個(gè)記錄的關(guān)鍵字比較，逆序時(shí)就交換位置。在掃描的過(guò)程中，不斷的將相鄰兩個(gè)記錄中關(guān)鍵字大的記錄向后移動(dòng)，最后將待排序記錄序列中的最大關(guān)鍵字記錄換到了待排序記錄序列的末尾，這也是最大關(guān)鍵字記錄應(yīng)在的位置。然后進(jìn)行第二趟冒泡排序，對(duì)前n-1個(gè)記錄進(jìn)行同樣的操作，其結(jié)果是使次大的記錄被放在第n-1個(gè)記錄的位置上。如此反復(fù)，直到排好序?yàn)橹梗ㄈ粼谀骋惶嗣芭葸^(guò)程中，沒(méi)有發(fā)現(xiàn)一個(gè)逆序，則可結(jié)束冒泡排序），所以冒泡過(guò)程最多進(jìn)行n-1趟。圖8.3冒泡排序示例算法描述void

BubbleSort(RecordTyper[],intlength)/*對(duì)記錄數(shù)組r做冒泡排序，length為數(shù)組的長(zhǎng)度*/{n=length;

change=TRUE；for(i=1;i<=n-1&&change;++i){

change=FALSE；

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

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

{

x=r[j];

r[j]=r[j+1];

r[j+1]=x;change=TRUE；

}}}/*

BubbleSort

*/算法分析最壞情況下，待排序記錄按關(guān)鍵字的逆序進(jìn)行排列，此時(shí)，每一趟冒泡排序需進(jìn)行i次比較，3i次移動(dòng)。經(jīng)過(guò)n-1趟冒泡排序后，總的比較次數(shù)為總的移動(dòng)次數(shù)為3n(n-1)/2次，因此該算法的時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)。另外，冒泡排序法是一種穩(wěn)定的排序方法。8.3.2快速排序快速排序的基本思想是：從待排序記錄序列中選取一個(gè)記錄（通常選取第一個(gè)記錄），其關(guān)鍵字設(shè)為K1，然后將其余關(guān)鍵字小于K1的記錄移到前面，而將關(guān)鍵字大于K1的記錄移到后面，結(jié)果將待排序記錄序列分成兩個(gè)子表，最后將關(guān)鍵字為K1的記錄插到其分界線的位置處。我們將這個(gè)過(guò)程稱作一趟快速排序。通過(guò)一次劃分后，就以關(guān)鍵字為K1的記錄為分界線，將待排序序列分成了兩個(gè)子表，且前面子表中所有記錄的關(guān)鍵字均不大于K1，而后面子表中的所有記錄的關(guān)鍵字均不小于K1。對(duì)分割后的子表繼續(xù)按上述原則進(jìn)行分割，直到所有子表的表長(zhǎng)不超過(guò)1為止，此時(shí)待排序記錄序列就變成了一個(gè)有序表。圖8.4快速排序圖示快速排序算法描述voidQKSort(RecordTyper[],intlow,inthigh)/*對(duì)記錄數(shù)組r[low..high]用快速排序算法進(jìn)行排序*/{

if(1ow<high)

{

pos=QKPass(r,low,high);

QKSort(r,low,pos-1);

QKSort(r,pos+1,high);}}一趟快速排序算法描述:int

QKPass(RecordTyper[],intleft，intright)*對(duì)記錄數(shù)組r中的r[left]至r[right]部分進(jìn)行一趟排序，并得到基準(zhǔn)的位置，使得排序后的結(jié)果滿足其之后（前）的記錄的關(guān)鍵字均不小于（大于）于基準(zhǔn)記錄*/{

x=r[left]；

low=left;

high=right；while(low<high){while(low<high&&r[high].key>=x.key)

/*high從右到左找小于x.key的記錄*/

high--；if(low<high)

{r[low]=r[high]；low++;}

/*找到小于x.key的記錄，則進(jìn)行交換*/while(low<high&&r[low].key<x.key

)

/*low從左到右找大于x.key的記錄*/

low++;if(low<high){r[high]=r[low]；high--;}/*找到大于x.key的記錄，則交換*/}r[low]=x；

/*將基準(zhǔn)記錄保存到low=high的位置*/returnlow;

/*返回基準(zhǔn)記錄的位置*/}/*QKPass*/算法分析分析快速排序的時(shí)間耗費(fèi),共需進(jìn)行多少趟，取決于遞歸調(diào)用深度?？焖倥判蛩钑r(shí)間的平均值為T(mén)arg(n)≤Knln(n)，這是目前內(nèi)部排序方法中所能達(dá)到的最好平均時(shí)間復(fù)雜度。但是若初始記錄序列按關(guān)鍵字有序或基本有序時(shí)，快速排序?qū)⑼懽優(yōu)槊芭菖判?，其時(shí)間復(fù)雜度為O(n2)

。為改進(jìn)之，可采用其他方法選取樞軸元素，以彌補(bǔ)缺陷。8.4選擇排序選擇排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。我們主要介紹簡(jiǎn)單選擇排序、樹(shù)型選擇排序和堆排序。8.4.1簡(jiǎn)單選擇排序8.4.2樹(shù)型選擇排序8.4.3堆排序8.4.1

簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序的基本思想：第i趟簡(jiǎn)單選擇排序是指通過(guò)n-i次關(guān)鍵字的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i個(gè)記錄進(jìn)行交換。共需進(jìn)行i-1趟比較，直到所有記錄排序完成為止。例如：進(jìn)行第i趟選擇時(shí)，從當(dāng)前候選記錄中選出關(guān)鍵字最小的k號(hào)記錄，并和第i個(gè)記錄進(jìn)行交換。算法描述void

SelectSort(RecordTyper[],intlength)/*對(duì)記錄數(shù)組r做簡(jiǎn)單選擇排序，length為數(shù)組的長(zhǎng)度*/{

n=length;for(i=1;i<=n－１;++i)

{k=i；for(j=i+1;j<=n;++j)

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

k=j；if(k!=i)

{x=r[i]；r[i]=r[k]；r[k]=x;}}

}/*SelectSort

*/算法分析簡(jiǎn)單選擇排序算法分析：在簡(jiǎn)單選擇排序過(guò)程中，所需移動(dòng)記錄的次數(shù)比較少。最好情況下，即待排序記錄初始狀態(tài)就已經(jīng)是正序排列了，則不需要移動(dòng)記錄。最壞情況下，即待排序記錄初始狀態(tài)是按逆序排列的，則需要移動(dòng)記錄的次數(shù)最多為3（n-1）。簡(jiǎn)單選擇排序過(guò)程中需要進(jìn)行的比較次數(shù)與初始狀態(tài)下待排序的記錄序列的排列情況無(wú)關(guān)。當(dāng)i=1時(shí)，需進(jìn)行n-1次比較；當(dāng)i=2時(shí)，需進(jìn)行n-2次比較；依次類推，共需要進(jìn)行的比較次數(shù)是

=(n-1)+(n-2)+…+2+1=n(n-1)/2，即進(jìn)行比較操作的時(shí)間復(fù)雜度為O(n2)。8.4.2樹(shù)型選擇排序樹(shù)型選擇排序也稱作錦標(biāo)賽排序。它的基本思想是：先把待排序的n個(gè)記錄的關(guān)鍵字兩兩進(jìn)行比較，取出較小者。然后再在n/2個(gè)較小者中，采用同樣的方法進(jìn)行比較選出每?jī)蓚€(gè)中的較小者，如此反復(fù)，直至選出最小關(guān)鍵字記錄為止。我們可以用一棵有n個(gè)結(jié)點(diǎn)的樹(shù)來(lái)表示，選出的最小關(guān)鍵字記錄就是這棵樹(shù)的根結(jié)點(diǎn)。在輸出最小關(guān)鍵字之后，為選出次小關(guān)鍵字，將根結(jié)點(diǎn)即最小關(guān)鍵字記錄所對(duì)應(yīng)的葉子結(jié)點(diǎn)的關(guān)鍵字的值置為∞，再進(jìn)行上述的過(guò)程，直到所有的記錄全部輸出為止。圖8.5樹(shù)型選擇排序示例(a)選出最小關(guān)鍵字13圖8.5樹(shù)型選擇排序示例(b)選出次小關(guān)鍵字27算法分析在樹(shù)型選擇排序中，被選中的關(guān)鍵字都是走了一條由葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的比較的過(guò)程,由于含有n個(gè)葉子節(jié)點(diǎn)的完全二叉數(shù)的深度log2n+1，則在樹(shù)型選擇排序中，每選擇一個(gè)小關(guān)鍵字需要進(jìn)行l(wèi)og2n次比較，因此其時(shí)間復(fù)雜度為O(nlog2n)。移動(dòng)記錄次數(shù)不超過(guò)比較次數(shù)，故總的算法時(shí)間復(fù)雜度為O(nlog2n)。與簡(jiǎn)單選擇排序相比較降低了比較次數(shù)的數(shù)量級(jí)，增加了n-1個(gè)額外的存儲(chǔ)空間存放中間比較結(jié)果，同時(shí)附加了與∞進(jìn)行比較的時(shí)間耗費(fèi)。為了彌補(bǔ)，威洛母斯在1964年提出了進(jìn)一步的改進(jìn)方法，即另外一種形式的選擇排序方法——堆排序。8.4.3堆排序堆排序是對(duì)樹(shù)型選擇排序的進(jìn)一步改進(jìn)。采用堆排序時(shí)，只需要一個(gè)記錄大小的輔助空間。堆排序是在排序過(guò)程中，將向量中存儲(chǔ)的數(shù)據(jù)看成一棵完全二叉樹(shù)，利用完全二叉樹(shù)中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來(lái)選擇關(guān)鍵字最小的記錄，即待排序記錄仍采用向量數(shù)組方式存儲(chǔ)，并非采用樹(shù)的存儲(chǔ)結(jié)構(gòu)，而僅僅是采用完全二叉樹(shù)的順序結(jié)構(gòu)的特征進(jìn)行分析而已。具體做法是：把待排序的記錄的關(guān)鍵字存放在數(shù)組r[1..n]之中，將r看成是一棵完全二叉樹(shù)的順序表示，每個(gè)結(jié)點(diǎn)表示一個(gè)記錄，第一個(gè)記錄r[1]作為二叉樹(shù)的根，以下各記錄r[2...n]依次逐層從左到右順序排列，任意結(jié)點(diǎn)r[i]的左孩子是r[2i],右孩子是r[2i+1],雙親是r[i/2]。對(duì)這棵完全二叉樹(shù)進(jìn)行調(diào)整，使各結(jié)點(diǎn)的關(guān)鍵字值滿足下列條件：r[i].key≥r[2i].key并且r[i].key≥r[2i+1].key(i=1,2,...n/2)，滿足這個(gè)條件的完全二叉樹(shù)為堆。這個(gè)堆中根結(jié)點(diǎn)的關(guān)鍵字最大，稱為大根堆。反之，如果這棵完全二叉樹(shù)中任意結(jié)點(diǎn)的關(guān)鍵字大于或者等于其左孩子和右孩子的關(guān)鍵字（當(dāng)有左孩子或右孩子時(shí)），對(duì)應(yīng)的堆為小根堆。圖8.6堆示例(a)大根椎(b)小根椎8.5歸并排序前面介紹的三類排序方法：插入排序、交換排序和選擇排序，都是將一組記錄按關(guān)鍵字大小排成一個(gè)有序的序列。而本節(jié)介紹的歸并排序法，它的基本思想是將兩個(gè)或兩個(gè)以上有序表合并成一個(gè)新的有序表。假設(shè)初始序列含有n個(gè)記錄，首先將這n個(gè)記錄看成n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1，然后兩兩歸并，得到個(gè)長(zhǎng)度為2（n為奇數(shù)時(shí)，最后一個(gè)序列的長(zhǎng)度為1）的有序子序列；在此基礎(chǔ)上，再進(jìn)行兩兩歸并，如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。這種方法被稱作2-路歸并排序。歸并的思想主要用于外部排序。外部排序可分兩步，①待排序記錄分批讀入內(nèi)存，用某種方法在內(nèi)存排序，組成有序的子文件，再按某種策略存入外存。②子文件多路歸并，成為較長(zhǎng)有序子文件，再記入外存，如此反復(fù)，直到整個(gè)待排序文件有序。外部排序可使用外存、磁帶、磁盤(pán)，最初形成有序子文件長(zhǎng)取決于內(nèi)存所能提供排序區(qū)大小和最初排序策略，歸并路數(shù)取決于所能提供排序的外部設(shè)備數(shù)。8.6基數(shù)排序

前介紹的排序方法都是根據(jù)關(guān)鍵字值的大小來(lái)進(jìn)行排序的。本節(jié)介紹的方法是按組成關(guān)鍵字的各個(gè)位的值來(lái)實(shí)現(xiàn)的排序的，這種方法稱為基數(shù)排序（radixsort）。采用基數(shù)排序法需要使用一批桶（或箱子），故這種方法又稱為桶排序列。下面以十進(jìn)制數(shù)為例來(lái)說(shuō)明基數(shù)排充的過(guò)程。假定待排序文件中所有記錄的關(guān)鍵字為不超過(guò)d位的非負(fù)整數(shù)，從最高位到最低位（個(gè)位）的編號(hào)依次為1，2，…，d。設(shè)置10個(gè)隊(duì)列（即上面所說(shuō)的桶），它們的編號(hào)分別為0，1，2，…，9。當(dāng)?shù)谝槐閽呙栉淖謺r(shí)，將記錄按關(guān)鍵字的個(gè)位（即第d位）數(shù)分別放到相應(yīng)的隊(duì)列中：個(gè)位數(shù)為0的關(guān)鍵字，其記錄依次放入0號(hào)隊(duì)列中i個(gè)位數(shù)為1的關(guān)鍵字，其記錄放入1號(hào)隊(duì)列中…；個(gè)位數(shù)為9的關(guān)鍵字，其記錄放入9號(hào)隊(duì)列中。這一過(guò)程叫做按個(gè)位數(shù)分配。現(xiàn)在把這10個(gè)隊(duì)列中的記錄，按0號(hào)，1號(hào)，9號(hào)隊(duì)列的順序收集和排列起來(lái)，同一隊(duì)列中的記錄按先進(jìn)先出的次序排列。這是第1遍。第2遍排序使用同樣的辦法，將第1遍排序后的記錄按其關(guān)鍵字的十位數(shù)（第d—1位）分配到相應(yīng)的隊(duì)列中，再把隊(duì)列中的記錄收集和排列起來(lái)。繼續(xù)進(jìn)行下去。第d遍排序時(shí)，按第d—1遍排序后記錄的關(guān)鍵字的最高位（第1位）進(jìn)行分配，再收集和排列各隊(duì)列中的記錄，醫(yī)得到了原文件的有序文件，這就是以10為基的關(guān)鍵字的基數(shù)排序法。例如，給出關(guān)鍵字序列（02，77，70，54，64，21，55，11，38，21），其中關(guān)鍵字02用1個(gè)0在2的前面補(bǔ)足到2位，余關(guān)鍵字均為2位的正整數(shù)。進(jìn)行基數(shù)排序的過(guò)程如圖9-9所示。在這個(gè)例子中，文件和所有的隊(duì)列都表示成向量（一維數(shù)組）。顯然，關(guān)鍵字的某一位有可能均為同一個(gè)數(shù)字（例如，個(gè)數(shù)都為0），這時(shí)所有的記錄都同時(shí)裝入同一個(gè)隊(duì)列中（例如，同時(shí)裝入0號(hào)隊(duì)列中）。因此，如果每個(gè)隊(duì)列的大小和文件大小相同，則需要一個(gè)10倍于文件大小的附加空間。此外，排序時(shí)需要進(jìn)行反復(fù)的分配和收集記錄。所以，采用順序表示是不方便的?；鶖?shù)排序所需的計(jì)算時(shí)間不僅與文件的大小n有關(guān)，而且還與關(guān)鍵字的位數(shù)、關(guān)鍵字的基有關(guān)。設(shè)關(guān)鍵字的基為r（十進(jìn)制數(shù)的基為10，二進(jìn)制數(shù)的基為2），為建立r個(gè)空隊(duì)列所需的時(shí)間為O（r）。把n個(gè)記錄分放到各個(gè)隊(duì)列中并重新收集起來(lái)所需的時(shí)間為O（n），因此一遍排序所需的時(shí)間為O（n+r）。若每個(gè)關(guān)鍵字有d位，則總共要進(jìn)行d遍排，所以基數(shù)排序的時(shí)間復(fù)雜度為O（d（n+r））。由于關(guān)鍵字的位數(shù)d直接與基數(shù)r以及最大關(guān)鍵字的值有關(guān)，因此不同的r和關(guān)鍵字將需要不同的時(shí)間。8.7各種內(nèi)部排序方法比較在已介紹的上述各種內(nèi)部排序方法中，就所需要的計(jì)算時(shí)間來(lái)看，快速排序、歸并排序、堆排序是很好的方法。但是，歸并排序需要大小為n的輔助空間，快速排序需要一個(gè)棧。除了快速排序、堆排序、選擇排序不穩(wěn)定外，基它排序方法都是穩(wěn)定的。評(píng)價(jià)一個(gè)排序算法性能好壞的主要標(biāo)準(zhǔn)是它所需的計(jì)算時(shí)間和存儲(chǔ)空間。影響計(jì)算時(shí)間的兩個(gè)景要因素是比較關(guān)鍵字的次數(shù)和記錄的移動(dòng)次數(shù)。在實(shí)際應(yīng)用中，究竟應(yīng)該選用何種排