使用Java实现桶排序算法

桶排序（Bucket Sort）是一种非比较型排序算法，它的核心思想是将待排序的元素分配到若干个“桶”中，每个桶内的元素再进行局部排序，最后将所有桶中的元素按顺序合并起来，得到最终的有序数组。这种排序算法非常适合数据分布比较均匀的场景，比如数据是整数且范围不大，或者可以将数据映射到一个较小的整数范围内。它的时间复杂度在理想情况下（数据均匀分布，每个桶内元素数量少）可以达到 O(n)，空间复杂度为 O(n)。

桶排序的步骤¶

确定桶的数量和范围：首先需要明确待排序数据的范围。例如，如果数据是整数且最大值为 max，那么桶的数量可以设置为 max + 1，每个桶对应一个整数范围（0 到 max）。如果数据是浮点数，可以通过一定的映射关系将其转换为整数桶（比如乘以一个倍数转为整数）。
创建桶：根据桶的数量，创建一个容器（如 ArrayList 数组），每个容器对应一个桶，用于存储该桶范围内的元素。
分配元素到桶：遍历待排序数组，将每个元素根据其值放入对应的桶中。例如，元素 num 对应的桶索引是 num（因为桶索引 0 对应元素 0，索引 1 对应元素 1 等）。
桶内排序：对每个桶中的元素进行排序。由于桶内的元素通常数量较少，这里可以使用简单的排序算法（如插入排序、冒泡排序），或者直接调用 Java 提供的 Collections.sort() 方法。
合并桶的结果：按照桶的顺序依次遍历每个桶，将桶内的元素按顺序添加到结果数组中，最终得到排序后的数组。

实例演示¶

假设我们要排序的数组是 [3, 1, 4, 1, 5, 9, 2, 6, 5]，具体步骤如下：

确定桶的范围：数组中的元素是 0 到 9 的整数，因此桶的数量为 9 + 1 = 10（索引 0 到 9）。
创建桶：创建一个长度为 10 的 ArrayList 数组，每个元素是一个 ArrayList，用于存储对应范围内的元素。
分配元素到桶：遍历数组，将每个元素放入对应索引的桶中：
- 元素 3 → 桶 3 → [3]
- 元素 1 → 桶 1 → [1]
- 元素 4 → 桶 4 → [4]
- 元素 1 → 桶 1 → [1, 1]
- 元素 5 → 桶 5 → [5]
- 元素 9 → 桶 9 → [9]
- 元素 2 → 桶 2 → [2]
- 元素 6 → 桶 6 → [6]
- 元素 5 → 桶 5 → [5, 5]
桶内排序：对每个桶中的元素排序（这里因元素数量少，排序后无变化）：
- 桶 1：[1, 1]（已排序）
- 桶 5：[5, 5]（已排序）
- 其他桶（如桶 0、2、3、4、6、9）仅含一个元素，无需排序。
合并结果：按桶的顺序（0 到 9）依次取出元素，合并得到排序后的数组：[1, 1, 2, 3, 4, 5, 5, 6, 9]。

Java 代码实现¶

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

public class BucketSort {

    public static void bucketSort(int[] arr) {
        // 处理边界情况：空数组或单元素数组无需排序
        if (arr == null || arr.length <= 1) {
            return;
        }

        // 步骤1：确定桶的范围（假设元素为非负整数，最大值为max）
        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }

        // 步骤2：创建桶，数量为max + 1（每个桶对应一个整数0~max）
        ArrayList<Integer>[] buckets = new ArrayList[max + 1];
        for (int i = 0; i <= max; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 步骤3：将元素分配到对应的桶中
        for (int num : arr) {
            int bucketIndex = num; // 元素num对应桶的索引为num
            buckets[bucketIndex].add(num);
        }

        // 步骤4：对每个桶内的元素进行排序
        for (ArrayList<Integer> bucket : buckets) {
            Collections.sort(bucket); // 使用Collections.sort简化排序操作
        }

        // 步骤5：合并所有桶的元素到原数组，得到排序结果
        int index = 0; // 原数组的索引
        for (ArrayList<Integer> bucket : buckets) {
            for (int num : bucket) { // 遍历桶内元素
                arr[index++] = num; // 覆盖原数组，依次放入元素
            }
        }
    }

    // 测试代码
    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5};
        System.out.println("排序前：" + java.util.Arrays.toString(arr));
        bucketSort(arr);
        System.out.println("排序后：" + java.util.Arrays.toString(arr));
    }
}

代码解释¶

边界处理：若数组为空或只有一个元素，直接返回，无需排序。
确定桶范围：通过遍历数组找到最大值 max，桶的数量为 max + 1，每个桶对应一个整数范围（0 到 max）。
创建桶：使用 ArrayList 数组作为桶，每个 ArrayList 用于存储对应范围内的元素。
分配元素：遍历原数组，将每个元素放入对应索引的桶中（元素 num 对应桶索引 num）。
桶内排序：对每个桶中的 ArrayList 使用 Collections.sort() 排序，确保桶内元素有序。
合并结果：按桶的顺序（0 到 max）依次取出元素，覆盖原数组，得到最终排序结果。

桶排序的优缺点¶

优点：当数据分布均匀且范围不大时，时间复杂度接近 O(n)，非常高效。每个元素只需一次分配和一次合并，桶内排序的时间成本低。
缺点：需要额外空间存储桶，当数据范围很大时（如元素值从 0 到 10^9），桶的数量会非常多，导致空间浪费。若数据分布不均匀（如大部分元素集中在少数几个桶中），桶内排序时间会增加，可能退化为 O(n^2)。

桶排序适用于数据分布均匀且范围可控的场景，通过合理设计桶的数量和范围，可以显著提升排序效率。

桶排序的步骤¶

实例演示¶

Java 代码实现¶

代码解释¶

桶排序的优缺点¶

相关文章