对数组 [4,1,5,0,8,3,7,5,1] 进行排序，我们可以开辟一大小为10的辅组数组空间help[10]，初值均为0。扫描数组，扫描到4，help[4]+1；扫描到1，help[1]+1；扫描到5，……。最后整个help数组是[1,2,0,1,1,2,0,1,1,0]。扫描help数组，元素非0代表着与下标值相同的这个数存在，个数等于元素值，能得到排序结果： [0,1,1,3,4,5,5,7,8]。
计数排序就是这种不基于比较的排序，只不过对上面举例的方法进行了更进一步改进。
算法描述
- 找出待排序数组中的最大值Max和最小值Min，构建大小为 Max-Min+1 辅助数组 help[]
- 统计待排序数组中每个值为 i 的元素出现的次数，存入辅助数组 help 的第 i-Min 位置
- help[i] 累加其之前所有计数，也即从第二项开始 help[i] += help[i-1]
- 反向遍历原始数组，扫描到值 i 时，根据 help[i-Min] 找到 i 在结果数组应该排在第几位。
限制：输入的元素必须要属于有限集合。
时间复杂度为O(n+k)，空间复杂度为O(n+k)。n为待排序数组的规模，k为辅助数组的规模。
例如在上面的例子中[4,1,5,0,8,3,7,5,1]的最大值为8，最小值是0，可以构建大小为9的辅助数组help，统计值次数后，help数组为[1,2,0,1,1,2,0,1,1]，累加计数后help数组为[1,3,3,4,5,7,7,8,9]。下面详细描述反向遍历原始数组过程：
- 扫描到值 1 时，help[1-0] = 3，help[1-0]--，help数组为[1,2,3,4,5,7,7,8,9]，1 排在结果数组的第3个位置；
- 扫描到值 5 时，help[5-0] = 7，help[5-0]--，help数组为[1,2,3,4,5,6,7,8,9]，5 排在结果数组的第7个位置；
- 扫描到值 7 时，help[7-0] = 8，help[7-0]--，help数组为[1,2,3,4,5,6,7,7,9]，7 排在结果数组的第8个位置；
- 扫描到值 3 时，help[3-0] = 4，help[3-0]--，help数组为[1,2,3,3,5,6,7,7,9]，3 排在结果数组的第4个位置；
- 扫描到值 8 时，help[8-0] = 9，help[8-0]--，help数组为[1,2,3,3,5,6,7,7,8]，8 排在结果数组的第9个位置；
- 扫描到值 0 时，help[0-0] = 1，help[0-0]--，help数组为[0,2,3,3,5,6,7,7,8]，0 排在结果数组的第1个位置；
- 扫描到值 5 时，help[5-0] = 6，help[5-0] --，help数组为[0,2,3,3,5,5,7,7,8]，5 排在结果数组的第6个位置；
- 扫描到值 1 时，help[1-0] = 2，help[1-0] --，help数组为[0,1,3,3,5,5,7,7,8]，1 排在结果数组的第2个位置；
- 扫描到值 4 时，help[4-0] = 5，help[4-0] --，help数组为[0,1,3,3,4,5,7,7,8]，4 排在结果数组的第5个位置；
结果数组为[0,1,1,3,4,5,5,7,8]。
Java代码实现
public class CountSort{
public static int[] countSort(int[]arr){
int[] res = new int[arr.length]; //结果数组
//求最大值和最小值
int max = arr[0],min = arr[0];
for(int value : arr){
if(value > max){
max = value;
}
if(value < min){
min = value;
}
}
int k= max - min + 1;
int[] help=new int[k];
for (int value : arr) {
help[value - min] += 1;
}
//累加计数
for(int i=1; i < help.length; ++i){
help[i]=help[i] + help[i-1];
}
//反向遍历
for(int i= arr.length-1; i >= 0; --i){
res[--help[arr[i] - min]]= arr[i];
}
return res;
}
}
小结
计数排序是一种空间换时间的算法，优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法，但当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序。要求排序元素的取值要在一定范围内，并且比较集中，其有限偏序集不能太大，才能发挥出计数排序的优势。