跳轉至
紙質書（簡體中文版）已發行，詳情請見這裡

# 11.8 桶排序

前述幾種排序演算法都屬於“基於比較的排序演算法”，它們透過比較元素間的大小來實現排序。此類排序演算法在最壞情況下的時間複雜度下界為 \(\Omega(n \log n)\) 。接下來，我們將探討幾種“非比較排序演算法”，它們的時間複雜度可以達到線性階。

桶排序（bucket sort）是分治策略的一個典型應用。它透過設定一些具有大小順序的桶，每個桶對應一個數據範圍，將資料平均分配到各個桶中；然後，在每個桶內部分別執行排序；最終按照桶的順序將所有資料合併。

## 11.8.1 演算法流程

考慮一個長度為 \(n\) 的陣列，其元素是範圍 \([0, 1)\) 內的浮點數。桶排序的流程如圖 11-13 所示。

1. 初始化 \(k\) 個桶，將 \(n\) 個元素分配到 \(k\) 個桶中。
2. 對每個桶分別執行排序（這裡採用程式語言的內建排序函式）。
3. 按照桶從小到大的順序合併結果。

圖 11-13 桶排序演算法流程

程式碼如下所示：

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
bucket_sort.py

    def bucket_sort(nums: list[float]):
        """桶排序"""
        # 初始化 k = n/2 個桶，預期向每個桶分配 2 個元素
        k = len(nums) // 2
        buckets = [[] for _ in range(k)]
        # 1. 將陣列元素分配到各個桶中
        for num in nums:
            # 輸入資料範圍為 [0, 1)，使用 num * k 對映到索引範圍 [0, k-1]
            i = int(num * k)
            # 將 num 新增進桶 i
            buckets[i].append(num)
        # 2. 對各個桶執行排序
        for bucket in buckets:
            # 使用內建排序函式，也可以替換成其他排序演算法
            bucket.sort()
        # 3. 走訪桶合併結果
        i = 0
        for bucket in buckets:
            for num in bucket:
                nums[i] = num
                i += 1

bucket_sort.cpp

    /* 桶排序 */
    void bucketSort(vector<float> &nums) {
        // 初始化 k = n/2 個桶，預期向每個桶分配 2 個元素
        int k = nums.size() / 2;
        vector<vector<float>> buckets(k);
        // 1. 將陣列元素分配到各個桶中
        for (float num : nums) {
            // 輸入資料範圍為 [0, 1)，使用 num * k 對映到索引範圍 [0, k-1]
            int i = num * k;
            // 將 num 新增進桶 bucket_idx
            buckets[i].push_back(num);
        }
        // 2. 對各個桶執行排序
        for (vector<float> &bucket : buckets) {
            // 使用內建排序函式，也可以替換成其他排序演算法
            sort(bucket.begin(), bucket.end());
        }
        // 3. 走訪桶合併結果
        int i = 0;
        for (vector<float> &bucket : buckets) {
            for (float num : bucket) {
                nums[i++] = num;
            }
        }
    }

bucket_sort.java

    /* 桶排序 */
    void bucketSort(float[] nums) {
        // 初始化 k = n/2 個桶，預期向每個桶分配 2 個元素
        int k = nums.length / 2;
        List<List<Float>> buckets = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            buckets.add(new ArrayList<>());
        }
        // 1. 將陣列元素分配到各個桶中
        for (float num : nums) {
            // 輸入資料範圍為 [0, 1)，使用 num * k 對映到索引範圍 [0, k-1]
            int i = (int) (num * k);
            // 將 num 新增進桶 i
            buckets.get(i).add(num);
        }
        // 2. 對各個桶執行排序
        for (List<Float> bucket : buckets) {
            // 使用內建排序函式，也可以替換成其他排序演算法
            Collections.sort(bucket);
        }
        // 3. 走訪桶合併結果
        int i = 0;
        for (List<Float> bucket : buckets) {
            for (float num : bucket) {
                nums[i++] = num;
            }
        }
    }

