排序算法-桶排序

桶排序（Bucket Sort）是一种分布式排序算法，它将待排序元素分到若干个桶（Bucket）中，每个桶单独排序（可以使用其他排序算法或递归桶排序），最后按顺序合并所有桶中的元素。

桶排序适用于数据分布均匀的情况，在理想情况下可以达到 O(n) 的时间复杂度，但最坏情况下可能退化为 O(n²)（如果所有元素都集中在少数桶中）。

桶排序步骤

1. 确定桶的数量和范围：

   • 根据数据范围，划分若干个区间（桶）。

   • 例如，数据在 [0, 100) 之间，可以分成 10 个桶，每个桶范围 [0,10), [10,20), ..., [90,100)。

2. 分配数据到桶中：

   • 遍历数组，将每个元素放入对应的桶。

3. 对每个桶单独排序：

   • 可以使用插入排序、快速排序、归并排序等（如果数据量小，插入排序效率较高）。

4. 合并所有桶：

   • 按桶的顺序依次取出元素，得到最终有序数组。

代码实现

package Sort;

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

public class BucketSort {
    public static void main(String[] args) {
        int[] res = getBucketSort(new int[]{7,12,56,23,19,33,35,42,42,2,8,22,39,26,17},5);
        for (int i = 0; i < res.length; i++) {
            System.out.print(res[i]+" ");
        }
    }
    //步骤：
    //1.计算最大和最小值，确定数据范围，并获得桶的数量
    //2.分配数据到桶中，遍历数组，将每个元素放入对应的桶中
    //3.对每个桶单独排序
    //4.合并所有桶
    //bucketSize：桶的容量，即每个桶所能方盒子多少个不同的值
    public static int[] getBucketSort(int[] nums, int bucketSize){
        if (nums == null || nums.length< 2) return nums;

        //1.计算最大和最小值，确定数据范围
        int min = nums[0],max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max){
                max = nums[i];
            }
            if (nums[i] < min){
                min = nums[i];
            }
        }
        //获得桶的数量
        int bucketCount = (max - min) / bucketSize + 1;

        //构建桶
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        //2.遍历数组，将每个元素放入对应的桶中
        for(int num : nums){
            int bucketIndex = (num - min) / bucketSize;
            buckets.get(bucketIndex).add(num);
        }

        //3.对每个桶单独排序
        for (ArrayList<Integer> bucket : buckets) {
            Collections.sort(bucket);
        }
        //4.合并所有桶
        int index = 0;
        for (ArrayList<Integer> bucket: buckets){
            for (int num : bucket){
                nums[index++] = num;
            }
        }
        return nums;
    }
}

复杂度分析

• n：数据规模

• k：桶的数量

适用场景

• 数据分布均匀（如 [0, 100) 的随机数）。

• 数据范围已知，且可以合理划分桶。