每日算法 — 使用java实现桶排序：分桶策略与均匀分布数据排序

引言

桶排序（Bucket Sort）是一种基于分治思想的线性时间排序算法。当输入数据服从均匀分布时，桶排序的平均时间复杂度可以达到 ( O(n) )，这是比较排序算法（如快速排序、归并排序）无法达到的理论下界。桶排序的核心思想是将数据分到若干个有序的”桶”中，每个桶内部再进行排序，最后按顺序合并所有桶。本文将详细讲解桶排序的原理，并用Java实现一个通用的桶排序框架。

算法原理

桶排序的工作流程分为三个步骤：

1. 分桶：根据数据的取值范围，创建若干个桶，每个桶对应一个区间
2. 分配：遍历原始数组，将每个元素放入对应的桶中
3. 排序与合并：对每个非空桶内部进行排序（通常使用插入排序或快速排序），然后按桶的顺序依次输出

假设输入数据均匀分布在区间 ([min, max]) 内，将其划分为 ( k ) 个等宽区间，每个区间的宽度为 ( w = (max – min) / k )。元素 ( x ) 所属的桶索引为 ( \lfloor (x – min) / w
floor )。

Java实现

基础版桶排序

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 桶排序实现类
 * 适用于均匀分布的浮点数或整数数据
 */
public class BucketSort {

    /**
     * 对浮点数组进行桶排序
     * @param arr 待排序数组，元素范围假设在[0, 1)之间
     */
    public static void sort(double[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        int n = arr.length;
        // 创建n个桶，每个桶是一个列表
        @SuppressWarnings("unchecked")
        List<Double>[] buckets = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 将元素分配到对应的桶中
        // 元素x放入索引为 (int)(n * x) 的桶
        for (double value : arr) {
            int bucketIndex = (int) (n * value);
            // 处理边界情况：当value为1.0时
            if (bucketIndex >= n) {
                bucketIndex = n - 1;
            }
            buckets[bucketIndex].add(value);
        }

        // 对每个桶内部进行排序，使用Collections.sort（基于TimSort）
        for (List<Double> bucket : buckets) {
            Collections.sort(bucket);
        }

        // 按顺序合并所有桶中的元素
        int index = 0;
        for (List<Double> bucket : buckets) {
            for (double value : bucket) {
                arr[index++] = value;
            }
        }
    }

    /**
     * 通用桶排序：支持任意范围的整数
     * @param arr 待排序整数数组
     * @param bucketCount 桶的数量
     */
    public static void sort(int[] arr, int bucketCount) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        // 找到数组的最小值和最大值
        int min = arr[0], max = arr[0];
        for (int value : arr) {
            if (value < min) min = value;
            if (value > max) max = value;
        }

        // 如果所有元素相同，直接返回
        if (min == max) return;

        // 创建桶
        @SuppressWarnings("unchecked")
        List<Integer>[] buckets = new ArrayList[bucketCount];
        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 计算每个桶的区间宽度
        double range = max - min + 1;
        double bucketSize = range / bucketCount;

        // 分配元素到桶
        for (int value : arr) {
            int bucketIndex = (int) ((value - min) / bucketSize);
            if (bucketIndex >= bucketCount) {
                bucketIndex = bucketCount - 1;
            }
            buckets[bucketIndex].add(value);
        }

        // 对每个桶排序并合并
        int index = 0;
        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket);
            for (int value : bucket) {
                arr[index++] = value;
            }
        }
    }
}

进阶版：自定义对象桶排序

/**
 * 学生成绩类，用于演示自定义对象的桶排序
 */
class StudentScore {
    String name;
    int score;  // 分数范围假设为 0-100

    public StudentScore(String name, int score) {
        this.name = name;
        this.score = score;
    }

    @Override
    public String toString() {
        return name + ":" + score;
    }
}

/**
 * 学生成绩分段统计与排序
 * 将成绩分为优(90-100)、良(80-89)、中(70-79)、及格(60-69)、不及格(0-59)五个桶
 */
public class StudentScoreBucketSort {