bucket_sort.cs

    /* 桶排序 */
    void BucketSort(float[] nums) {
        // 初始化 k = n/2 個桶，預期向每個桶分配 2 個元素
        int k = nums.Length / 2;
        List<List<float>> buckets = [];
        for (int i = 0; i < k; i++) {
            buckets.Add([]);
        }
        // 1. 將陣列元素分配到各個桶中
        foreach (float num in nums) {
            // 輸入資料範圍為 [0, 1)，使用 num * k 對映到索引範圍 [0, k-1]
            int i = (int)(num * k);
            // 將 num 新增進桶 i
            buckets[i].Add(num);
        }
        // 2. 對各個桶執行排序
        foreach (List<float> bucket in buckets) {
            // 使用內建排序函式，也可以替換成其他排序演算法
            bucket.Sort();
        }
        // 3. 走訪桶合併結果
        int j = 0;
        foreach (List<float> bucket in buckets) {
            foreach (float num in bucket) {
                nums[j++] = num;
            }
        }
    }

bucket_sort.go

    /* 桶排序 */
    func bucketSort(nums []float64) {
        // 初始化 k = n/2 個桶，預期向每個桶分配 2 個元素
        k := len(nums) / 2
        buckets := make([][]float64, k)
        for i := 0; i < k; i++ {
            buckets[i] = make([]float64, 0)
        }
        // 1. 將陣列元素分配到各個桶中
        for _, num := range nums {
            // 輸入資料範圍為 [0, 1)，使用 num * k 對映到索引範圍 [0, k-1]
            i := int(num * float64(k))
            // 將 num 新增進桶 i
            buckets[i] = append(buckets[i], num)
        }
        // 2. 對各個桶執行排序
        for i := 0; i < k; i++ {
            // 使用內建切片排序函式，也可以替換成其他排序演算法
            sort.Float64s(buckets[i])
        }
        // 3. 走訪桶合併結果
        i := 0
        for _, bucket := range buckets {
            for _, num := range bucket {
                nums[i] = num
                i++
            }
        }
    }

bucket_sort.swift

    /* 桶排序 */
    func bucketSort(nums: inout [Double]) {
        // 初始化 k = n/2 個桶，預期向每個桶分配 2 個元素
        let k = nums.count / 2
        var buckets = (0 ..< k).map { _ in [Double]() }
        // 1. 將陣列元素分配到各個桶中
        for num in nums {
            // 輸入資料範圍為 [0, 1)，使用 num * k 對映到索引範圍 [0, k-1]
            let i = Int(num * Double(k))
            // 將 num 新增進桶 i
            buckets[i].append(num)
        }
        // 2. 對各個桶執行排序
        for i in buckets.indices {
            // 使用內建排序函式，也可以替換成其他排序演算法
            buckets[i].sort()
        }
        // 3. 走訪桶合併結果
        var i = nums.startIndex
        for bucket in buckets {
            for num in bucket {
                nums[i] = num
                i += 1
            }
        }
    }

bucket_sort.js

    /* 桶排序 */
    function bucketSort(nums) {
        // 初始化 k = n/2 個桶，預期向每個桶分配 2 個元素
        const k = nums.length / 2;
        const buckets = [];
        for (let i = 0; i < k; i++) {
            buckets.push([]);
        }
        // 1. 將陣列元素分配到各個桶中
        for (const num of nums) {
            // 輸入資料範圍為 [0, 1)，使用 num * k 對映到索引範圍 [0, k-1]
            const i = Math.floor(num * k);
            // 將 num 新增進桶 i
            buckets[i].push(num);
        }
        // 2. 對各個桶執行排序
        for (const bucket of buckets) {
            // 使用內建排序函式，也可以替換成其他排序演算法
            bucket.sort((a, b) => a - b);
        }
        // 3. 走訪桶合併結果
        let i = 0;
        for (const bucket of buckets) {
            for (const num of bucket) {
                nums[i++] = num;
            }
        }
    }

