桶排序

桶排序是一种基于分布的排序算法，而不是比较排序。它将数值分散到有序的桶中，分别对每个桶内的数值排序，再按顺序收集各桶以得到结果。当数值在已知范围内分布得较为均匀时，这种算法尤其有效。只要能找到合适的数值到桶的映射，这种分散再收集的方法就很实用。

桶排序算法

选择 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)，因为每个值只存放在一个桶中，而不是复制到每个桶里。