一、定義

計(jì)數(shù)排序，這種排序算法是利用數(shù)組下標(biāo)來(lái)確定元素的正確位置的。

二、思路

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

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

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

下面就開(kāi)始遍歷這個(gè)無(wú)序的隨機(jī)數(shù)列，每一個(gè)整數(shù)按照其值對(duì)號(hào)入座，

同時(shí)，對(duì)應(yīng)數(shù)組下標(biāo)的元素進(jìn)行加1操作。

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

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

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

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

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

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

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

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

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

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

比如，分?jǐn)?shù)排序： 95，94，91，98，99，90，99，93，91，92 ，數(shù)組起始數(shù)為90，這樣數(shù)組前面的位置就浪費(fèi)了。可以采用偏移量的方式：

三、代碼實(shí)現(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 {
        // 對(duì) arr 進(jìn)行拷貝，不改變參數(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ù)雜度

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

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

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