bucket_sort.ts

    /* 桶排序 */
    function bucketSort(nums: number[]): void {
        // 初始化 k = n/2 個桶，預期向每個桶分配 2 個元素
        const k = nums.length / 2;
        const buckets: number[][] = [];
        for (let i = 0; i < k; i++) {
            buckets.push([]);
        }
        // 1. 將陣列元素分配到各個桶中
        for (const num of nums) {
            // 輸入資料範圍為 [0, 1)，使用 num * k 對映到索引範圍 [0, k-1]
            const i = Math.floor(num * k);
            // 將 num 新增進桶 i
            buckets[i].push(num);
        }
        // 2. 對各個桶執行排序
        for (const bucket of buckets) {
            // 使用內建排序函式，也可以替換成其他排序演算法
            bucket.sort((a, b) => a - b);
        }
        // 3. 走訪桶合併結果
        let i = 0;
        for (const bucket of buckets) {
            for (const num of bucket) {
                nums[i++] = num;
            }
        }
    }

bucket_sort.dart

    /* 桶排序 */
    void bucketSort(List<double> nums) {
      // 初始化 k = n/2 個桶，預期向每個桶分配 2 個元素
      int k = nums.length ~/ 2;
      List<List<double>> buckets = List.generate(k, (index) => []);

      // 1. 將陣列元素分配到各個桶中
      for (double _num in nums) {
        // 輸入資料範圍為 [0, 1)，使用 _num * k 對映到索引範圍 [0, k-1]
        int i = (_num * k).toInt();
        // 將 _num 新增進桶 bucket_idx
        buckets[i].add(_num);
      }
      // 2. 對各個桶執行排序
      for (List<double> bucket in buckets) {
        bucket.sort();
      }
      // 3. 走訪桶合併結果
      int i = 0;
      for (List<double> bucket in buckets) {
        for (double _num in bucket) {
          nums[i++] = _num;
        }
      }
    }

bucket_sort.rs

    /* 桶排序 */
    fn bucket_sort(nums: &mut [f64]) {
        // 初始化 k = n/2 個桶，預期向每個桶分配 2 個元素
        let k = nums.len() / 2;
        let mut buckets = vec![vec![]; k];
        // 1. 將陣列元素分配到各個桶中
        for &num in nums.iter() {
            // 輸入資料範圍為 [0, 1)，使用 num * k 對映到索引範圍 [0, k-1]
            let i = (num * k as f64) as usize;
            // 將 num 新增進桶 i
            buckets[i].push(num);
        }
        // 2. 對各個桶執行排序
        for bucket in &mut buckets {
            // 使用內建排序函式，也可以替換成其他排序演算法
            bucket.sort_by(|a, b| a.partial_cmp(b).unwrap());
        }
        // 3. 走訪桶合併結果
        let mut i = 0;
        for bucket in buckets.iter() {
            for &num in bucket.iter() {
                nums[i] = num;
                i += 1;
            }
        }
    }

bucket_sort.c

    /* 桶排序 */
    void bucketSort(float nums[], int n) {
        int k = n / 2;                                 // 初始化 k = n/2 個桶
        int *sizes = malloc(k * sizeof(int));          // 記錄每個桶的大小
        float **buckets = malloc(k * sizeof(float *)); // 動態陣列的陣列（桶）
        // 為每個桶預分配足夠的空間
        for (int i = 0; i < k; ++i) {
            buckets[i] = (float *)malloc(n * sizeof(float));
            sizes[i] = 0;
        }
        // 1. 將陣列元素分配到各個桶中
        for (int i = 0; i < n; ++i) {
            int idx = (int)(nums[i] * k);
            buckets[idx][sizes[idx]++] = nums[i];
        }
        // 2. 對各個桶執行排序
        for (int i = 0; i < k; ++i) {
            qsort(buckets[i], sizes[i], sizeof(float), compare);
        }
        // 3. 合併排序後的桶
        int idx = 0;
        for (int i = 0; i < k; ++i) {
            for (int j = 0; j < sizes[i]; ++j) {
                nums[idx++] = buckets[i][j];
            }
            // 釋放記憶體
            free(buckets[i]);
        }
    }

