思路
计数排序是三个桶排序算法之一（计数排序、基数排序、桶排序），是不需要通过比较就可以对数组进行排序的一种算法。
计数排序的主要思路是：
1、新建一个数组，数组长度为原数组中最大的元素 + 1；
2、遍历原数组，将新数组下标等于原数组当前元素的值 + 1，也就是计数了；
3、遍历新数组，按下标依次取出所有元素值不为0的所有下标，并且元素值为几就取几次；
4、全部取出来就是排好序的数组。
另外说明一下计数排序的适用场景：
1、因为是使用数组下标 = 原数组值的形式计数的，所有原数组中的元素只能是大于等于0的数；
2、数组中的元素间隔越小越好。比如如果有一个数组是[1, 2, 99999]，这样的话，虽然只有3个元素，却需要创建一个100000大小的数组才能进行计数排序。
讲解
有数组如下：
image.png
我们先创建一个新的数组，长度为原数组中最大值 8 + 1：
image.png
然后开始遍历原数组，第一个数为 2，那么新数组下标 2 的值 + 1：
image.png
第二个元素为 0，新数组下标 0 的值 + 1：
image.png
以此类推，直到遍历完整个原数组，最终新数组如下：
image.png
这时候我们就可以遍历新数组，把所有下标取出，次数为下标对应的值。首先取出 0，0 对应的值为 1，取出一个即可：
image.png
1 也是同样的，只取出一个：
image.png
一直到下标 3 ，下标 3 的值为 2，需要取出两个：
image.png
后面的 4 和 7 下标对应的值为 0，不需要取。
直至取完所有元素，数组也就完成了排序：
image.png
实现
@Test
public void sortTest() {
int[] nums = new int[]{2, 0, 1, 8, 3, 3, 6, 5};
countSort(nums);
System.out.println(Arrays.toString(nums));
}
private void countSort(int[] nums) {
if (nums.length < 2) {
return;
}
// 为了确定新数组大小，先找出原数组最大值
int maxValue = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > maxValue) {
maxValue = nums[i];
}
}
// 定义新数组
int[] result = new int[maxValue + 1];
// 遍历原数组，将新数组下标对应的值 + 1
for (int i = 0; i < nums.length; i++) {
result[nums[i]] += 1;
}
// 将原数组作为结果数组，遍历并设值
for (int i = 0, j = 0; i < nums.length;) {
// 遍历新数组
for (; j < result.length; j++) {
// 遍历新数组中的某一个元素，遍历次数为该元素的值
for (int k = 0; k < result[j]; k++) {
// 取出下标设置到结果数组中
nums[i] = j;
i++;
}
}
}
}
看下运行结果：
image.png
