使用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 代碼實現¶

代碼解釋¶

桶排序的優缺點¶

相關文章