簡介
今天我們介紹一種不需要作比較就能排序的算法：count排序。
count排序是一種空間換時間的算法，我們借助一個外部的count數組來統計各個元素出現的次數，進而最終完成排序。
count排序的例子
count排序有一定的限制，因為外部的count數組長度是和原數組的元素範圍是一緻的，是以count排序一般隻适合數組中元素範圍比較小的情況。
我們舉一個0-9的元素的排序的例子：3,4,2,5,6,2,4,9,1,3,5。
先看一個動畫，看看是怎麼排序的：
count數組裡面存放的是從0到9這些元素出現的次數。
我們周遊原始數組，遇到相應的數字就給相應的count+1。
等所有的元素都count之後，再根據count數組中的值還原排序過後的數組。
count排序的java實作
count排序很簡單，我們主要掌握下面兩個大的步驟：
- 周遊原始數組，建構count數組。
- 根據count數組中的count值，重新建構排序數組。
public class CountingSort {
public void doCountingSort(int[] array){
int n = array.length;
// 存儲排序過後的數組
int output[] = new int[n];
// count數組，用來存儲統計各個元素出現的次數
int count[] = new int[10];
for (int i=0; i<10; ++i) {
count[i] = 0;
}
log.info("初始化count值:{}",count);
// 将原始數組中資料出現次數存入count數組
for (int i=0; i<n; ++i) {
++count[array[i]];
}
log.info("count之後count值:{}",count);
//周遊count，将相應的資料插入output
int j=0;
for(int i=0; i<10; i++){
while(count[i]-- > 0){
output[j++]=i;
}
}
log.info("建構output之後的output值:{}",output);
//将排序後的數組寫回原數組
for (int i = 0; i<n; ++i)
array[i] = output[i];
}
public static void main(String[] args) {
int[] array= {3,4,2,5,6,2,4,9,1,3,5};
CountingSort countingSort=new CountingSort();
log.info("countingSort之前的數組為:{}",array);
countingSort.doCountingSort(array);
}
} 上面的注釋應該很清楚了。
運作的結果如下：
count排序的第二種方法
在我們獲得count數組中每個元素的個數之後，其實我們還有另外一個生成結果數組的辦法：
// 這裡是一個小技巧，我們根據count中元素出現的次數計算對應元素第一次應該出現在output中的下标。
//這裡的下标是從右往左數的
for (int i=1; i<10; i++) {
count[i] += count[i - 1];
}
log.info("整理count對應的output下标:{}",count);
// 根據count中的下标，建構排序後的數組
//插入一個之後，相應的count下标要減一
for (int i = n-1; i>=0; i--)
{
output[count[array[i]]-1] = array[i];
--count[array[i]];
}
log.info("建構output之後的output值:{}",output); 主要分為兩步:
第一步我們根據count中元素出現的次數計算對應元素第一次應該出現在output中的下标。這裡的下标是從右往左數的。
第二步根據count中的下标，建構排序後的數組，插入一個之後，相應的count下标要減一。
可能不是很好了解，大家可以結合輸出結果反複琢磨一下。
count排序的時間複雜度
從上面的代碼我們可以看到，count排序實際上隻做了少量次數的周遊。是以它的時間複雜度是O(n)。
本文的代碼位址：
learn-algorithm本文已收錄于 http://www.flydean.com/algorithm-count-sort/最通俗的解讀，最深刻的幹貨，最簡潔的教程，衆多你不知道的小技巧等你來發現！
歡迎關注我的公衆号:「程式那些事」,懂技術，更懂你！