C++ 排序算法实践：桶排序，分而治之，各桶归位

假设你有一堆 0 到 1 之间的小数要排序。

与其两两比较，不如准备 10 个桶，分别装 [0, 0.1)、[0.1, 0.2)…… [0.9, 1.0) 的数。

每个桶里的数不多，简单排一下就行。

最后按桶号从 0 到 9 把所有桶里的数依次倒出来，这样全局就有序了。

桶排序（Bucket Sort） 就是这个思路：把数据均匀分配到若干个桶里，各桶内部单独排序，最后合并所有桶。

它是计数排序的”泛化版本”，计数排序相当于每个桶只装一种值，桶排序则允许一个桶装一个范围的值。

---

它是什么

核心思想 将数据按规则分配到多个桶中，使得落在同一个桶内的数据范围较小且有序关系简单；对各桶分别排序后，按桶序合并即得全局有序结果。

分类整理：先把东西粗略归类到不同篮子里，然后在每个篮子内部再细排。

桶排序的关键就在于均匀分布。

如果数据均匀分散到各个桶里，每个桶的数据量就会很小，桶内排序的成本就极低。

与计数排序的关系

特征	计数排序	桶排序
每个桶装什么	只装相同值的元素	装一定范围内的所有值
桶内操作	无需排序（直接输出）	需要排序（桶内元素少时插入排序更优）
适用数据	整数，范围小	浮点数或均匀分布的数据
时间	O(n+k)	平均 O(n)，最坏 O(n log n)
稳定性	取决于实现	取决于桶内排序算法

可以把计数排序看作桶排序的一个特例：桶的数量 = 数据范围，每个桶只存一个值。

伪代码

// 仅为示意（针对 [0,1) 范围浮点数）
function bucketSort(arr, n):
    创建 n 个空桶 buckets[0..n-1]

    // Step 1: 分桶
    for each x in arr:
        idx = floor(x * n)
        buckets[idx].append(x)

    // Step 2: 各桶内排序
    for each bucket in buckets:
        if bucket 不空:
            // 桶内元素少时插入排序更优，演示代码用 std::sort 简化
            sort(bucket)         

    // Step 3: 合并
    result = []
    for i = 0 to n-1:
        result.extend(buckets[i])

    return result

下面用流程图拆解分桶、桶内排序与合并过程。

工作原理流程图

对应伪代码的整体流程：

flowchart LR
    A(["输入数组 arr"]) --> B["创建 k 个空桶<br/>k 通常 = n"]
    B --> C["遍历 arr<br/>arr[i] 放入第 floor(arr[i]*k) 个桶"]
    C --> D["对每个非空桶独立排序<br/>桶内少时插入排序更优"]
    D --> E["按桶 0,1,...,k-1 顺序<br/>合并所有桶内元素"]
    E --> F(["输出有序数组"])

逐步演示

用 [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]（n=10，10 个桶）跑一遍：

初始数组 (10 个元素, 范围 [0,1)): [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]

Step 1 - 分桶:
  0.78 -> 桶[7]    0.17 -> 桶[1]    0.39 -> 桶[3]
  0.26 -> 桶[2]    0.72 -> 桶[7]    0.94 -> 桶[9]
  0.21 -> 桶[2]    0.12 -> 桶[1]    0.23 -> 桶[2]
  0.68 -> 桶[6]

Step 2 - 各桶内排序:
  桶[1]: [0.12, 0.17]        (2 个元素)
  桶[2]: [0.21, 0.23, 0.26]   (3 个元素)
  桶[3]: [0.39]               (1 个元素)
  桶[6]: [0.68]               (1 个元素)
  桶[7]: [0.72, 0.78]         (2 个元素)
  桶[9]: [0.94]               (1 个元素)

Step 3 - 按桶顺序合并:
最终结果: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

每个桶平均只有 1-3 个元素，桶内仅常数个元素，排序成本接近 O(1)。

总工作量接近线性。

---

能解决什么问题

适用场景

场景	为什么适合
浮点数均匀分布	经典应用场景，如 [0,1) 均匀分布的小数
已知大致分布的数据	可以据此设计桶的范围和数量
外部排序的预处理	大文件可以先分桶，各桶独立排序后合并

