桶排序

桶排序是一種以分配為基礎的排序演算法，而非比較排序。它會將值分散到依序排列的桶中，分別排序各桶內的值，再依序收集各桶以產生結果。當值在已知範圍內分布得相當平均時，桶排序特別有效。只要能找到合適的值到桶的映射方式，這種分散再收集的方法就很實用。

桶排序演算法

選擇 k 個桶來涵蓋輸入範圍，再將每個值映射到對應區間的桶。對於 [0, 1) 中的值，一個方便的零起始索引規則是 floor(k * x)：桶 j 涵蓋 [j/k, (j+1)/k)。由於上限不包含在區間內，每個符合條件的值都會映射到 0 至 k - 1 之間的索引。超出此範圍的值需要先正規化，或改用其他映射方式；這個公式並非通用規則。

步驟如下：

1. 為選定的範圍建立 k 個桶。
2. 逐一檢視每個輸入值 x，並將它放入桶 floor(k * x)。
3. 分別排序每個桶。小桶常使用插入排序，也可以使用其他局部排序方法。
4. 按索引順序走訪各桶，將排好序的值附加到結果中。

桶的映射會保留不同桶之間的順序：桶 j 中的每個值都小於桶 j + 1 中的每個值。各桶內排序則負責處理落在相同區間的值。上方連結的插入排序文章介紹了一種簡單的局部排序方法；下方實作則改用 C++ 標準函式庫的 sort 函式。

桶排序範例

在 [0, 1) 上使用十個等長區間，因此索引為 floor(10 * x)。區間依序為 [0.0, 0.1)、[0.1, 0.2)，一路到 [0.9, 1.0)。特別是，0.1 會放入桶 1，因為它是該區間的左端點，包含在區間內。

輸入 (0.22, 0.33, 0.1, 0.45, 0.38, 0.55, 0.21, 0.31) 經分配後如下：

將各桶排序後，桶 2 的內容為 0.21, 0.22，桶 3 的內容為 0.31, 0.33, 0.38；其他非空桶各只有一個值。從桶 0 到桶 9 依序串接後，會得到遞增序列 (0.1, 0.21, 0.22, 0.31, 0.33, 0.38, 0.45, 0.55)。

桶排序演算法實作

這段 C++ 程式使用上方相同的八個值，將它們分配到十個桶中、分別排序，再印出收集後的序列。輸出中顯示的標籤「Sorted values:」維持英文。

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

std::vector<double> bucketSort(const std::vector<double>& values,
                               std::size_t bucketCount) {
    std::vector<std::vector<double>> buckets(bucketCount);

    for (double value : values) {
        const std::size_t index = static_cast<std::size_t>(value * bucketCount);
        buckets[index].push_back(value);
    }

    std::vector<double> result;
    result.reserve(values.size());
    for (auto& bucket : buckets) {
        std::sort(bucket.begin(), bucket.end());
        result.insert(result.end(), bucket.begin(), bucket.end());
    }
    return result;
}

int main() {
    const std::vector<double> values = {0.22, 0.33, 0.1, 0.45,
                                        0.38, 0.55, 0.21, 0.31};
    const std::vector<double> sorted = bucketSort(values, 10);

    std::cout << "Sorted values:";
    for (double value : sorted) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';
    return 0;
}

Sorted values: 0.1 0.21 0.22 0.31 0.33 0.38 0.45 0.55

此函式假設 bucketCount 為正數，且每個值都位於 [0, 1)，因此計算出的索引會落在桶向量的範圍內。若使用其他範圍，請先正規化數值，或在索引前定義適合該範圍的映射方式。提供的執行證據記錄了此程式成功執行，結束代碼為 0，並輸出上方所示的排序序列。

桶排序演算法複雜度

令 n 為值的數量、k 為桶的數量，並以 b_j 表示桶 j 中的值數量。建立桶並分配值需要 O(n + k) 時間。若每個桶都使用 std::sort 等比較排序，額外工作量受各桶局部排序成本總和限制，為 O(Σ b_j log b_j)；因此，單一桶過度擁擠時，總時間可能達到 O(n log n)。當值的分布讓各桶維持較小，通常在 k 與 n 成正比且輸入近似均勻分布時，才可能有預期的近線性表現。僅憑演算法名稱無法保證這種表現。

若在桶內使用插入排序，大小為 b_j 的桶在最壞情況下可能需要 O(b_j²) 時間。此時，擁擠的桶可能使總時間達到二次方。因此，估算效能時，局部排序方法與輸入分布都很重要。

輔助空間為 O(n + k)：桶中存放 n 個值，桶的結構本身則有 k 個項目。這是此實作使用的空間；實作會回傳一個獨立的排序後向量。空間不是 O(n * k)，因為每個值只會存放在一個桶中，不會複製到每個桶裡。