计数排序

本文内容和代码来自《漫画算法》
之前练习的冒泡排序、鸡尾酒排序、快速排序、堆排序都是基于元素比较和位置元素交换实现的，有一些特殊的排序并不基于元素比较，如计数排序、桶排序、基数排序。
以计数排序来说，这种排序算法是利用数组下标来确定元素的正确位置的。
来看一个例子：
假设有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这样的数字，则无法创建对应的统计数组。这样显然无法进行计数排序。