计数排序

计数排序不是一个比较排序算法，该算法于1954年由 Harold H. Seward提出，通过计数将时间复杂度降到了计数排序、基数排序 - 图3 。

找出原数组中元素值最大的，记为max。
创建一个新数组count，其长度是max加1，其元素默认值都为0。
遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。
创建结果数组result，起始索引index。
遍历count数组，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到result数组中去，每处理一次，count中的该元素值减1，直到该元素值不大于0，依次处理count中剩下的元素。

返回结果数组result。

public class CountSort {
 public static void sort(int[] arr) {
     int max = Integer.MIN_VALUE;
     for (int num : arr) {
         max = Math.max(num, max);
     }
     int[] count = new int[max+1];
     for (int num : arr) {
         count[num] ++;
     }
     for (int i = 0, index = 0; i < count.length; i++) {
         while (count[i] != 0) {
             arr[index++] = i;
             count[i] --;
         }
     }
 }
 public static void main(String[] args) {
     int[] arr = ArrayGenerator.getArr(10, 50);
     System.out.println(Arrays.toString(arr));
     sort(arr);
     System.out.println(Arrays.toString(arr));
 }
}

改进版：如果原先的算法最大值为 1000，最小值为 990，那依旧需要开辟长度为 1000 的数组来进行排序，会造成极大的浪费。只需要将最小值求出就可以大大减少空间浪费

public static void sort(int[] arr) {
 int max = Integer.MIN_VALUE;
 int min = Integer.MAX_VALUE;
 for (int num : arr) {
     max = Math.max(num, max);
     min = Math.min(num, min);
 }
 int[] count = new int[max - min + 1];
 for (int num : arr) {
     count[num - min]++;
 }
 for (int i = 0, index = 0; i < count.length; i++) {
     while (count[i] != 0) {
         arr[index++] = i + min;
         count[i]--;
     }
 }
}

计数排序算法可以将排序算法的时间复杂度降低到计数排序、基数排序 - 图4 ，但是有两个前提需要满足：一是需要排序的元素必须是整数，二是排序元素的取值要在一定范围内，并且比较集中。只有这两个条件都满足，才能最大程度发挥计数排序的优势

基数排序

import java.util.Arrays;

public class RadixSort {
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length == 0) return;

        sort(arr, 0, arr.length - 1, maxbits(arr));
    }

    /**
     * 返回最大值是几位数
     */
    public static int maxbits(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int res = 0;
        while (max % 10 != 0) {
            res++;
            max /= 10;
        }
        return res;
    }

    public static void sort(int[] arr, int L, int R, int digit) {
        // 辅助空间
        int[] bucket = new int[R - L + 1];

        int index = 0;

        // 多少位就需要操作多少次
        for (int i = 1; i <= digit; i++) {
            // 10 进制 需要 10 个桶
            // count[0] 当前位置是 <=0 的数字有多少个
            // count[1] 当前位置是 <=1 的数字有多少个
            // count[2] 当前位置是 <=2 的数字有多少个
            // count[i] 当前位置是 <=i 的数字有多少个
            int[] count = new int[10];

            for (int j = L; j <= R; j++) {
                int num = getDigit(arr[j], i);
                count[num]++;
            }
            // 将 count 处理成前置和
            for (int j = 1; j < 10; j++) {
                count[j] = count[j] + count[j - 1];
            }
            // 从右往左开始将本次排序的结果放到数组中，保证顺序
            for (int r = R; r >= L; r--) {
                int num = getDigit(arr[r], i);
                if (count[num] == 0) continue;
                bucket[count[num] - 1] = arr[r];
                count[num]--;
            }
            // 将辅助数组中排序后的值给 arr
            index = L;
            for (int j = 0; index <= R; index++, j++) {
                arr[index] = bucket[j];
            }
        }
    }

    /**
     * 获取 num 在 i 位置上的值
     */
    private static int getDigit(int num, int i) {
        return (num / Math.max(1, (int) Math.pow(10, i - 1))) % 10;
    }

    public static void main(String[] args) {
        int[] arr = ArrayGenerator.getArr(10, 50);
        System.out.println(Arrays.toString(arr));
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
        for (int i = 0; i < 50; i++) {
            arr = ArrayGenerator.getArr(10, 50);
            int[] arr1 = ArrayGenerator.getSortArr(arr);
            radixSort(arr);
            if (!ArrayGenerator.isSame(arr, arr1)) {
                System.out.println("出错了：" + Arrays.toString(arr));
            }
        }
    }
}