import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型一维数组
     */
    public int[] bucketSort(int[] nums) {
        // 找出最大值和最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }

        // 计算桶的数量
        int bucketNum = (max - min) / nums.length + 1;

        // 初始化桶
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < bucketNum; i++) {
            buckets.add(new ArrayList<>());
        }

        // 将元素分配到桶中
        for (int num : nums) {
            int bucketIndex = (num - min) / nums.length;
            buckets.get(bucketIndex).add(num);
        }

        // 对每个桶中的元素进行排序
        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket);
        }

        // 汇总所有桶的结果
        int index = 0;
        int[] result = new int[nums.length];
        for (List<Integer> bucket : buckets) {
            for (int num : bucket) {
                result[index++] = num;
            }
        }

        return result;
    }
}

本题知识点分析：

1.桶排序

2.数组遍历

3.集合的存取

4.API工具类Collections.sort

5.数学模拟

本题解题思路分析：

1.先遍历数组，获取最大值和最小值

2.根据最大值和最小值的差值，去分配桶的数量

3.将每个元素分配到不同的桶中

4.使用工具类进行排序

5.汇总所有桶的结果

注意事项：很多人写成计数排序，这题你要注意题目给的数值范围：[-5 * 10^4, 5 * 10^4]，是有负数的，你用bucket[nums[i]]++这种，数组是没有负号的下标的，所以一定会出错，只是测试用例不够而已。

我把GPT回答桶排序和计数排序的区别答案放在这里：

桶排序（Bucket Sort）和计数排序（Counting Sort）是两种基于桶的排序算法，它们有一些相似之处，但也有一些关键的区别。

  1. 桶的粒度不同：在桶排序中，对于输入数据的分布范围，我们将其划分为多个桶，然后将数据分别放入对应的桶中。每个桶再使用其他排序算法或递归地继续进行排序。而计数排序中，在确定输入数据范围后，我们直接创建一个计数数组，并根据输入数据的值，将其放入计数数组中对应的位置。
  2. 对于输入数据分布的要求：桶排序对输入数据的分布要求相对较宽松。可以适用于均匀分布和不均匀分布的数据。而计数排序对于输入数据的分布有更严格的要求。输入数据的范围必须是已知的，并且分布比较集中，即数据非常稀疏。因为计数排序依赖于输入数据的范围来创建计数数组，并且需要分配足够大的计数数组来容纳所有可能的值。
  3. 对于排序稳定性的保持：在桶排序中，如果在每个桶内使用稳定的排序算法，比如插入排序，可以保持元素的相对顺序。而计数排序本身就是稳定的，无论是对于相同值的元素，还是对于排序后相同计数值的元素。
  4. 时间复杂度：桶排序的时间复杂度是O(n+k)，其中n是元素的数量，k是桶的数量。计数排序的时间复杂度是O(n+k)，其中n是元素的数量，k是元素范围。

做题需要耐心