本文内容和代码来自《漫画算法》 之前练习的冒泡排序、鸡尾酒排序、快速排序、堆排序都是基于元素比较和位置元素交换实现的，有一些特殊的排序并不基于元素比较，如计数排序、桶排序、基数排序。 以计数排序来说，这种排序算法是利用数组下标来确定元素的正确位置的。 来看一个例子： 假设有20个随机整数，取值范围0-10，要求用最快的速度把这20个整数从小到大进行排序 建立一个长度为11的数组，下标0-10，元素全为0。 假设20个数字如下所示 9,3,5,4,9,1,2,7,8,1,3,6,5,3,4,0,10,9,7,9 下面遍历这个20个元素的数字序列，每一个整数按其值对号入座，同时数组下标的元素进行加1操作。 例如第一个整数是9，那么下标为9的元素加1。 第二个整数是3，那么下标为3的元素加1。 继续遍历并修改数组… 最终当数列修改完毕，数组的状态如下。 该数组的每一个下标位置的值代表数列中对应整数出现的次数。有了这个统计结果，排序就很简单了。直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次。 0 1 1 2 3 3 3 4 4 5 5 6 7 7 8 9 9 9 9 10 显然，现在输出的数列已经是有序的了。 这就是计数排序的基本过程，它适用于一定范围内的整数排序。在取值范围不是很大的情况下，它的性能甚至快过那些时间复杂度为O(nlogn)的排序。
后面还有很多图片，就不比着书画了。最主要的还有当有重复数据的时候涉及到的一个顺序的处理。还是看一下原书，更好理解一点。除了重复数据顺序的问题，还有一个就是无需序列不从0开始的情况的处理。 最终的java实现如下
int[] countSort(int[] arr) { // 1.得到数组的最大值、最小值，并算出差值d int max = 0, min = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } if (arr[i] < min) { min = arr[i]; } } int d = max - min; // 2.创建统计数组并统计对应元素的个数 int[] countArr = new int[d + 1]; for (int i = 0; i < arr.length; i++) { countArr[arr[i] - min]++; } // 3.统计数组变形，后面的元素等于前面的元素之和 for (int i = 1; i < countArr.length; i++) { countArr[i] += countArr[i - 1]; } // 4.倒序遍历原始数组，从统计数组找到正确的位置，输出到结果数组 int[] sortedArr = new int[arr.length]; for (int i = arr.length - 1; i >= 0; i--) { sortedArr[countArr[arr[i] - min] - 1] = arr[i]; countArr[arr[i] - min]--; } return sortedArr; } @Test public void fun1() { // int[] arr=new int[]{95,94,91,98,99,90,99,93,91,92}; int[] arr = new int[] { 49, 38, 65, 97, 76, 13, 27, 49 }; int[] sortedArr = countSort(arr); System.out.println(Arrays.toString(sortedArr)); }操作原始数组运算量n，操作统计数列运算量为m 时间复杂度O(n+m) 不考虑结果数组和统计数组， 空间复杂度O(m) 它的时间复杂度是线性级的，然而它的局限性也非常严重 1.当数列最大和最小值差距过大时，并不适合用计数排序 例如给出20个随机整数，范围在0到1亿之间，需要创建1亿个元素的数组，不但严重浪费空间，而且时间复杂度也会随之升高。 2.当数列元素不是整数时，也不适合用计数排序 如果数列中的元素都是小数，如25.213，或0.00 000 001这样的数字，则无法创建对应的统计数组。这样显然无法进行计数排序。
