桶排序适合数据均匀分布、范围已知且相对集中的场景，如0~999的整数排序；不适用于值域远大于元素个数、稀疏或含未平移负数的数据。

桶排序适合什么数据场景 桶排序不是万能的，它只在数据均匀分布、范围已知且相对集中时才有明显优势。比如对 vector 中 0~999 的整数排序，开 1000 个桶就非常高效；但若数据是 {1, 1000000, 5, 999999}，桶数组会极度稀疏，空间浪费严重，甚至直接 OOM。

• 数据必须是非负整数（或能映射为非负整数索引，如浮点数归一化后 × 桶数取整）
• 值域范围 max_val - min_val 不宜远大于元素个数 n，否则桶太多、空桶多、缓存不友好
• 若含负数，需整体平移：先遍历得 min_val，所有数减 min_val，排序后再加回

手写核心逻辑：分配 + 局部排序 + 合并 桶排序本质是「分而治之」：把值域切分成若干区间（桶），每个桶内用快排/插入排序，最后按桶序合并。C++ 中最轻量的做法是用 vector> 表示桶数组。

• 桶数量通常取 n（元素个数），这样平均每个桶约 1 个元素，局部排序开销小
• 分配时用 (num - min_val) / bucket_size 算桶下标，bucket_size = (max_val - min_val) / n + 1 防止除零和越界
• 每个桶内部推荐用 std::sort（小数据时 std::sort 自动切到插入排序，无需手写）

void bucketSort(vector<int>& arr) {
    if (arr.size() > buckets(bucket_count);
<pre class="brush:php;toolbar:false;">// 计算桶容量，避免除零
int bucket_size = (max_val - min_val) / n + 1;
for (int num : arr) {
    int idx = (num - min_val) / bucket_size;
    idx = min(idx, bucket_count - 1); // 防止 max_val 落在最后一桶外
    buckets[idx].push_back(num);
}

int i = 0;
for (auto& bucket : buckets) {
    sort(bucket.begin(), bucket.end()); // 桶内排序
    for (int num : bucket) {
        arr[i++] = num;
    }
}

}

常见错误：越界、空桶、浮点映射失准 手写时最容易在索引计算上翻车：

• 忘记处理 min_val > 0 或负数，导致 num - min_val 为负，再除正数仍为负，idx 变成负数 → 访问 buckets[-1] → 未定义行为
• bucket_size 用整数除法直接写 (max_val - min_val) / n，当值域小于 n 时结果为 0 → 除零崩溃
• 对浮点数做桶排序时，用 floor(x * bucket_count) 但没处理 x == 1.0 边界，导致索引等于 bucket_count → 越界
• 忘记清空或复用 buckets，多次调用函数时残留旧数据

性能与替代方案对比 纯手写桶排序在 C++ 中 rarely 比 std::sort 快，除非你确定数据满足强假设（均匀、整数、值域可控）且已做过 profiling 验证。

• 时间复杂度理论是 O(n + k)，k 是桶数，但常数大：多次内存分配、二级指针跳转、缓存不连续
• std::sort 是混合排序（introsort），对随机数据实际更快，且无额外空间
• 如果只是想稳定、少写代码，直接用 std::sort；只有当你明确知道输入模式（比如传感器采样值总在 200~220 之间），才值得手写定制桶排序

边界情况比想象中多，尤其是索引截断和空桶跳过——别省那几行 if (!bucket.empty())。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！