    public static void sortByGradeLevel(StudentScore[] students) {
        if (students == null || students.length <= 1) return;

        // 5个等级桶
        @SuppressWarnings("unchecked")
        List<StudentScore>[] gradeBuckets = new ArrayList[5];
        for (int i = 0; i < 5; i++) {
            gradeBuckets[i] = new ArrayList<>();
        }

        // 分配学生到对应等级桶
        for (StudentScore student : students) {
            int bucketIndex;
            if (student.score >= 90) bucketIndex = 0;      // 优
            else if (student.score >= 80) bucketIndex = 1; // 良
            else if (student.score >= 70) bucketIndex = 2; // 中
            else if (student.score >= 60) bucketIndex = 3; // 及格
            else bucketIndex = 4;                           // 不及格
            gradeBuckets[bucketIndex].add(student);
        }

        // 每个等级桶内按分数降序排列
        for (List<StudentScore> bucket : gradeBuckets) {
            bucket.sort((a, b) -> b.score - a.score);
        }

        // 合并结果：从优到不及格
        String[] gradeNames = {"优秀", "良好", "中等", "及格", "不及格"};
        int index = 0;
        for (int i = 0; i < 5; i++) {
            System.out.println("\n【" + gradeNames[i] + "】共" + gradeBuckets[i].size() + "人:");
            for (StudentScore s : gradeBuckets[i]) {
                System.out.println("  " + s);
                students[index++] = s;
            }
        }
    }
}

测试与演示

public class BucketSortDemo {
    public static void main(String[] args) {
        // 测试1：浮点数桶排序（均匀分布在[0, 1)）
        System.out.println("=== 测试1：浮点数桶排序 ===");
        double[] floatArr = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51, 0.12, 0.89, 0.05};
        System.out.print("排序前: ");
        printArray(floatArr);
        BucketSort.sort(floatArr);
        System.out.print("排序后: ");
        printArray(floatArr);

        // 测试2：整数桶排序
        System.out.println("\n=== 测试2：整数桶排序 ===");
        int[] intArr = {78, 17, 39, 26, 72, 94, 21, 12, 23, 68, 45, 56, 89, 34};
        System.out.print("排序前: ");
        printArray(intArr);
        BucketSort.sort(intArr, 5);  // 使用5个桶
        System.out.print("排序后: ");
        printArray(intArr);

        // 测试3：学生成绩分段统计
        System.out.println("\n=== 测试3：学生成绩分段统计 ===");
        StudentScore[] students = {
            new StudentScore("张三", 85),
            new StudentScore("李四", 92),
            new StudentScore("王五", 67),
            new StudentScore("赵六", 78),
            new StudentScore("孙七", 95),
            new StudentScore("周八", 58),
            new StudentScore("吴九", 73),
            new StudentScore("郑十", 88)
        };
        StudentScoreBucketSort.sortByGradeLevel(students);
    }

    static void printArray(double[] arr) {
        for (double v : arr) System.out.printf("%.2f ", v);
        System.out.println();
    }

    static void printArray(int[] arr) {
        for (int v : arr) System.out.print(v + " ");
        System.out.println();
    }
}

复杂度分析

适用场景与优化策略

适用场景

• 数据服从均匀分布或近似均匀分布
• 数据范围已知且可以划分成合理的区间
• 需要线性时间排序的外部排序场景

优化策略

1. 动态桶数量：根据数据量 ( n ) 选择桶数，通常取 ( k pprox n ) 或 ( k = \sqrt{n} )
2. 自适应桶大小：对非均匀分布数据，使用不等宽桶（如直方图均衡化思想）
3. 桶内排序算法选择：小数据量用插入排序，大数据量用快速排序
4. 链表替代数组：避免桶内数组扩容开销

总结

桶排序通过空间换时间的策略，在数据分布良好的情况下实现了线性时间排序。本文不仅实现了基础桶排序，还展示了如何将桶排序应用于成绩分段统计等实际场景。理解桶排序有助于掌握分治思想在非比较排序中的应用。