局限性

局限	说明
依赖数据分布	如果数据集中在一个桶里，退化为对该桶的全排序
额外的桶管理开销	需要维护多个容器
不是原地排序	需要额外的桶空间
稳定性不确定	取决于桶内使用的排序算法

退化场景演示

如果数据高度集中：

退化数据: [0.01, 0.02, 0.03, 0.04, 0.05, 0.91, 0.92, 0.93, 0.94, 0.95]

分桶结果:
  桶[0]: [0.01, 0.02, 0.03, 0.04, 0.05]   (5 个元素!)
  桶[9]: [0.91, 0.92, 0.93, 0.94, 0.95]   (5 个元素!)

此时桶内排序的工作量 ≈ 对 5 个元素做全排序

虽然这个例子中退化后仍然可控，但如果 n=100 万且全部集中在 1 个桶里，就退化为对全量数据的常规排序了（std::sort 为 O(n log n)，插入排序为 O(n²)）。

---

C++ 实现与复杂度分析

通用 C++ 模板实现 可直接复用的代码：

// 通用模板：适用于任意数值类型（int / double / float 等）
template <typename T>
void bucketSort(std::vector<T>& arr, int bucketCount = 0) {
    int n = static_cast<int>(arr.size());
    if (n <= 1) return;
    if (bucketCount <= 0) bucketCount = n;          // 默认桶数 = 元素数

    // 确定数据范围
    auto [minIt, maxIt] = std::minmax_element(arr.begin(), arr.end());
    T minVal = *minIt, maxVal = *maxIt;
    if (minVal == maxVal) return;

    // 创建桶
    std::vector<std::vector<T>> buckets(bucketCount);

    // 分桶：将每个元素映射到对应桶
    double range = static_cast<double>(maxVal - minVal);
    for (const T& val : arr) {
        int idx = static_cast<int>(
            bucketCount * static_cast<double>(val - minVal) / range);
        if (idx >= bucketCount) idx = bucketCount - 1;   // 边界保护
        buckets[idx].push_back(val);
    }

    // 各桶内部排序 + 按桶号合并
    arr.clear();
    for (auto& bucket : buckets) {
        std::sort(bucket.begin(), bucket.end());
        arr.insert(arr.end(), bucket.begin(), bucket.end());
    }
}

时间复杂度怎么算

分三步计算：

步骤	操作	平均复杂度	最坏复杂度
分桶	遍历 + 计算	O(n)	O(n)
桶内排序	取决于桶内元素数	O(n)（均匀时每桶 O(1)）	O(n log n)（std::sort）/ O(n²)（插入排序）
合并	遍历所有桶	O(n)	O(n)

平均情况（数据均匀分布）： 每个桶期望有 n/k = O(1) 个元素（设 k=n），桶内排序接近常数时间 → 总计 O(n)。

最坏情况（所有元素进同一桶）： 退化为对单个桶做全量排序。若桶内用 std::sort（演示代码做法），最坏 O(n log n)；若桶内用插入排序（元素少时更优），最坏 O(n²)。

情况	时间复杂度	条件
最好	O(n)	每桶 ≤ 1 个元素
平均	O(n)	数据均匀分布
最坏	O(n log n)（std::sort）/ O(n²)（插入排序）	所有元素落入同一桶

空间复杂度

n 个桶 + n 个元素的总副本 → O(n + k)，其中 k 为桶数（通常 k=n）→ O(n)。

小结算法：时间平均 O(n)（最坏 O(n log n)，用插入排序则为 O(n²)）、空间 O(n)、稳定性取决于桶内排序、适用于均匀分布的数据。

---

全文小结

• 是什么：按映射规则把数据分到若干桶，各桶独立排序后合并。是计数排序的泛化版。
• 解决什么 / 用在哪：均匀分布的浮点数排序；已知分布数据的快速排序；外部排序预处理。
• 局限：数据分布不均时退化；稳定性取决于桶内算法；需要额外桶空间。
• 复杂度怎么算：分桶 O(n) + 合并 O(n) 固定；桶内排序决定总复杂度。均匀时 O(n)，最坏 O(n log n)（std::sort）或 O(n²)（插入排序）。空间 O(n)。