什么是计数排序？

计数排序、基数排序、桶排序，这几种排序算法，可能大家见到的这次不多，有些大学的教材课本中，甚至有些都没有计数排序算法。

所以呢，帅地今天就简单讲一讲计数排序算法吧，而不会像前面一样长篇大论，因为我觉得，每一个学习计数排序的，应该都是有一定的算法基础了，而对于计数排序，我觉得大家掌握最基本的思想就可以了，平时做算法题的时候，还是会偶尔用到。

当然，计数排序如果要深入讲解，其实也是可以比较复杂的，但是这里，帅地只讲最简洁的，因为我觉得了解了基础的，就差不多了。

举个例子，假如我要给如下这个数组排序，你会如何排序呢？

输入 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;}