桶子排序是一種 把資料分類再逐一排序 的演算法。
想像一下你有一堆數字,目標是從小到大排列,但這堆數字範圍很大、分布也不均勻。
因此桶子排序的想法就是:
(1) 先根據數字的範圍,把它們分進不同的「桶子」裡。
(2) 每個桶子裡的數字再個別進行排序。
(3) 最後把所有桶子的內容合併在一起,這樣數字就排好了!
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:
原始數組 : []
排序結果 : []
各位應該到這邊,應該會有一個疑問,既然我在程式碼中就用了 sort 這個指令,為什麼我還需要桶子排序? 直接sort一下就行了阿?最大的原因在於,桶子排序先分類再排序,可以減少 sort 的計算時間 (直覺: 給你一堆數值要你去排序,跟幫你分類好再請你排序,誰會比較好排? 顯然是後者會更有效率)
因此桶子排序的核心概念是 分類加速,將資料劃分為多個小範圍(桶),僅對桶內資料排序後合併,完成排序。且其優勢在於時間複雜度接近 O(n) (最差就頂多與sort 的 O(n log n) 一樣) ,當資料符合以下條件時會感受到極大效率的差異:
(1) 資料分布均勻:均勻分布的資料使每個桶內的資料量接近平均,可大幅減少排序成本,接近線性排序。
(2) 資料範圍大且分布明確:範圍大的資料,若使用桶子排序可以按範圍劃分,可以縮小排序範圍,比直接用 sort() 更高效。
所以,如果資料分布均勻且範圍大,桶子排序能夠幫助你更好的提高資料處裡效率,特別適合巨量資料處理。而對於範圍小或隨機分布的資料,直接用 sort() 會更簡單且快速~