计数排序

转自：https://www.runoob.com/w3cnote/counting-sort.html

利用额外空间完成的排序算法，计数排序要求输入的数据必须是由确定范围的整数。
当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。

算法实现：

public class CountingSort {
    public static int getMax(int[] nums) {
        int maxValue = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxValue = Math.max(maxValue, nums[i]);
        }
        return maxValue;
    }

    public static int[] sort(int[] nums, int maxValue) {
        int[] tmpArr = new int[maxValue + 1];
        // 记录每个槽位有多少个相同的数
        for (int num : nums) {
            tmpArr[num]++;
        }
        int index = 0;
        for (int i = 0; i < tmpArr.length; i++) {
            while (tmpArr[i]-- > 0) {
                nums[index++] = i;
            }
        }
        return nums;
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 3, 5, 9, 9, 10, 11, 5, 3, 1};
        System.out.println(Arrays.toString(sort(nums, getMax(nums))));
    }
}