常用的非比較排序算法：計(jì)數(shù)排序，基數(shù)排序，桶排序的詳細(xì)資料概述

這篇文章中我們來(lái)探討一下常用的非比較排序算法：計(jì)數(shù)排序，基數(shù)排序，桶排序。在一定條件下，它們的時(shí)間復(fù)雜度可以達(dá)到O(n)。

這里我們用到的唯一數(shù)據(jù)結(jié)構(gòu)就是數(shù)組，當(dāng)然我們也可以利用鏈表來(lái)實(shí)現(xiàn)下述算法。

計(jì)數(shù)排序(Counting Sort)

計(jì)數(shù)排序用到一個(gè)額外的計(jì)數(shù)數(shù)組C，根據(jù)數(shù)組C來(lái)將原數(shù)組A中的元素排到正確的位置。

通俗地理解，例如有10個(gè)年齡不同的人，假如統(tǒng)計(jì)出有8個(gè)人的年齡不比小明大（即小于等于小明的年齡，這里也包括了小明），那么小明的年齡就排在第8位，通過(guò)這種思想可以確定每個(gè)人的位置，也就排好了序。當(dāng)然，年齡一樣時(shí)需要特殊處理（保證穩(wěn)定性）：通過(guò)反向填充目標(biāo)數(shù)組，填充完畢后將對(duì)應(yīng)的數(shù)字統(tǒng)計(jì)遞減，可以確保計(jì)數(shù)排序的穩(wěn)定性。

計(jì)數(shù)排序的步驟如下：

統(tǒng)計(jì)數(shù)組A中每個(gè)值A(chǔ)[i]出現(xiàn)的次數(shù)，存入C[A[i]]

從前向后，使數(shù)組C中的每個(gè)值等于其與前一項(xiàng)相加，這樣數(shù)組C[A[i]]就變成了代表數(shù)組A中小于等于A[i]的元素個(gè)數(shù)

反向填充目標(biāo)數(shù)組B：將數(shù)組元素A[i]放在數(shù)組B的第C[A[i]]個(gè)位置（下標(biāo)為C[A[i]] – 1），每放一個(gè)元素就將C[A[i]]遞減

計(jì)數(shù)排序的實(shí)現(xiàn)代碼如下：

#include

usingnamespacestd;

// 分類 ------------ 內(nèi)部非比較排序

// 數(shù)據(jù)結(jié)構(gòu) --------- 數(shù)組

// 最差時(shí)間復(fù)雜度 ---- O(n + k)

// 最優(yōu)時(shí)間復(fù)雜度 ---- O(n + k)

// 平均時(shí)間復(fù)雜度 ---- O(n + k)

// 所需輔助空間 ------ O(n + k)

// 穩(wěn)定性 ----------- 穩(wěn)定

constintk=100;// 基數(shù)為100，排序[0,99]內(nèi)的整數(shù)

intC[k];// 計(jì)數(shù)數(shù)組

voidCountingSort(intA[],intn)

