一、定義

計數(shù)排序，這種排序算法是利用數(shù)組下標來確定元素的正確位置的。

二、思路

假設(shè)數(shù)組中有10個整數(shù)，取值范圍為0～10，要求用最快的速度把這10個整數(shù)從小到大進行排序。

可以根據(jù)這有限的范圍，建立一個長度為11的數(shù)組。數(shù)組下標從0到10，元素初始值全為0。

假設(shè)數(shù)組數(shù)據(jù)為：9，1，2，7，8，1，3，6，5，3 。

下面就開始遍歷這個無序的隨機數(shù)列，每一個整數(shù)按照其值對號入座，

同時，對應(yīng)數(shù)組下標的元素進行加1操作。

例如第1個整數(shù)是9，那么數(shù)組下標為9的元素加1。

最終，當數(shù)列遍歷完畢時，數(shù)組的狀態(tài)如下：

該數(shù)組中每一個下標位置的值代表數(shù)列中對應(yīng)整數(shù)出現(xiàn)的次數(shù)。

直接遍歷數(shù)組，輸出數(shù)組元素的下標值，元素的值是幾，就輸出幾次，0不輸出。

則順序輸出是：1、1、2、3、3、5、6、7、8、9。

計數(shù)排序：計數(shù)排序只能用在數(shù)據(jù)范圍不大的場景中，如果數(shù)據(jù)范圍k比要排序的數(shù)據(jù)n大很多，就不適合用計數(shù)排序了。

而且，計數(shù)排序只能給非負整數(shù)排序，如果要排序的數(shù)據(jù)是其他類型的，要將其在不改變相對大小的情況下，轉(zhuǎn)化為非負整數(shù)。

如果起始數(shù)不是從0開始，為了不浪費空間，可以采用偏移量的方式解決。

比如，如果考生最低成績0分，最高900分，但成績要精確到小數(shù)后一位，我們就需要將所有的分數(shù)都先乘以10，轉(zhuǎn)化成整數(shù)，然后再放到9010個桶內(nèi)。

比如，如果要排序的數(shù)據(jù)中有負數(shù)，數(shù)據(jù)的范圍是[-1000, 1000]，那我們就需要先對每個數(shù)據(jù)都加1000，轉(zhuǎn)化成非負整數(shù)。

比如，分數(shù)排序： 95，94，91，98，99，90，99，93，91，92 ，數(shù)組起始數(shù)為90，這樣數(shù)組前面的位置就浪費了?？梢圆捎闷屏康姆绞剑?/p>

三、代碼實現(xiàn)

import java.util.Arrays;

public class CountingSort{

    public static void main(String[] args) throws Exception {
        int[] scores = {9, 3, 4, 9, 1, 2, 7, 8,1,3, 3, 4, 0, 10, 9, 7, 9};
        for (int n : sort(scores)) {
            System.out.println(n);
        }
    }

    public static int[] sort(int[] sourceArray) throws Exception {
        // 對 arr 進行拷貝，不改變參數(shù)內(nèi)容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
                //
        int maxValue = getMaxValue(arr);

        return countingSort(arr, maxValue);
    }

    private static int[] countingSort(int[] arr, int maxValue) {
        int bucketLen = maxValue + 1;
        int[] bucket = new int[bucketLen];

        for (int value : arr) {
            bucket[value]++;
        }

        int sortedIndex = 0;
        for (int j = 0; j < bucketLen; j++) {
            while (bucket[j] > 0) {
                arr[sortedIndex++] = j;
                bucket[j]--;
            }
        }
        return arr;
    }

    private static int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }
}

四、復(fù)雜度

時間復(fù)雜度是O(n+m) n: 數(shù)據(jù)個數(shù) m: 數(shù)據(jù)范圍；

空間復(fù)雜度是O(m)；

穩(wěn)定性：穩(wěn)定排序。