最近面試了一些人，發現大家都忽略了排序算法中的計數排序、桶排序和基數排序，segmentfault中都沒有它們的标簽就是一明證，呵呵！
計數排序
當輸入的元素是 n 個 0 到 k 之間的整數時，它的運作時間是 Θ(n + k)。計數排序不是比較排序，排序的速度快于任何比較排序算法。
由于用來計數的數組C的長度取決于待排序數組中資料的範圍（等于待排序數組的最大值與最小值的差加上1），這使得計數排序對于資料範圍很大的數組，需要大量記憶體。計數排序是用來排序0到100之間的數字的最好的算法，但是它不适合按字母順序排序人名。但是，計數排序可以用在基數排序中的算法來排序資料範圍很大的數組。
算法的步驟如下：
- 找出待排序的數組中最大和最小的元素
- 統計數組中每個值為i的元素出現的次數，存入數組C的第i項
- 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）
- 反向填充目标數組：将每個元素i放在新數組的第C(i)項，每放一個元素就将C(i)減去1
#define NUM_RANGE (100) //預定義資料範圍上限，即K的值
void counting_sort(int *ini_arr, int *sorted_arr, int n) //所需空間為 2*n+k
{
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]]++;
}
//統計數組計數，每項存前N項和，這實質為排序過程
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);
}
桶排序
我的了解：
桶排序是計數排序的變種，把計數排序中相鄰的m個"小桶"放到一個"大桶"中，在分完桶後，對每個桶進行排序（一般用快排），然後合并成最後的結果。
基本思想：
桶排序假設序列由一個随機過程産生，該過程将元素均勻而獨立地分布在區間[0,1)上。我們把區間[0,1)劃分成n個相同大小的子區間，稱為桶。将n個記錄分布到各個桶中去。如果有多于一個記錄分到同一個桶中，需要進行桶内排序。最後依次把各個桶中的記錄列出來記得到有序序列。
效率分析：
桶排序的平均時間複雜度為線性的O(N+C)，其中C為桶内快排的時間複雜度。如果相對于同樣的N，桶數量M越大，其效率越高，最好的時間複雜度達到O(N)。 當然桶排序的空間複雜度 為O(N+M)，如果輸入資料非常龐大，而桶的數量也非常多，則空間代價無疑是昂貴的。此外，桶排序是穩定的。
基數排序
基本思想：
将待排資料中的每組關鍵字依次進行桶配置設定。
具體示例：
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個左右。
但是，對比桶排序，基數排序每次需要的桶的數量并不多。而且基數排序幾乎不需要任何“比較”操作，而桶排序在桶相對較少的情況下，桶内多個資料必須進行基于比較操作的排序。是以，在實際應用中，基數排序的應用範圍更加廣泛。
![初級銀行從業資格證有什麼用？[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)