核心思想

計數(shù)排序不是基于比較的排序算法思灰，算法的核心有3點：

1. 統(tǒng)計原數(shù)組中每個元素出現(xiàn)的次數(shù)茉盏。
2. 以原數(shù)組中的元素為下標(biāo)，元素出現(xiàn)的次數(shù)為值隔披，存入另一個計數(shù)數(shù)組中赃份。
3. 從下標(biāo)0開始遍歷計數(shù)數(shù)組，反向填充到目標(biāo)數(shù)組奢米。

時間復(fù)雜度和穩(wěn)定性

當(dāng)數(shù)組的元素是 n 個 0 到 m 之間的整數(shù)時抓韩，時間復(fù)雜度是O(n+m)，空間復(fù)雜度也是O(n+m)鬓长，其排序速度快于任何比較排序算法谒拴。
計數(shù)排序是一個很穩(wěn)定的排序算法。

適用范圍

由于計數(shù)數(shù)組的長度取決于原數(shù)組中最小元素和最大元素涉波，所以當(dāng)最小元素和最大元素之間的差值比較大時英上，計數(shù)數(shù)組將占用很大的存儲空間炭序。
因此計數(shù)排序算法僅適用于 元素值比較小、元素數(shù)量有限而且比較集中 的數(shù)組苍日。

Java 實現(xiàn)

注意點：
當(dāng)數(shù)組中的 元素 出現(xiàn) 負(fù)值 時惭聂，需要考慮負(fù)值元素如何正確地表示為計數(shù)數(shù)組的下標(biāo)：

• 根據(jù)數(shù)組中的最小值計算出一個偏移量（即負(fù)的最小值），計數(shù)數(shù)組的下標(biāo)=數(shù)組中的元素+偏移量相恃。
• 偏移量還有個好處是可以使計數(shù)數(shù)組從下標(biāo)0開始就存放有效數(shù)據(jù)辜纲。

import java.util.Arrays;

/**
 * 計數(shù)排序
 *
 * @author Alisallon
 * Created on 2021/6/5 9:38 上午.
 */
public class CountingSort {
    public static void main(String[] args) {
        int[] nums = {2, 3, 6, 8, 4, 2, 1, 8, 9, 4, 8, 0, 2, 3, 4, 9, 6, 5, 7, -3, -1, -7, -4, -9, -10, -5, -6};
        System.out.println(Arrays.toString(sort(nums)));
    }

    /**
     * 計數(shù)排序?qū)崿F(xiàn)
     *
     * @param nums 原數(shù)組
     * @return 排序后的數(shù)組
     */
    private static int[] sort(int[] nums) {
        // 找出原數(shù)組nums中最小值和最大值,用來確定計數(shù)數(shù)組bucket的長度和bucket索引的偏移量
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int a : nums) {
            min = Math.min(a, min);
            max = Math.max(a, max);
        }
        // 為了防止原數(shù)組中的元素a為負(fù)值的情況,所以需要計算偏移量
        // 即使元素a不可能出現(xiàn)負(fù)數(shù),該偏移量也能確保計數(shù)數(shù)組bucket從下標(biāo)0開始存放有效數(shù)據(jù),盡量使存儲空間更緊湊
        int offset = -min;
        // 統(tǒng)計數(shù)組nums中每個值為a的元素出現(xiàn)的次數(shù)，存入計數(shù)數(shù)組bucket的第a項
        int[] bucket = new int[max + offset + 1];
        for (int a : nums) {
            // 把計數(shù)數(shù)組bucket的第a項的計數(shù)累加
            // 為了防止原數(shù)組中的元素a為負(fù)值的情況(負(fù)數(shù)不能作為bucket的下標(biāo)),這時需要a減去偏移量變成不小于0的數(shù)
            // 即使元素a不可能出現(xiàn)負(fù)數(shù),該偏移量也能確保計數(shù)數(shù)組bucket從下標(biāo)0開始就存放有效數(shù)據(jù)
            bucket[a + offset]++;
        }
        // 從位置0開始循環(huán)計數(shù)數(shù)組bucket拦耐，把原值反向填充到原數(shù)組nums
        int index = 0;
        for (int i = 0; i < bucket.length; i++) {
            // 根據(jù)偏移量計算出原值
            int a = i - offset;
            // 把原值反向填充到原數(shù)組nums
            Arrays.fill(nums, index, index + bucket[i], a);
            index += bucket[i];
        }
        return nums;
    }
}