什么是计数排序？
计数排序、基数排序、桶排序，这几种排序算法，可能大家见到的这次不多，有些大学的教材课本中，甚至有些都没有计数排序算法。
所以呢，帅地今天就简单讲一讲计数排序算法吧，而不会像前面一样长篇大论，因为我觉得，每一个学习计数排序的，应该都是有一定的算法基础了，而对于计数排序，我觉得大家掌握最基本的思想就可以了，平时做算法题的时候，还是会偶尔用到。
当然，计数排序如果要深入讲解，其实也是可以比较复杂的，但是这里，帅地只讲最简洁的，因为我觉得了解了基础的，就差不多了。
举个例子，假如我要给如下这个数组排序，你会如何排序呢？
输入 arr[] = {9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9 ，7，9}。
如果用快速排序，归并排序等这些排序算法的话，那么他们的时间复杂度其实是 O(nlogn)。
那么有没有一种方法，使得它的时间复杂度是 O(n) 呢？
答是有的，那便是计数排序。
计数排序的基本思想是这样的：把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。
例如对于上面那个例子，我们可以创建一个数组大小为 11 的临时数组 temp
因为数组的最大值是 10，所以临时数组的最大下标为 10 即可。
然后遍历数组，第一个整数是9，那么数组下标为9的元素加1：
第二个整数是3，那么数组下标为3的元素加1：
最终，数列遍历完毕时，数组的状态如下：
之后我们只需要遍历临时数组 temp，输出临时数组元素的下标值即可，元素的值是几，就输出几次，结果如下：
0，1，1，2，3，3，3，4，4，5，5，6，7，7，8，9，9，9，9，10
显然，这个输出的数列已经是有序的了。
Java 代码如下（代码会做详细的注释）
public static int[] countSort(int[] arr) {
if(arr == null || arr.length < 2) return arr;
int n = arr.length;
int max = arr[0];
// 寻找数组的最大值，该值用来创建临时数组用的
for (int i = 1; i < n; i++) {
if(max < arr[i])
max = arr[i];
}
//创建大小为max + 1的临时数组
int[] temp = new int[max + 1];
//统计元素i出现的次数
for (int i = 0; i < n; i++) {
temp[arr[i]]++;
}
int k = 0;
//把临时数组统计好的数据汇总到原数组
for (int i = 0; i <= max; i++) {
// temp[i] 的值表示元素 i 出现的次数
for (int j = temp[i]; j > 0; j--) {
arr[k++] = i;
}
}
return arr;
}
优化一下
上面的代码中，我们是根据 max 的大小来创建对应大小的数组，假如原数组只有 10 个元素，并且最小值为 min = 10000，最大值为 max = 10005，那我们创建 10005 + 1 大小的数组不是很吃亏？最大值与最小值的差值为 5，所以我们创建大小为 6 的临时数组就可以了，这样可以节省空间浪费
也就是说，我们创建的临时数组大小 (max – min + 1)就可以了，然后我们再把 min作为偏移量。优化之后的代码如下所示：
public static int[] sort(int[] arr) {
if(arr == null || arr.length < 2) return arr;
int n = arr.length;
int min = arr[0];
int max = arr[0];
// 寻找数组的最大值与最小值
for (int i = 1; i < n; i++) {
if(max < arr[i])
max = arr[i];
if(min > arr[i])
min = arr[i];
}
int d = max - min + 1;
//创建大小为max的临时数组
int[] temp = new int[d];
//统计元素i出现的次数
for (int i = 0; i < n; i++) {
temp[arr[i] - min]++;
}
int k = 0;
//把临时数组统计好的数据汇总到原数组
for (int i = 0; i < d; i++) {
// temp[i] 的值表示元素 i 出现的次数
for (int j = temp[i]; j > 0; j--) {
arr[k++] = i + min;
}
}
return arr;
}
我这里还给大家准备了一个动画，大家看看就好
有人可能会问，如果数组只有十个元素，最小值为 min = 0，最大值 max = 1000000。那我不是得创建一个 大小为 1000000 的数组？
或者说，如果我数组中有浮点数，那不就是无法作为下标来使用了？
别问，问就是，每一种排序算法都有它的局限性，不然还用啥快速排序，目前用的最广的感觉还是快速排序，想计数排序这种，适用特定领域数据下的排序，例如最大值和最小值的差值不是很大的整数数组。