iT邦幫忙

2

桶子排序是什麼?

桶子排序是一種 把資料分類再逐一排序 的演算法。
想像一下你有一堆數字,目標是從小到大排列,但這堆數字範圍很大、分布也不均勻。

因此桶子排序的想法就是:
(1) 先根據數字的範圍,把它們分進不同的「桶子」裡。
(2) 每個桶子裡的數字再個別進行排序。
(3) 最後把所有桶子的內容合併在一起,這樣數字就排好了!


通常在撰寫過程,可注意以下細節

  1. 檢查特殊情況: 如果輸入的數字列是空的,或所有數字都一樣,那直接回傳原本的就好,不需要排序。
  2. 計算範圍: 找出數字的 最小值最大值,用來決定每個桶子的範圍大小(例如,範圍是 0~100,就可以分成 10 個桶子,每個桶子範圍是 10)。
  3. 分桶: 根據每個數值,算出應該放到哪個桶子(例如 25 放進第 2 個桶,89 放進第 8 個桶)。
  4. 桶內排序: 每個桶子內的數字,使用 Python 內建的排序功能(這樣速度快又穩定)。
  5. 合併結果: 把所有桶子的內容依序取出來,合併成最後的排序結果。

示意圖

https://ithelp.ithome.com.tw/upload/images/20250129/20171636SAtVoetKIb.png

實作

def bucket_sort(arr, num_buckets=10):
    """
    通用桶子排序算法,適用於小數與整數
    para:
        arr: 輸入數字列表
        num_buckets: 桶的數量 (預設 10)
    return:
        排序後的列表
    """
    if not arr:
        return arr  # 空陣列直接回傳
    
    # 計算數值範圍
    min_val, max_val = min(arr), max(arr)
    if min_val == max_val:
        return arr  # 全部數值相同直接回傳

    # 建立桶陣列
    buckets = [[] for _ in range(num_buckets)]
    bucket_range = (max_val - min_val) / num_buckets

    # 把數字分配到對應的桶
    for num in arr:
        idx = int((num - min_val) / bucket_range)
        idx = min(idx, num_buckets - 1)  # 確保最大值進入最後一個桶
        buckets[idx].append(num)

    # 各桶子排序並合併結果
    return [num for bucket in buckets for num in sorted(bucket)]


# 測試五種情境
if __name__ == "__main__":
    test_cases = [
        [13.5, 0.2, 7.8, 10.1, 1.23, 5.5, 3.14, 8.9], # 小數
        [100, 2, 56, 32, 89, 12, 45], # 整數
        [0.001, 1000.5, 25.7, 500.2, 0.12, 89.2], # 範圍很大
        [1, 1, 1, 1, 1], # 相同數值
        [5], # 單一值
        [] # 空值
    ]
    print("桶子排序測試\n" + "="*100)
    for i, case in enumerate(test_cases, 1):
        print(f"測試案例 {i}: \n原始數組 : {case}")
        print(f"排序結果 : {bucket_sort(case)}\n")

程式碼產出如下:

桶子排序測試
====================================================================================================
測試案例 1: 
原始數組 : [13.5, 0.2, 7.8, 10.1, 1.23, 5.5, 3.14, 8.9]
排序結果 : [0.2, 1.23, 3.14, 5.5, 7.8, 8.9, 10.1, 13.5]

測試案例 2: 
原始數組 : [100, 2, 56, 32, 89, 12, 45]
排序結果 : [2, 12, 32, 45, 56, 89, 100]

測試案例 3: 
原始數組 : [0.001, 1000.5, 25.7, 500.2, 0.12, 89.2]
排序結果 : [0.001, 0.12, 25.7, 89.2, 500.2, 1000.5]

測試案例 4: 
原始數組 : [1, 1, 1, 1, 1]
排序結果 : [1, 1, 1, 1, 1]

測試案例 5: 
原始數組 : [5]
排序結果 : [5]

測試案例 6: 
原始數組 : []
排序結果 : []

備註 (for 眼尖的人)

各位應該到這邊,應該會有一個疑問,既然我在程式碼中就用了 sort 這個指令,為什麼我還需要桶子排序? 直接sort一下就行了阿?最大的原因在於,桶子排序先分類再排序,可以減少 sort 的計算時間 (直覺: 給你一堆數值要你去排序,跟幫你分類好再請你排序,誰會比較好排? 顯然是後者會更有效率)

因此桶子排序的核心概念是 分類加速,將資料劃分為多個小範圍(桶),僅對桶內資料排序後合併,完成排序。且其優勢在於時間複雜度接近 O(n) (最差就頂多與sort 的 O(n log n) 一樣) ,當資料符合以下條件時會感受到極大效率的差異:

(1) 資料分布均勻:均勻分布的資料使每個桶內的資料量接近平均,可大幅減少排序成本,接近線性排序。
(2) 資料範圍大且分布明確:範圍大的資料,若使用桶子排序可以按範圍劃分,可以縮小排序範圍,比直接用 sort() 更高效。

所以,如果資料分布均勻且範圍大,桶子排序能夠幫助你更好的提高資料處裡效率,特別適合巨量資料處理。而對於範圍小或隨機分布的資料,直接用 sort() 會更簡單且快速~


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言