桶排序（Bucket Sort）是一種非比較型排序算法，基於分治思想，通過將數據分配到多個“桶”中，逐個桶排序後合併結果實現整體有序。它的核心是“分而治之”，適合數據分佈均勻且範圍有限的場景。

桶排序的基本思路¶

1. 分桶：根據數據分佈特點，將數據劃分到若干個桶中。例如，若數據在0到1之間均勻分佈，可將0到1的區間劃分爲n個等長的子區間（每個子區間對應一個桶，n爲數據個數）。
2. 桶內排序：每個桶內元素數量較少，使用簡單排序算法（如插入排序、內置排序函數）對桶內元素排序。
3. 合併桶：按桶的順序依次取出元素，合併成最終有序數組。

適用場景¶

• 數據分佈均勻：當數據在某一連續區間內均勻分佈時（如0到1之間），桶排序時間複雜度接近線性（O(n)）。
• 範圍有限：若數據範圍明確（如整數0到1000），便於設置桶的數量和大小。
• 不適用：若數據分佈不均勻（如大部分元素集中在少數桶中），可能退化爲O(n²)，效率低於快速排序等算法。

Python實現步驟（以0-1區間浮點數爲例）¶

1. 確定桶數量：設桶數等於數據長度n，每個桶負責的區間爲1/n。
2. 創建桶：初始化n個空桶（列表的列表）。
3. 分配數據到桶：遍歷數據，通過int(num * n)計算桶索引，將元素放入對應桶。
4. 桶內排序：對每個桶使用內置排序函數（如sort()）。
5. 合併桶：依次遍歷所有桶，將元素合併成有序數組。

代碼實現¶

def bucket_sort(arr):
    # 1. 處理空數組
    if not arr:
        return arr

    n = len(arr)
    # 2. 創建n個空桶
    buckets = [[] for _ in range(n)]

    # 3. 將數據分配到桶中（假設數據在0到1之間）
    for num in arr:
        # 計算桶索引：num * n 取整
        bucket_index = int(num * n)
        buckets[bucket_index].append(num)

    # 4. 對每個桶內元素排序併合並結果
    sorted_arr = []
    for bucket in buckets:
        bucket.sort()  # 桶內排序（內置排序高效）
        sorted_arr.extend(bucket)  # 合併桶內元素

    return sorted_arr

# 測試
if __name__ == "__main__":
    test_data = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
    sorted_data = bucket_sort(test_data)
    print("原始數據:", test_data)
    print("排序後:", sorted_data)

代碼解釋¶

• 桶數量：n = len(arr)，確保每個桶覆蓋區間爲1/n，避免數據溢出。
• 桶索引計算：int(num * n)將0-1之間的數映射到0到n-1的桶索引，例如num=0.3、n=7時，桶索引爲0.3*7=2.1→2。
• 桶內排序：bucket.sort()直接使用內置排序，小數據量下效率極高。
• 合併結果：sorted_arr.extend(bucket)依次添加每個桶的元素，最終得到有序數組。

運行結果¶

原始數據: [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
排序後: [0.32, 0.33, 0.37, 0.42, 0.47, 0.51, 0.52]

注意事項¶

• 數據分佈：若數據範圍非0-1區間，需調整桶索引計算方式（如int((num - min_val) / bucket_size)）。
• 桶大小優化：桶數量應根據數據分佈動態調整，避免部分桶元素過多（如極端值集中時，需增大桶數量）。

總結¶

桶排序通過“分桶-排序-合併”三步實現高效排序，適合數據均勻分佈的場景。其核心是利用分治思想降低整體複雜度，代碼簡潔但需注意數據分佈特性，避免性能退化。