排序算法之计数排序(JAVA)

排序过程
1.找出待排序的数组中最大和最小的元素
2.统计数组中每个值为出现的次数，存入数组位置等于该值处
3.对所有的计数累加sum
4.反向填充目标数组：将计数数组的元素顺序倒出到新数组中，每倒出一个元素，计数数组的计数就减一(sum也减一)，sum减到0结束

排序的各项指标
平均时间复杂度：O(N+K)
最坏时间复杂度：O(N+K)
空间复杂度：O(N+K)
是否稳定：稳定

排序实现

在这里插入代码片
public static void countingSort(int[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
    int max = Integer.MIN_VALUE;    // 也可以同时设置最大 和 最小（不设置就从0开始）， 这样可以减少空间浪费
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
    }
    int[] countArr = new int[max + 1];
    for (int i = 0; i < arr.length; i++) {
        countArr[arr[i]] = countArr[arr[i]] + 1;
    }
    int index = 0;
    for (int i = 0; i < countArr.length; i++) {
        while (countArr[i] > 0) {
            arr[index++] = i;
            countArr[i] = countArr[i] - 1;
        }
    }
}