計數排序、桶排序和基數排序

計數排序

當輸入的元素是 n 個 0 到 k 之間的整數時，它的運行時間是 Θ(n?+?k)。計數排序不是比較排序，排序的速度快于任何比較排序算法。

由于用來計數的數組C的長度取決于待排序數組中數據的范圍（等于待排序數組的最大值與最小值的差加上1），這使得計數排序對于數據范圍很大的數組，需要大量時間和內存。例如：計數排序是用來排序0到100之間的數字的最好的算法，但是它不適合按字母順序排序人名。但是，計數排序可以用在基數排序中的算法來排序數據范圍很大的數組。

算法的步驟如下：

1. 找出待排序的數組中最大和最小的元素
2. 統計數組中每個值為i的元素出現的次數，存入數組C的第i項
3. 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）
4. 反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1

貼上代碼：

#include?<stdio.h>??
#include?<stdlib.h>??
#include?<time.h>??
??
//對于排序的關鍵字范圍，一定是0-99??
#define?NUM_RANGE?(100)??
??
void?print_arr(int?*arr,?int?n)??
{??
???????int?i;??
???????for(i=0;?i<n;?i++){??
???????????????if(!i){??
???????????????????????printf(“%d”,?arr[i]);??
???????????????}else{??
???????????????????????printf(“?%d”,?arr[i]);??
???????????????}??
???????}??
???????printf(“\n”);??
}??
??
/*??
算法的步驟如下：??
????1.找出待排序的數組中最大和最小的元素??
????2.統計數組中每個值為i的元素出現的次數，存入數組C的第i項??
????3.對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）??
????4.反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1??
*/??
??
void?counting_sort(int?*ini_arr,?int?*sorted_arr,?int?n)??
{??
???????int?*count_arr?=?(int?*)malloc(sizeof(int)?*?NUM_RANGE);??
???????int?i,?j,?k;??
??
???????//統計數組中，每個元素出現的次數??
???????for(k=0;?k<NUM_RANGE;?k++){??
???????????????count_arr[k]?=?0;??
???????}??
?????????
???????for(i=0;?i<n;?i++){??
???????????????count_arr[ini_arr[i]]++;??
???????}??
??
??
???????for(k=1;?k<NUM_RANGE;?k++){??
???????????????count_arr[k]?+=?count_arr[k-1];??
???????}??
??
???????for(j=n-1?;?j>=0;?j–){??
???????????int?elem?=?ini_arr[j];??
???????????int?index?=?count_arr[elem]-1;??
???????????sorted_arr[index]?=?elem;??
???????????count_arr[elem]–;??
???????}??
???????free(count_arr);??
}??
??
??
int?main(int?argc,?char*?argv[])??
{??
???????int?n;??
???????if(argc?<?2){??
???????????????n?=?10;??
???????}else{??
???????????????n?=?atoi(argv[1]);??
???????}??
???????int?i;??
???????int?*arr?=?(int?*)malloc(sizeof(int)?*?n);??
???????int?*sorted_arr?=?(int?*)malloc(sizeof(int)?*n);??
???????srand(time(0));??
??
?????????
???????for(i=0;?i<n;?i++){??
???????????????arr[i]?=?rand()?%?NUM_RANGE;??
???????}??
??
???????printf(“ini_array:?”);??
???????print_arr(arr,?n);??
???????counting_sort(arr,?sorted_arr,?n);??
???????printf(“sorted_array:?”);??
???????print_arr(sorted_arr,?n);??
???????free(arr);??
???????free(sorted_arr);??
???????return?0;??
}??

#include <stdio.h>

#include <stdlib.h> #include <time.h> //對于排序的關鍵字范圍，一定是0-99 #define NUM_RANGE (100) void print_arr(int *arr, int n) { int i; for(i=0; i<n; i++){ if(!i){ printf("%d", arr[i]); }else{ printf(" %d", arr[i]); } } printf("\n"); } /* 算法的步驟如下： 1.找出待排序的數組中最大和最小的元素 2.統計數組中每個值為i的元素出現的次數，存入數組C的第i項 3.對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加） 4.反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1 */ void counting_sort(int *ini_arr, int *sorted_arr, int n) { int *count_arr = (int *)malloc(sizeof(int) * NUM_RANGE); int i, j, k; //統計數組中，每個元素出現的次數 for(k=0; k<NUM_RANGE; k++){ count_arr[k] = 0; } for(i=0; i<n; i++){ count_arr[ini_arr[i]]++; } for(k=1; k<NUM_RANGE; k++){ count_arr[k] += count_arr[k-1]; } for(j=n-1 ; j>=0; j--){ int elem = ini_arr[j]; int index = count_arr[elem]-1; sorted_arr[index] = elem; count_arr[elem]--; } free(count_arr); } int main(int argc, char* argv[]) { int n; if(argc < 2){ n = 10; }else{ n = atoi(argv[1]); } int i; int *arr = (int *)malloc(sizeof(int) * n); int *sorted_arr = (int *)malloc(sizeof(int) *n); srand(time(0)); for(i=0; i<n; i++){ arr[i] = rand() % NUM_RANGE; } printf("ini_array: "); print_arr(arr, n); counting_sort(arr, sorted_arr, n); printf("sorted_array: "); print_arr(sorted_arr, n); free(arr); free(sorted_arr); return 0; }

