【算法】计数排序算法的讲解和代码实践

思路

计数排序是三个桶排序算法之一（计数排序、基数排序、桶排序），是不需要通过比较就可以对数组进行排序的一种算法。
计数排序的主要思路是：
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