计数排序

计数排序（Counting sort）是一种稳定的线性时间排序算法。该算法于 1954 年由 Harold H. Seward 提出。计数排序使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。维基百科：计数排序。

计数排序要求待排序数组必须是整数，而且值域必须明确。

public void countingSort(int[] nums) {
    // 取最大、最小值
    int max = Arrays.stream(nums).max().getAsInt();
    int min = Arrays.stream(nums).min().getAsInt();

    // 为额外数组 count 开空间
    int range = max - min + 1;
    int[] count = new int[range];

    // 统计元素出现次数（需要计算偏移量）
    for (int num : nums) count[num - min]++;

    // 求计数和
    for (int i = 1; i < range; ++i) count[i] += count[i - 1];

    // 反向填充数组，
    int len = nums.length;
    int[] output = new int[len];
    for (int i = len - 1; i >= 0; --i) {
        output[count[nums[i] - min] - 1] = nums[i];
        count[nums[i] - min]--;
    }

    // 写回
    for (int i = 0; i < len; ++i) nums[i] = output[i];
}