前言

计数排序是一种非基于比较的排序方法，在某些特定的场景中，使用计数排序的方式可以实现O(n+k)的时间复杂（k表示待排序的数据范围），比任何基于比较的排序方法都要快。

算法分析

1、给每一个数都准备一个存放的空间，一般可以用数组来记录。
2、然后对待排序的数据进行遍历，记录每一个数出现的次数，并放在对应的数组下标中。
3、最后从数组中以此遍历出来即可。

图解分析

假设原始待排序数据为：6，3，7，5，3，2，5

在这里插入图片描述

构建一个计数数组，大小等于原始数组取值的范围，假设待排序数据都是正整数，那么对于上面的待排序数组的取值范围就是0~8
在这里插入图片描述

以此记录每个位置对应值出现的次数
在这里插入图片描述

最后以此遍历计数数组即可

代码实现


public class CountSort {

    public static void main(String[] args) {
        int[] arr = {6, 3, 7, 5, 3, 2, 5};
        count(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void count(int[] arr) {
        // 边界处理
        if (arr == null || arr.length < 2) {
            return;
        }
        int len = arr.length;

        // 用来确定计数数组的范围
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            max = Math.max(max, arr[i]);
        }

        // 定义计数数组
        int[] countArr = new int[max + 1];
        // 统计每个值出现的次数，并放到计数数组对应的下标中
        for (int i = 0; i < len; i++) {
            countArr[arr[i]]++;
        }

        // 依次从计数数组中取出，并重新赋值给arr数组，便完成了排序
        int i = 0;
        for (int j = 0; j < len + 1; j++) {
            while (countArr[j]-- > 0) {
                arr[i++] = j;
            }
        }
    }
    
}