bucket_sort.kt

    /* 桶排序 */
    fun bucketSort(nums: FloatArray) {
        // 初始化 k = n/2 個桶，預期向每個桶分配 2 個元素
        val k = nums.size / 2
        val buckets = mutableListOf<MutableList<Float>>()
        for (i in 0..<k) {
            buckets.add(mutableListOf())
        }
        // 1. 將陣列元素分配到各個桶中
        for (num in nums) {
            // 輸入資料範圍為 [0, 1)，使用 num * k 對映到索引範圍 [0, k-1]
            val i = (num * k).toInt()
            // 將 num 新增進桶 i
            buckets[i].add(num)
        }
        // 2. 對各個桶執行排序
        for (bucket in buckets) {
            // 使用內建排序函式，也可以替換成其他排序演算法
            bucket.sort()
        }
        // 3. 走訪桶合併結果
        var i = 0
        for (bucket in buckets) {
            for (num in bucket) {
                nums[i++] = num
            }
        }
    }

bucket_sort.rb

    ### 桶排序 ###
    def bucket_sort(nums)
      # 初始化 k = n/2 個桶，預期向每個桶分配 2 個元素
      k = nums.length / 2
      buckets = Array.new(k) { [] }

      # 1. 將陣列元素分配到各個桶中
      nums.each do |num|
        # 輸入資料範圍為 [0, 1)，使用 num * k 對映到索引範圍 [0, k-1]
        i = (num * k).to_i
        # 將 num 新增進桶 i
        buckets[i] << num
      end

      # 2. 對各個桶執行排序
      buckets.each do |bucket|
        # 使用內建排序函式，也可以替換成其他排序演算法
        bucket.sort!
      end

      # 3. 走訪桶合併結果
      i = 0
      buckets.each do |bucket|
        bucket.each do |num|
          nums[i] = num
          i += 1
        end
      end
    end

視覺化執行

全螢幕觀看 >

## 11.8.2 演算法特性

桶排序適用於處理體量很大的資料。例如，輸入資料包含 100 萬個元素，由於空間限制，系統記憶體無法一次性載入所有資料。此時，可以將資料分成 1000 個桶，然後分別對每個桶進行排序，最後將結果合併。

- 時間複雜度為 \(O(n + k)\) ：假設元素在各個桶內平均分佈，那麼每個桶內的元素數量為 \(\frac{n}{k}\) 。假設排序單個桶使用 \(O(\frac{n}{k} \log\frac{n}{k})\) 時間，則排序所有桶使用 \(O(n \log\frac{n}{k})\) 時間。當桶數量 \(k\) 比較大時，時間複雜度則趨向於 \(O(n)\) 。合併結果時需要走訪所有桶和元素，花費 \(O(n + k)\) 時間。在最差情況下，所有資料被分配到一個桶中，且排序該桶使用 \(O(n^2)\) 時間。
- 空間複雜度為 \(O(n + k)\)、非原地排序：需要藉助 \(k\) 個桶和總共 \(n\) 個元素的額外空間。
- 桶排序是否穩定取決於排序桶內元素的演算法是否穩定。

## 11.8.3 如何實現平均分配

桶排序的時間複雜度理論上可以達到 \(O(n)\) ，關鍵在於將元素均勻分配到各個桶中，因為實際資料往往不是均勻分佈的。例如，我們想要將淘寶上的所有商品按價格範圍平均分配到 10 個桶中，但商品價格分佈不均，低於 100 元的非常多，高於 1000 元的非常少。若將價格區間平均劃分為 10 個，各個桶中的商品數量差距會非常大。

為實現平均分配，我們可以先設定一條大致的分界線，將資料粗略地分到 3 個桶中。分配完畢後，再將商品較多的桶繼續劃分為 3 個桶，直至所有桶中的元素數量大致相等。

如圖 11-14 所示，這種方法本質上是建立一棵遞迴樹，目標是讓葉節點的值儘可能平均。當然，不一定要每輪將資料劃分為 3 個桶，具體劃分方式可根據資料特點靈活選擇。

圖 11-14 遞迴劃分桶

如果我們提前知道商品價格的機率分佈，則可以根據資料機率分佈設定每個桶的價格分界線。值得注意的是，資料分佈並不一定需要特意統計，也可以根據資料特點採用某種機率模型進行近似。

如圖 11-15 所示，我們假設商品價格服從正態分佈，這樣就可以合理地設定價格區間，從而將商品平均分配到各個桶中。

圖 11-15 根據機率分佈劃分桶

##### 歡迎在評論區留下你的見解、問題或建議