桶排序中对计算第几只桶的疑问

啊哦！这里确实我的代码错了！感谢提醒！我有时间修改一下这一小节的视频。

抱歉！

==========

修改后的完整代码如下：

public static void sort2(Integer[] arr, int c){
        
    if(c <= 0)
        throw new IllegalArgumentException("c must be > 0");
    
    // 首先，需要计算 arr 中的数据范围    
    int maxv = Integer.MIN_VALUE, minv = Integer.MAX_VALUE;
    for(int e: arr){
        maxv = Math.max(maxv, e);
        minv = Math.min(minv, e);
    }
    int range = maxv - minv + 1; // arr 中的数据范围
    
    // 根据数据范围 range 和每个桶中最多可容纳的元素，计算桶的个数 B 
    int B = range / c + (range % c > 0 ? 1 : 0); // 根据数据范围决定桶的个数
        
    // 开设桶
    LinkedList<Integer>[] buckets = new LinkedList[B];
    for(int i = 0; i < B; i ++)
        buckets[i] = new LinkedList<>();
    
    // 把数据放入桶中
    for(int e: arr)
        buckets[(e - minv) / c].add(e);
        
    // 对每一个桶排序
    for(int i = 0; i < B; i ++)
        Collections.sort(buckets[i]);
        
    // 重新整理所有数据
    int index = 0;
    for(int i = 0; i < B; i ++)
        for(int e: buckets[i])
            arr[index ++] = e;
    }
}

对于这个代码，我使用 Leetcode 164 进行了测试：https://leetcode-cn.com/problems/maximum-gap/

测试代码如下（直接复用上面的算法类。因为 164 问题给的是 int[]，也可以针对 int[] 再实现一遍桶排序。）

class Solution {
    public int maximumGap(int[] nums) {
        if(nums.length < 2) return 0;
        Integer[] data = Arrays.stream(nums).boxed().toArray( Integer[]::new );
        BucketSort.sort2(data, 100000);
        for(int e: data) System.out.println(e);
        int res = data[1] - data[0];
        for(int i = 2; i < data.length; i ++)
            res = Math.max(res, data[i] - data[i - 1]);
        return res;
    }
}

是可以获得通过的。

这个代码我也已经更新到了课程的官方代码仓中，可以参考这里：https://git.imooc.com/class-105/Play-Algorithms-and-Data-Structures/src/master/30-MSD-Radix-Sort-and-Bucket-Sort/07-Bucket-Sort2/src/BucketSort.java

继续加油！：）