?桶排序：http://blog.sina.com.cn/s/blog_667739ba0100veth.html

桶排序的基本思想

假設有一組長度為N的待排關鍵字序列K[1….n]。首先將這個序列劃分成M個的子區間(桶) 。然后基于某種映射函數 ，將待排序列的關鍵字k映射到第i個桶中(即桶數組B的下標 i) ，那么該關鍵字k就作為B[i]中的元素(每個桶B[i]都是一組大小為N/M的序列)。接著對每個桶B[i]中的所有元素進行比較排序(可以使用快排)。然后依次枚舉輸出B[0]….B[M]中的全部內容即是一個有序序列。

假如待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。這些數據全部在1—100之間。因此我們定制10個桶，然后確定映射函數f(k)=k/10。則第一個關鍵字49將定位到第4個桶中(49/10=4)。依次將所有關鍵字全部堆入桶中，并在每個非空的桶中進行快速排序。

桶排序代價分析

桶排序利用函數的映射關系，減少了幾乎所有的比較工作。實際上，桶排序的f(k)值的計算，其作用就相當于快排中劃分，已經把大量數據分割成了基本有序的數據塊(桶)。然后只需要對桶中的少量數據做先進的比較排序即可。

?

對N個關鍵字進行桶排序的時間復雜度分為兩個部分：

(1)?循環計算每個關鍵字的桶映射函數，這個時間復雜度是O(N)。

(2) 利用先進的比較排序算法對每個桶內的所有數據進行排序，其時間復雜度為 ∑ O(Ni*logNi) 。其中Ni 為第i個桶的數據量。

?

很顯然，第(2)部分是桶排序性能好壞的決定因素。盡量減少桶內數據的數量是提高效率的唯一辦法(因為基于比較排序的最好平均時間復雜度只能達到O(N*logN)了)。因此，我們需要盡量做到下面兩點：

(1) 映射函數f(k)能夠將N個數據平均的分配到M個桶中，這樣每個桶就有[N/M]個數據量。

(2) 盡量的增大桶的數量。極限情況下每個桶只能得到一個數據，這樣就完全避開了桶內數據的“比較”排序操作。 當然，做到這一點很不容易，數據量巨大的情況下，f(k)函數會使得桶集合的數量巨大，空間浪費嚴重。這就是一個時間代價和空間代價的權衡問題了。

?

對于N個待排數據，M個桶，平均每個桶[N/M]個數據的桶排序平均時間復雜度為：

O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

當N=M時，即極限情況下每個桶只有一個數據時。桶排序的最好效率能夠達到O(N)。

?

總結： 桶排序的平均時間復雜度為線性的O(N+C)，其中C=N*(logN-logM)。如果相對于同樣的N，桶數量M越大，其效率越高，最好的時間復雜度達到O(N)。 當然桶排序的空間復雜度 為O(N+M)，如果輸入數據非常龐大，而桶的數量也非常多，則空間代價無疑是昂貴的。此外，桶排序是穩定的。

我個人還有一個感受：在查找算法中，基于比較的查找算法最好的時間復雜度也是O(logN)。比如折半查找、平衡二叉樹、紅黑樹等。但是Hash表卻有O(C)線性級別的查找效率(不沖突情況下查找效率達到O(1))。大家好好體會一下：Hash表的思想和桶排序是不是有一曲同工之妙呢?

基數排序

上面的問題是多關鍵字的排序，但單關鍵字也仍然可以使用這種方式。

比如字符串“abcd” “aesc” “dwsc” “rews”就可以把每個字符看成一個關鍵字。另外還有整數 425、321、235、432也可以每個位上的數字為一個關鍵字。

?

基數排序的思想就是將待排數據中的每組關鍵字依次進行桶分配。比如下面的待排序列：

278、109、063、930、589、184、505、269、008、083

我們將每個數值的個位，十位，百位分成三個關鍵字： 278 -> k1(個位)=8 ，k2(十位)=7 ，k3=(百位)=2。

然后從最低位個位開始(從最次關鍵字開始)，對所有數據的k1關鍵字進行桶分配(因為，每個數字都是 0-9的，因此桶大小為10)，再依次輸出桶中的數據得到下面的序列。

930、063、083、184、505、278、008、109、589、269

再對上面的序列接著進行針對k2的桶分配，輸出序列為：

505、008、109、930、063、269、278、083、184、589

最后針對k3的桶分配，輸出序列為：

008、063、083、109、184、269、278、505、589、930

?

性能分析

很明顯，基數排序的性能比桶排序要略差。每一次關鍵字的桶分配都需要O(N)的時間復雜度，而且分配之后得到新的關鍵字序列又需要O(N)的時間復雜度。假如待排數據可以分為d個關鍵字，則基數排序的時間復雜度將是O(d*2N) ，當然d要遠遠小于N，因此基本上還是線性級別的。基數排序的空間復雜度為O(N+M)，其中M為桶的數量。一般來說N>>M，因此額外空間需要大概N個左右。

?

但是，對比桶排序，基數排序每次需要的桶的數量并不多。而且基數排序幾乎不需要任何“比較”操作，而桶排序在桶相對較少的情況下，桶內多個數據必須進行基于比較操作的排序。因此，在實際應用中，基數排序的應用范圍更加廣泛。