插值排序

十大经典排序算法

插值排序（interpolation sort）也称直方图排序（histogram sort），他是桶排序算法的一种变型，和桶排序非常类似，每个元素放到哪个桶里是通过下面公式计算的。

哪个桶 = 取整数(((设算数 - 最小数) / (最大数 - 最小数)) * (桶子数量 - 1))

然后每个桶里的元素在单独排序，具体可以看下桶排序。

private void interpolationSort(int[] nums) {
    int length = nums.length;
    int min = Arrays.stream(nums).min().getAsInt(); // 数组最小值
    int max = Arrays.stream(nums).max().getAsInt(); // 数组最大值
    if (max == min)
        return;
    List<Integer>[] bucket = new List[length];
    for (int i = 0; i < length; i++)
        bucket[i] = new ArrayList<>();
    for (int i = 0; i < length; i++) {
        // 计算当前值在哪个桶里
        int index = (int) Math.floor(((nums[i] - min) * 1.0 / (max - min)) * (length - 1));
        bucket[index].add(nums[i]);
    }

    int index = 0;
    for (int i = 0; i < length; i++) {
        if (bucket[i].size() > 1)
            Collections.sort(bucket[i]);// 每个桶在单独排序
        for (int j = 0; j < bucket[i].size(); j++)
            nums[index++] = bucket[i].get(j);
    }
}

相关链接