计数排序(counting sort)

计算排序是一种通过计算每个元素出现的次数来进行排序的算法。它不比较元素，而是利用数组来“计数”，所以在某些情况下，它能比传统的比较排序快。

计数排序首先要找到要排序数组的最大值，然后创建一个统计数组存储每个排序元素的出现次数，然后累加计数数组，根据计数数组来确定每个元素的位置。

以一个实际例子来看，假设待排序数组：{2,8,7,6,4,5,2,8,5}

统计每个元素出现次数

要记录元素的统计次数，这里要创建一个统计数组用来记录次数，由于要记录每个元素的次数，所以要先找到元素的最大值来确定统计数组的容量，这里最大值是8，所以要创建一个 8+1长度的统计数组来存储元素记录数。考虑元素为0的情况。

最后统计数组结果如下：

这里统计数组下标待排序元素值，数组中值代表该元素出现次数。

累加统计数组

这里累加就是将统计数组总的当前位置索引值改为前面所有统计数的和。

这一步其实就是确定每个元素的大致位置，只不过由于有相同的元素还需要进行微调。

这里从统计数组头开始具体看，其实可以理解成排名次，首先 0和1出现次数都是0直接舍弃，接着2出现了两次，前两名就是2个2，3

确定元素位置

上面计数数组累加完成后，大致顺序已经出来了，只不过有相同元素存在导致元素具体位置存在空档和重复。

最后元素排序后的位置需要定义一个新的数组来存储，元素的位置还是

这一步就需要根据统计数组中的累加值来计算，计数数组中的累加值当对应位置元素被拿出一次后，当前位置累加数-1，便于下次在取的时候位置错开。

原数组 {2,8,7,6,4,5,2,8,5}

一次根据计数类加数确定位置

最后确定每个元素在输出数组中的位置，排序也完成了。

代码实现

public static int[] sort(int[] arr){
	//1、找到数组最大值
	int max = arr[0];
	for (int i = 1; i < arr.length; i++) {
		if(arr[i] > max) max = arr[i];
	}

	//2、创建计数数组,数组长度 max+1，要存储所有可能元素计数，+1是考虑有元素0的情况
	int[] countArr = new int[max+1];
	//初始化
	for (int i = 0; i < countArr.length; i++) {
		countArr[i] = 0;
	}
	/**
	 * 元素计数，这里 countArr：下标是排序数组元素，值是当前这个数出现的次数
	 */
	for (int i = 0; i < arr.length; i++) {
		countArr[arr[i] ] += 1;
	}

	/**
	 * 累加计数 ，这里是将计数数组的值依次累加，这样就能知道每个元素（排序数组下标）对应的排序位置
	 */
	for (int i = 1; i < countArr.length; i++) {
		countArr[i] += countArr[i-1];
	}

	/**
	 * 构建输出数组
	 * 根据当前元素累加值确定输出数组位置，每次拿出一个，原来对应位置累加值-1
	 */
	int[] outArr = new int[arr.length];
	for (int i = 0; i < arr.length; i++) {
		outArr[ countArr[arr[i]]-1 ] = arr[i];
		countArr[arr[i]]--;
	}
	return outArr;
}

计数排序巧妙的运用了一个计数数组，每个元素值作为计数数组的下标来存取值。上面排序过程中也看到虽然没有进行排序比较，但是过程中创建了两个数组来存储计数和输出结果，空间复杂度提高。是一种用空间换时间的排序方式。

计算排序适合用于数组元素范围不大（例如 0 到 1000）。对于大量具有相同值的元素的排序。值的范围太大会造成计数数组空间偏大。如果排序中元素最小值较大，计数数组长度可以取为[最小值,最大值],元素下标统一偏移最小值即可。这样节省了最小值个数组长度空间。