以下是桶排序的詳細解析，包含基礎實現、常見變體的完整代碼示例，以及各變體的對比表格：

---

一、桶排序基礎實現

原理

將數據分到有限數量的桶中，每個桶內部使用其他排序算法（如插入排序或快速排序），最后合并所有桶的結果。

代碼示例

import java.util.ArrayList;
import java.util.List;public class BucketSort {void sort(float[] arr) {if (arr.length == 0) return;// 創建桶（假設每個桶是一個ArrayList）int bucketCount = arr.length; // 桶的數量通常與元素數量相近List<ArrayList<Float>> buckets = new ArrayList<>();for (int i = 0; i < bucketCount; i++) {buckets.add(new ArrayList<>());}// 將數據分配到桶中for (float num : arr) {int index = (int) Math.floor(num * bucketCount);buckets.get(index).add(num);}// 對每個桶進行排序（此處使用插入排序）for (ArrayList<Float> bucket : buckets) {insertionSort(bucket);}// 合并所有桶的結果到原數組int index = 0;for (ArrayList<Float> bucket : buckets) {for (float num : bucket) {arr[index++] = num;}}}// 插入排序用于桶內排序private void insertionSort(ArrayList<Float> list) {for (int i = 1; i < list.size(); i++) {float key = list.get(i);int j = i - 1;while (j >= 0 && list.get(j) > key) {list.set(j + 1, list.get(j));j--;}list.set(j + 1, key);}}
}

復雜度分析

• 時間復雜度：
  • 平均：O(n + k)（k為桶的數量）。
  • 最壞：O(n2)（數據分布極不均勻時，桶內排序退化）。
• 空間復雜度：O(n + k)。
• 穩定性：穩定（若桶內排序算法穩定）。

---

二、常見變體及代碼示例

1. 自適應桶排序（動態桶大小）

改進點：根據數據分布動態調整桶的大小，減少極端分布的影響。
適用場景：數據分布不均勻時。

import java.util.ArrayList;
import java.util.List;public class AdaptiveBucketSort {void sort(float[] arr) {if (arr.length == 0) return;// 統計數據分布float min = Arrays.stream(arr).min().getAsFloat();float max = Arrays.stream(arr).max().getAsFloat();int bucketCount = arr.length;float bucketSize = (max - min) / bucketCount;List<ArrayList<Float>> buckets = new ArrayList<>();for (int i = 0; i < bucketCount; i++) {buckets.add(new ArrayList<>());}// 動態分配到桶for (float num : arr) {int index = (int) ((num - min) / bucketSize);index = Math.min(index, bucketCount - 1); // 防止溢出buckets.get(index).add(num);}// 桶內排序并合并int index = 0;for (ArrayList<Float> bucket : buckets) {insertionSort(bucket);for (float num : bucket) {arr[index++] = num;}}}private void insertionSort(ArrayList<Float> list) {// 同基礎版本的插入排序}
}

2. 分布式桶排序

改進點：利用多線程對多個桶并行排序。
適用場景：大數據或分布式計算環境。

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;public class ParallelBucketSort {void sort(float[] arr) {if (arr.length == 0) return;int bucketCount = arr.length;List<ArrayList<Float>> buckets = new ArrayList<>();for (int i = 0; i < bucketCount; i++) {buckets.add(new ArrayList<>());}// 分配到桶for (float num : arr) {int index = (int) Math.floor(num * bucketCount);buckets.get(index).add(num);}// 并行排序每個桶ExecutorService executor = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());for (ArrayList<Float> bucket : buckets) {executor.submit(() -> insertionSort(bucket));}executor.shutdown();try {executor.awaitTermination(Long.MAX_VALUE, TimeUnit.NANOSECONDS);} catch (InterruptedException e) {e.printStackTrace();}// 合并結果int index = 0;for (ArrayList<Float> bucket : buckets) {for (float num : bucket) {arr[index++] = num;}}}private void insertionSort(ArrayList<Float> list) {// 同基礎版本的插入排序}
}

3. 基于鏈表的桶排序

改進點：用鏈表存儲桶中的元素，避免動態擴容開銷。
適用場景：頻繁插入/刪除元素的場景。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;public class LinkedListBucketSort {void sort(float[] arr) {if (arr.length == 0) return;int bucketCount = arr.length;List<LinkedList<Float>> buckets = new ArrayList<>();for (int i = 0; i < bucketCount; i++) {buckets.add(new LinkedList<>());}// 分配到桶for (float num : arr) {int index = (int) Math.floor(num * bucketCount);buckets.get(index).add(num);}// 對每個桶排序（此處用快速排序）for (LinkedList<Float> bucket : buckets) {quickSort(bucket, 0, bucket.size() - 1);}// 合并結果int index = 0;for (LinkedList<Float> bucket : buckets) {for (float num : bucket) {arr[index++] = num;}}}private void quickSort(LinkedList<Float> list, int low, int high) {// 快速排序實現（略）}
}

---

三、變體對比表格

變體名稱	時間復雜度	空間復雜度	穩定性	主要特點	適用場景
基礎桶排序	O(n + k)（平均） O(n2)（最壞）	O(n + k)	穩定	簡單實現，適用于均勻分布數據	值域均勻且數據量適中的場景
自適應桶排序	O(n + k)	O(n + k)	穩定	動態調整桶大小，適應不均勻分布	數據分布不均勻但需穩定性
分布式桶排序	O(n/k + k)（并行）	O(n + k)	穩定	并行加速，適合大數據或分布式系統	大數據集或高性能計算環境
基于鏈表的桶排序	O(n + k)	O(n + k)	不穩定	鏈表存儲減少擴容開銷，桶內排序可選算法	需頻繁插入/刪除或對內存敏感場景

---

四、關鍵選擇原則

1. 基礎場景：優先使用基礎桶排序，因其簡單且適合均勻分布數據。
2. 數據分布不均勻：自適應桶排序通過動態調整桶大小，減少極端情況的影響。
3. 性能優化：分布式版本利用多線程加速，適合大數據或并行環境。
4. 內存效率：鏈表桶排序減少動態擴容開銷，但需注意桶內排序算法的穩定性。
5. 穩定性需求：若需穩定排序，避免使用鏈表桶排序（若桶內使用快速排序等不穩定算法）。

通過選擇合適的變體，可在特定場景下優化性能或適應數據特性。例如，自適應桶排序解決數據分布問題，而分布式版本提升處理超大數據的效率。