桶排序算法解读（基于java实现）

1. 初始化空桶数组bucket
2. 遍历待排序数组arr，将每个元素按照某种映射规则分配到对应的桶中
   bucket[floor(arr[i]/bucketSize)] += arr[i]
3. 遍历桶数组bucket，对每个非空桶内部进行排序
   for j = 0 to bucket.length-1 do
      if bucket[j] is not empty then
         sort(bucket[j])
4. 将各个桶内部排序后的数据合并到待排序数组arr中
   index = 0
   for j = 0 to bucket.length-1 do
      if bucket[j] is not empty then
         for k = 0 to bucket[j].length-1 do
            arr[index] = bucket[j][k]
            index++
5. 返回排好序的数组arr

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class BucketSort {
    public static void bucketSort(int[] arr, int bucketSize) {
        if (arr.length == 0) {
            return;
        }

        // 寻找数组中的最大值和最小值
        int minValue = arr[0];
        int maxValue = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < minValue) {
                minValue = arr[i];
            } else if (arr[i] > maxValue) {
                maxValue = arr[i];
            }
        }

        // 计算桶的数量
        int bucketCount = (maxValue - minValue) / bucketSize + 1;
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }

        // 将数组中的元素分配到各个桶中
        for (int value : arr) {
            int bucketIndex = (value - minValue) / bucketSize;
            buckets.get(bucketIndex).add(value);
        }

        // 对每个非空的桶内部进行排序
        int index = 0;
        for (ArrayList<Integer> bucket : buckets) {
            if (!bucket.isEmpty()) {
                Collections.sort(bucket); // 这里使用了Java自带的排序方法
                for (int value : bucket) {
                    arr[index++] = value;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {29, 25, 3, 49, 9, 37, 21, 43};
        bucketSort(arr, 10);

        System.out.println(Arrays.toString(arr));
    }
}