当数列最大和最小差距过大时, 并不适用计数排序

例如给出20个随机整数, 范围在0-1亿之间, 这时如果使用计数排序, 
需要创建长度为1亿的数组. 不但严重浪费空间, 而且时间复杂度也会随之升高.

当数列元素不是整数时, 不适用计数排序

如果数列中的元素都是小树, 如25.213, 或是0.0000000001这样的数字, 
则无法创建对应的统计数组. 这样显然无法进行计数排序.

示例代码

    public static void main(String[] args) {
        int[] arr = new int[]{6, 4, 3, 2, 1, 9, 5, 7, 8, 10};
        int[] resultArr = countSort(arr);
        System.out.println("数组一排序: " + Arrays.toString(resultArr));

        arr = new int[]{80, 89, 87, 82, 81, 88, 85, 84, 83, 86};
        int[] resultArr2 = countSort(arr);
        System.out.println("数组二排序: " + Arrays.toString(resultArr2));
    }
    
    -----------------------------------------------------------------
    数组一排序: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    数组二排序: [80, 81, 82, 83, 84, 85, 86, 87, 88, 89]
    -----------------------------------------------------------------

    public static int[] countSort(int[] nums) {
        // 得到数列最大/最小值
        int max = nums[0];
        int min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(nums[i], max);
            min = Math.min(nums[i], min);
        }

        // 根据数列最大值和最小值确定计数数组长度
        int[] countArr = new int[max - min + 1];
        // 遍历数列, 填充统计长度
        for (int num : nums) {
            countArr[num - min]++;
        }
        
        // 遍历统计数组, 输出结果 
        int index = 0;
        int[] sortArr = new int[nums.length];
        for (int i = 0; i < countArr.length; i++) {
            for (int j = 0; j < countArr[i]; j++) {
                sortArr[index++] = i + min;
            }
        }
        return sortArr;
    }