1. 核心原理

桶排序是一種非比較型排序算法，通過將數據分配到多個“桶”中，每個桶單獨排序后再合并。其核心步驟包括：

• 分桶：根據元素的范圍或分布，將數據分配到有限數量的桶中。
• 桶內排序：對每個非空桶內的數據進行排序（通常使用插入排序等簡單算法）。
• 合并結果：按桶的順序將數據合并回原數組。

關鍵特點：

• 適用于數據分布均勻且范圍已知的場景。
• 時間復雜度依賴數據分布，理想情況下接近線性。
• 屬于**“空間換時間”**的排序策略。

2. 時間復雜度與空間復雜度

維度	說明
最好情況	O(n)（數據均勻分布，每個桶元素數量均衡）
平均情況	O(n + k)，k為桶數量（若每個桶內用O(n2)排序，則為O(n + n2/k)）
最壞情況	O(n2)（所有數據集中在一個桶內）
空間復雜度	O(n + k)（需要額外存儲桶和桶內數據）

3. 適用場景

推薦場景	不推薦場景
- 數據均勻分布	- 數據分布極度不均
- 數據范圍已知	- 內存嚴格受限
- 外部排序（如大數據）	- 數據范圍未知或動態變化
- 需要穩定排序	- 對空間效率要求高

4. 代碼實現（Python）

以下是將范圍 [0, 100) 的整數分為10個桶的示例：

def bucket_sort(arr, bucket_size=10):if len(arr) == 0:return arr# 1. 計算數據范圍min_val, max_val = min(arr), max(arr)bucket_count = (max_val - min_val) // bucket_size + 1buckets = [[] for _ in range(bucket_count)]# 2. 分桶for num in arr:idx = (num - min_val) // bucket_sizebuckets[idx].append(num)# 3. 桶內排序（此處使用內置排序，實際可用插入排序）sorted_arr = []for bucket in buckets:sorted_arr.extend(sorted(bucket))  # 穩定排序需保持插入順序return sorted_arr# 示例調用
arr = [29, 25, 3, 49, 9, 37, 21, 43]
sorted_arr = bucket_sort(arr)
print("排序結果:", sorted_arr)  # 輸出: [3, 9, 21, 25, 29, 37, 43, 49]

5. 分桶過程示例

假設輸入數組為 [29, 25, 3, 49, 9, 37, 21, 43]，最小值為3，最大值為49，桶大小為10：

1. 計算桶數量：(49 - 3) // 10 + 1 = 5個桶（范圍分別為3-12, 13-22, 23-32, 33-42, 43-52）。
2. 分桶結果：
   • Bucket 0 (3-12): [3, 9]
   • Bucket 1 (13-22): [21]
   • Bucket 2 (23-32): [29, 25]
   • Bucket 3 (33-42): [37]
   • Bucket 4 (43-52): [49, 43]
3. 桶內排序：
   • Bucket 0 → [3, 9]
   • Bucket 1 → [21]
   • Bucket 2 → [25, 29]
   • Bucket 3 → [37]
   • Bucket 4 → [43, 49]
4. 合并結果：[3, 9, 21, 25, 29, 37, 43, 49]。

6. 優化策略

• 動態調整桶大小：根據數據分布自動調整桶的數量和范圍。
• 混合排序算法：對小桶使用插入排序，對大桶遞歸使用桶排序。
• 處理重復元素：使用計數排序優化含大量重復值的數據。

7. 對比其他排序算法

維度	桶排序	快速排序	歸并排序
排序類型	非比較排序	比較排序	比較排序
穩定性	是（若桶內排序穩定）	否	是
最佳場景	均勻分布數據	通用隨機數據	鏈表/外部排序
空間開銷	高（需額外桶空間）	低（遞歸棧）	高（合并需額外數組）

8. 總結

桶排序在數據均勻分布且范圍已知時效率極高，但需權衡空間開銷。適用于大規模數據、外部排序及特定場景（如浮點數排序）。實際應用中需結合數據特點調整分桶策略，以平衡時間與空間效率。