## **计数排序** 计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。 ## **算法描述** 1. 找出待排序的数组中最大和最小的元素； 2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项； 3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）； 4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。 ## **稳定性** 最后给 b 数组赋值是倒着遍历的，而且放进去一个就将C数组对应的值（表示前面有多少元素小于或等于A\[i\]）减去一。如果有相同的数x1,x2，那么相对位置后面那个元素x2放在（比如下标为4的位置），相对位置前面那个元素x1下次进循环就会被放在x2前面的位置3。从而保证了稳定性。 ## **适用场景** 排序目标要能够映射到整数域，其最大值最小值应当容易辨别。例如高中生考试的总分数，显然用0-750就OK啦；又比如一群人的年龄，用个0-150应该就可以了，再不济就用0-200喽。另外，计数排序需要占用大量空间，它比较适用于数据比较集中的情况。 ## **JAVA代码实现** ``` public static void countSort(int[] a, int max, int min) { int[] b = new int[a.length];//存储数组 int[] count = new int[max - min + 1];//计数数组 for (int num = min; num <= max; num++) { //初始化各元素值为0，数组下标从0开始因此减min count[num - min] = 0; } for (int i = 0; i < a.length; i++) { int num = a[i]; count[num - min]++;//每出现一个值，计数数组对应元素的值+1 } for (int num = min + 1; num <= max; num++) { //加总数组元素的值为计数数组对应元素及左边所有元素的值的总和 count[num - min] += sum[num - min - 1] } for (int i = 0; i < a.length; i++) { int num = a[i];//源数组第i位的值 int index = count[num - min] - 1;//加总数组中对应元素的下标 b[index] = num;//将该值存入存储数组对应下标中 count[num - min]--;//加总数组中，该值的总和减少1。 } //将存储数组的值一一替换给源数组 for(int i=0;i<a.length;i++){ a[i] = b[i]; } } ```