1. 简介

先举个例子

• 假设现在有个数组

[1,1,2,6,0,4]

如果我们不关心这个数组中的顺序, 除了上面的表达方式, 我们还可以用什么办法表示它呢?

• 我们可以列一个表格

• 这个表格充分表达了数组中有哪些元素

这个表格能简化吗?

我们可以用一个数组来描述上面这个表格

[1,2,1,0,1,0,1]
//数组的下标表示表格的第一行, 数组中的数字表示表格的第二行
//[1个,2个,1个,0个,1个,0个,1个]

• 是不是有感觉了?

2. 实现

实现思路

1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

Java实现

public static int[] sort(int[] arr)   {
    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;
}

3. 分析

设:

• 元素个数为n
• 数字最大值为k

时间复杂度

• 时间复杂度 = O(n+k)

空间复杂度

• 时间复杂度 = O(k)

总结

计数排序不是比较排序，排序的速度快于任何比较排序算法。但由于其与数字最大值k相关, 所以当K很大的时候计数排序就不太适用, 会极大的浪费内存和时间, 例如对时间戳排序