计数排序

基本思想

核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数

算法步骤

知道待排序数组的范围，开辟新数组空间
遍历待排序数组元素，值为k，则新数组第k项+1
遍历新数组，输出所有值

动图演示

countingSort.gif
代码实现

    public static void countingSort(int[] arr, int max) {
        if (null == arr || arr.length < 1) return;

        int[] resultTemp = new int[max + 1];
        for (int value : arr) {
            resultTemp[value]++;
        }

        int index = 0;
        for (int i = 0; i <= max; i++) {
            while (resultTemp[i]-- > 0) {
                arr[index++] = i;
            }
        }
    }

时间复杂度分析

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。
当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

优化

其缺点也是显而易见的，当k很大，且数据比较分散时，会占用较大无用空间，十分浪费，桶排序、基数排序都是对其的优化。