常用排序算法總結(jié)二(計(jì)數(shù)排序，基數(shù)排序，桶排序)
目錄
上一篇文章中我們總結(jié)了常用的比較排序算法，主要有冒泡排序，選擇排序，插入排序，歸并排序，堆排序，快速排序等。
這篇文章中我們來探討一下常用的非比較排序算法：計(jì)數(shù)排序，基數(shù)排序，桶排序。在一定條件下，它們的時(shí)間復(fù)雜度可以達(dá)到O(n)。
這里我們用到的唯一數(shù)據(jù)結(jié)構(gòu)就是數(shù)組，當(dāng)然我們也可以利用鏈表來實(shí)現(xiàn)下述算法。
計(jì)數(shù)排序(Counting Sort)
計(jì)數(shù)排序用到一個(gè)額外的計(jì)數(shù)數(shù)組C，根據(jù)數(shù)組C來將原數(shù)組A中的元素排到正確的位置。
通俗地理解，例如有10個(gè)年齡不同的人，假如統(tǒng)計(jì)出有8個(gè)人的年齡不比小明大（即小于等于小明的年齡，這里也包括了小明），那么小明的年齡就排在第8位，通過這種思想可以確定每個(gè)人的位置，也就排好了序。當(dāng)然，年齡一樣時(shí)需要特殊處理（保證穩(wěn)定性）：通過反向填充目標(biāo)數(shù)組，填充完畢后將對應(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<iostream> using namespace std; // 分類 ------------ 內(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)定 const int k = 100; // 基數(shù)為100，排序[0,99]內(nèi)的整數(shù) int C[k]; // 計(jì)數(shù)數(shù)組 void CountingSort(int A[], int n) { for (int i = 0; i < k; i++) // 初始化，將數(shù)組C中的元素置0(此步驟可省略，整型數(shù)組元素默認(rèn)值為0) { C[i] = 0; } for (int i = 0; i < n; i++) // 使C[i]保存著等于i的元素個(gè)數(shù) { C[A[i]]++; } for (int i = 1; i < k; i++) // 使C[i]保存著小于等于i的元素個(gè)數(shù)，排序后元素i就放在第C[i]個(gè)輸出位置上 { C[i] = C[i] + C[i - 1]; } int *B = (int *)malloc((n) * sizeof(int));// 分配臨時(shí)空間,長度為n，用來暫存中間數(shù)據(jù) for (int i = n - 1; i >= 0; i--) // 從后向前掃描保證計(jì)數(shù)排序的穩(wěn)定性(重復(fù)元素相對次序不變) { B[--C[A[i]]] = A[i]; // 把每個(gè)元素A[i]放到它在輸出數(shù)組B中的正確位置上 // 當(dāng)再遇到重復(fù)元素時(shí)會(huì)被放在當(dāng)前元素的前一個(gè)位置上保證計(jì)數(shù)排序的穩(wěn)定性 } for (int i = 0; i < n; i++) // 把臨時(shí)空間B中的數(shù)據(jù)拷貝回A { A[i] = B[i]; } free(B); // 釋放臨時(shí)空間 } int main() { int A[] = { 15, 22, 19, 46, 27, 73, 1, 19, 8 }; // 針對計(jì)數(shù)排序設(shè)計(jì)的輸入，每一個(gè)元素都在[0,100]上且有重復(fù)元素 int n = sizeof(A) / sizeof(int); CountingSort(A, n); printf("計(jì)數(shù)排序結(jié)果："); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); return 0; }
下圖給出了對{ 4, 1, 3, 4, 3 }進(jìn)行計(jì)數(shù)排序的簡單演示過程
計(jì)數(shù)排序的時(shí)間復(fù)雜度和空間復(fù)雜度與數(shù)組A的數(shù)據(jù)范圍（A中元素的最大值與最小值的差加上1）有關(guān)，因此對于數(shù)據(jù)范圍很大的數(shù)組，計(jì)數(shù)排序需要大量時(shí)間和內(nèi)存。
例如：對0到99之間的數(shù)字進(jìn)行排序，計(jì)數(shù)排序是最好的算法，然而計(jì)數(shù)排序并不適合按字母順序排序人名，將計(jì)數(shù)排序用在基數(shù)排序算法中，能夠更有效的排序數(shù)據(jù)范圍很大的數(shù)組。
基數(shù)排序(Radix Sort)
基數(shù)排序的發(fā)明可以追溯到1887年赫爾曼·何樂禮在打孔卡片制表機(jī)上的貢獻(xiàn)。它是這樣實(shí)現(xiàn)的：將所有待比較正整數(shù)統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開始進(jìn)行基數(shù)為10的計(jì)數(shù)排序，一直到最高位計(jì)數(shù)排序完后，數(shù)列就變成一個(gè)有序序列（利用了計(jì)數(shù)排序的穩(wěn)定性）。
基數(shù)排序的實(shí)現(xiàn)代碼如下：
#include<iostream> using namespace std; // 分類 ------------- 內(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)定 const int dn = 3; // 待排序的元素為三位數(shù)及以下 const int k = 10; // 基數(shù)為10，每一位的數(shù)字都是[0,9]內(nèi)的整數(shù) int C[k]; int GetDigit(int x, int d) // 獲得元素x的第d位數(shù)字 { int radix[] = { 1, 1, 10, 100 };// 最大為三位數(shù)，所以這里只要到百位就滿足了 return (x / radix[d]) % 10; } void CountingSort(int A[], int n, int d)// 依據(jù)元素的第d位數(shù)字，對A數(shù)組進(jìn)行計(jì)數(shù)排序 { for (int i = 0; i < k; i++) { C[i] = 0; } for (int i = 0; i < n; i++) { C[GetDigit(A[i], d)]++; } for (int i = 1; i < k; i++) { C[i] = C[i] + C[i - 1]; } int *B = (int*)malloc(n * sizeof(int)); for (int i = n - 1; i >= 0; i--) { int dight = 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 (int i = 0; i < n; i++) { A[i] = B[i]; } free(B); } void LsdRadixSort(int A[], int n) // 最低位優(yōu)先基數(shù)排序 { for (int d = 1; d <= dn; d++) // 從低位到高位 CountingSort(A, n, d); // 依據(jù)第d位數(shù)字對A進(jìn)行計(jì)數(shù)排序 } int main() { int A[] = { 20, 90, 64, 289, 998, 365, 852, 123, 789, 456 };// 針對基數(shù)排序設(shè)計(jì)的輸入 int n = sizeof(A) / sizeof(int); LsdRadixSort(A, n); printf("基數(shù)排序結(jié)果："); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); return 0; }
下圖給出了對{ 329, 457, 657, 839, 436, 720, 355 }進(jìn)行基數(shù)排序的簡單演示過程
基數(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)行對照，基數(shù)排序的形式復(fù)雜度雖然不一定更小，但由于不進(jìn)行比較，因此其基本操作的代價(jià)較小，而且如果適當(dāng)?shù)倪x擇基數(shù)，dn一般不大于log n，所以基數(shù)排序一般要快過基于比較的排序，比如快速排序。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序并不是只能用于整數(shù)排序。
桶排序(Bucket Sort)
桶排序也叫箱排序。工作的原理是將數(shù)組元素映射到有限數(shù)量個(gè)桶里，利用計(jì)數(shù)排序可以定位桶的邊界，每個(gè)桶再各自進(jìn)行桶內(nèi)排序（使用其它排序算法或以遞歸方式繼續(xù)使用桶排序）。
桶排序的實(shí)現(xiàn)代碼如下：
#include<iostream> using namespace std; // 分類 ------------- 內(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ù)組模擬桶 */ const int bn = 5; // 這里排序[0,49]的元素，使用5個(gè)桶就夠了，也可以根據(jù)輸入動(dòng)態(tài)確定桶的數(shù)量 int C[bn]; // 計(jì)數(shù)數(shù)組，存放桶的邊界信息 void InsertionSort(int A[], int left, int right) { for (int i = left + 1; i <= right; i++) // 從第二張牌開始抓，直到最后一張牌 { int get = A[i]; int j = i - 1; while (j >= left && A[j] > get) { A[j + 1] = A[j]; j--; } A[j + 1] = get; } } int MapToBucket(int x) { return x / 10; // 映射函數(shù)f(x)，作用相當(dāng)于快排中的Partition，把大量數(shù)據(jù)分割成基本有序的數(shù)據(jù)塊 } void CountingSort(int A[], int n) { for (int i = 0; i < bn; i++) { C[i] = 0; } for (int i = 0; i < n; i++) // 使C[i]保存著i號桶中元素的個(gè)數(shù) { C[MapToBucket(A[i])]++; } for (int i = 1; i < bn; i++) // 定位桶邊界：初始時(shí)，C[i]-1為i號桶最后一個(gè)元素的位置 { C[i] = C[i] + C[i - 1]; } int *B = (int *)malloc((n) * sizeof(int)); for (int i = n - 1; i >= 0; i--)// 從后向前掃描保證計(jì)數(shù)排序的穩(wěn)定性(重復(fù)元素相對次序不變) { int b = MapToBucket(A[i]); // 元素A[i]位于b號桶 B[--C[b]] = A[i]; // 把每個(gè)元素A[i]放到它在輸出數(shù)組B中的正確位置上 // 桶的邊界被更新：C[b]為b號桶第一個(gè)元素的位置 } for (int i = 0; i < n; i++) { A[i] = B[i]; } free(B); } void BucketSort(int A[], int n) { CountingSort(A, n); // 利用計(jì)數(shù)排序確定各個(gè)桶的邊界（分桶） for (int i = 0; i < bn; i++) // 對每一個(gè)桶中的元素應(yīng)用插入排序 { int left = C[i]; // C[i]為i號桶第一個(gè)元素的位置 int right = (i == bn - 1 ? n - 1 : C[i + 1] - 1);// C[i+1]-1為i號桶最后一個(gè)元素的位置 if (left < right) // 對元素個(gè)數(shù)大于1的桶進(jìn)行桶內(nèi)插入排序 InsertionSort(A, left, right); } } int main() { int A[] = { 29, 25, 3, 49, 9, 37, 21, 43 };// 針對桶排序設(shè)計(jì)的輸入 int n = sizeof(A) / sizeof(int); BucketSort(A, n); printf("桶排序結(jié)果："); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); return 0; }
下圖給出了對{ 29, 25, 3, 49, 9, 37, 21, 43 }進(jìn)行桶排序的簡單演示過程
桶排序不是比較排序，不受到O(nlogn)下限的影響，它是鴿巢排序的一種歸納結(jié)果，當(dāng)所要排序的數(shù)組值分散均勻的時(shí)候，桶排序擁有線性的時(shí)間復(fù)雜度。
如對本文有疑問，請?zhí)峤坏浇涣髡搲?，廣大熱心網(wǎng)友會(huì)為你解答！！ 點(diǎn)擊進(jìn)入論壇