{

for(inti=0;i

{

C[i]=0;

}

for(inti=0;i

{

C[A[i]]++;

}

for(inti=1;i

{

C[i]=C[i]+C[i-1];

}

int*B=(int*)malloc((n)*sizeof(int));// 分配臨時(shí)空間,長(zhǎng)度為n，用來(lái)暫存中間數(shù)據(jù)

for(inti=n-1;i>=0;i--)// 從后向前掃描保證計(jì)數(shù)排序的穩(wěn)定性(重復(fù)元素相對(duì)次序不變)

{

B[--C[A[i]]]=A[i];// 把每個(gè)元素A[i]放到它在輸出數(shù)組B中的正確位置上

// 當(dāng)再遇到重復(fù)元素時(shí)會(huì)被放在當(dāng)前元素的前一個(gè)位置上保證計(jì)數(shù)排序的穩(wěn)定性

}

for(inti=0;i

{

A[i]=B[i];

}

free(B);// 釋放臨時(shí)空間

}

intmain()

{

intA[]={15,22,19,46,27,73,1,19,8};// 針對(duì)計(jì)數(shù)排序設(shè)計(jì)的輸入，每一個(gè)元素都在[0,100]上且有重復(fù)元素

intn=sizeof(A)/sizeof(int);

CountingSort(A,n);

printf("計(jì)數(shù)排序結(jié)果：");

for(inti=0;i

{

printf("%d ",A[i]);

}

printf("\n");

return0;

}

下圖給出了對(duì){ 4, 1, 3, 4, 3 }進(jìn)行計(jì)數(shù)排序的簡(jiǎn)單演示過(guò)程

計(jì)數(shù)排序的時(shí)間復(fù)雜度和空間復(fù)雜度與數(shù)組A的數(shù)據(jù)范圍（A中元素的最大值與最小值的差加上1）有關(guān)，因此對(duì)于數(shù)據(jù)范圍很大的數(shù)組，計(jì)數(shù)排序需要大量時(shí)間和內(nèi)存。

例如：對(duì)0到99之間的數(shù)字進(jìn)行排序，計(jì)數(shù)排序是最好的算法，然而計(jì)數(shù)排序并不適合按字母順序排序人名，將計(jì)數(shù)排序用在基數(shù)排序算法中，能夠更有效的排序數(shù)據(jù)范圍很大的數(shù)組。

基數(shù)排序(Radix Sort)

基數(shù)排序的發(fā)明可以追溯到1887年赫爾曼·何樂(lè)禮在打孔卡片制表機(jī)上的貢獻(xiàn)。它是這樣實(shí)現(xiàn)的：將所有待比較正整數(shù)統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開(kāi)始進(jìn)行基數(shù)為10的計(jì)數(shù)排序，一直到最高位計(jì)數(shù)排序完后，數(shù)列就變成一個(gè)有序序列（利用了計(jì)數(shù)排序的穩(wěn)定性）。

基數(shù)排序的實(shí)現(xiàn)代碼如下：

#include

usingnamespacestd;

// 分類 ------------- 內(nèi)部非比較排序

// 數(shù)據(jù)結(jié)構(gòu) ---------- 數(shù)組

// 最差時(shí)間復(fù)雜度 ---- O(n * dn)

// 最優(yōu)時(shí)間復(fù)雜度 ---- O(n * dn)

// 平均時(shí)間復(fù)雜度 ---- O(n * dn)

// 所需輔助空間 ------ O(n * dn)

// 穩(wěn)定性 ----------- 穩(wěn)定

constintdn=3;// 待排序的元素為三位數(shù)及以下

constintk=10;// 基數(shù)為10，每一位的數(shù)字都是[0,9]內(nèi)的整數(shù)

intC[k];

intGetDigit(intx,intd)// 獲得元素x的第d位數(shù)字

{

intradix[]={1,1,10,100};// 最大為三位數(shù)，所以這里只要到百位就滿足了

return(x/radix[d])%10;

}

voidCountingSort(intA[],intn,intd)// 依據(jù)元素的第d位數(shù)字，對(duì)A數(shù)組進(jìn)行計(jì)數(shù)排序

{

for(inti=0;i

{

C[i]=0;

}

for(inti=0;i

{

C[GetDigit(A[i],d)]++;

}

for(inti=1;i

{

C[i]=C[i]+C[i-1];

}

int*B=(int*)malloc(n *sizeof(int));

for(inti=n-1;i>=0;i--)

{

intdight=GetDigit(A[i],d);// 元素A[i]當(dāng)前位數(shù)字為dight

B[--C[dight]]=A[i];// 根據(jù)當(dāng)前位數(shù)字，把每個(gè)元素A[i]放到它在輸出數(shù)組B中的正確位置上

// 當(dāng)再遇到當(dāng)前位數(shù)字同為dight的元素時(shí)，會(huì)將其放在當(dāng)前元素的前一個(gè)位置上保證計(jì)數(shù)排序的穩(wěn)定性

}

for(inti=0;i

{

A[i]=B[i];

}

free(B);

}

voidLsdRadixSort(intA[],intn)// 最低位優(yōu)先基數(shù)排序

{

for(intd=1;d<=?dn;d++)?????// 從低位到高位

CountingSort(A,n,d);// 依據(jù)第d位數(shù)字對(duì)A進(jìn)行計(jì)數(shù)排序

}

intmain()

{

intA[]={20,90,64,289,998,365,852,123,789,456};// 針對(duì)基數(shù)排序設(shè)計(jì)的輸入

intn=sizeof(A)/sizeof(int);

LsdRadixSort(A,n);

printf("基數(shù)排序結(jié)果：");

for(inti=0;i

{

printf("%d ",A[i]);

}

printf("\n");

return0;

}

下圖給出了對(duì){ 329, 457, 657, 839, 436, 720, 355 }進(jìn)行基數(shù)排序的簡(jiǎn)單演示過(guò)程

基數(shù)排序的時(shí)間復(fù)雜度是O(n*dn)，其中n是待排序元素個(gè)數(shù)，dn是數(shù)字位數(shù)。這個(gè)時(shí)間復(fù)雜度不一定優(yōu)于O(n log n)，dn的大小取決于數(shù)字位的選擇（比如比特位數(shù)），和待排序數(shù)據(jù)所屬數(shù)據(jù)類型的全集的大??；dn決定了進(jìn)行多少輪處理，而n是每輪處理的操作數(shù)目。

如果考慮和比較排序進(jìn)行對(duì)照，基數(shù)排序的形式復(fù)雜度雖然不一定更小，但由于不進(jìn)行比較，因此其基本操作的代價(jià)較小，而且如果適當(dāng)?shù)倪x擇基數(shù)，dn一般不大于log n，所以基數(shù)排序一般要快過(guò)基于比較的排序，比如快速排序。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序并不是只能用于整數(shù)排序。

桶排序(Bucket Sort)

桶排序也叫箱排序。工作的原理是將數(shù)組元素映射到有限數(shù)量個(gè)桶里，利用計(jì)數(shù)排序可以定位桶的邊界，每個(gè)桶再各自進(jìn)行桶內(nèi)排序（使用其它排序算法或以遞歸方式繼續(xù)使用桶排序）。

桶排序的實(shí)現(xiàn)代碼如下：

#include

usingnamespacestd;

// 分類 ------------- 內(nèi)部非比較排序

// 數(shù)據(jù)結(jié)構(gòu) --------- 數(shù)組

// 最差時(shí)間復(fù)雜度 ---- O(nlogn)或O(n^2)，只有一個(gè)桶，取決于桶內(nèi)排序方式

// 最優(yōu)時(shí)間復(fù)雜度 ---- O(n)，每個(gè)元素占一個(gè)桶

// 平均時(shí)間復(fù)雜度 ---- O(n)，保證各個(gè)桶內(nèi)元素個(gè)數(shù)均勻即可

// 所需輔助空間 ------ O(n + bn)

// 穩(wěn)定性 ----------- 穩(wěn)定

/* 本程序用數(shù)組模擬桶 */

constintbn=5;// 這里排序[0,49]的元素，使用5個(gè)桶就夠了，也可以根據(jù)輸入動(dòng)態(tài)確定桶的數(shù)量

intC[bn];// 計(jì)數(shù)數(shù)組，存放桶的邊界信息

voidInsertionSort(intA[],intleft,intright)

{

for(inti=left+1;i<=?right;i++)??// 從第二張牌開(kāi)始抓，直到最后一張牌

{

intget=A[i];

intj=i-1;

while(j>=left&&A[j]>get)

{

A[j+1]=A[j];

j--;

}

A[j+1]=get;

}

}

intMapToBucket(intx)

{

returnx/10;// 映射函數(shù)f(x)，作用相當(dāng)于快排中的Partition，把大量數(shù)據(jù)分割成基本有序的數(shù)據(jù)塊

}

voidCountingSort(intA[],intn)

{

for(inti=0;i

{

C[i]=0;

}

for(inti=0;i

{

C[MapToBucket(A[i])]++;

}

for(inti=1;i

{

C[i]=C[i]+C[i-1];

}

int*B=(int*)malloc((n)*sizeof(int));

for(inti=n-1;i>=0;i--)// 從后向前掃描保證計(jì)數(shù)排序的穩(wěn)定性(重復(fù)元素相對(duì)次序不變)

{

intb=MapToBucket(A[i]);// 元素A[i]位于b號(hào)桶

B[--C[b]]=A[i];// 把每個(gè)元素A[i]放到它在輸出數(shù)組B中的正確位置上

// 桶的邊界被更新：C[b]為b號(hào)桶第一個(gè)元素的位置

}

for(inti=0;i

{

A[i]=B[i];

}

free(B);

}

voidBucketSort(intA[],intn)

{

CountingSort(A,n);// 利用計(jì)數(shù)排序確定各個(gè)桶的邊界（分桶）

for(inti=0;i

{

intleft=C[i];// C[i]為i號(hào)桶第一個(gè)元素的位置

intright=(i==bn-1?n-1:C[i+1]-1);// C[i+1]-1為i號(hào)桶最后一個(gè)元素的位置

if(left

InsertionSort(A,left,right);

}

}

intmain()

{

intA[]={29,25,3,49,9,37,21,43};// 針對(duì)桶排序設(shè)計(jì)的輸入

intn=sizeof(A)/sizeof(int);

BucketSort(A,n);

printf("桶排序結(jié)果：");

for(inti=0;i

{

printf("%d ",A[i]);

}

printf("\n");

return0;

}

下圖給出了對(duì){ 29, 25, 3, 49, 9, 37, 21, 43 }進(jìn)行桶排序的簡(jiǎn)單演示過(guò)程

桶排序不是比較排序，不受到O(nlogn)下限的影響，它是鴿巢排序的一種歸納結(jié)果，當(dāng)所要排序的數(shù)組值分散均勻的時(shí)候，桶排序擁有線性的時(shí)間復(fù)雜度。