桶排序适合数据均匀分布在有限整数区间（如[0,1000)）且数量级适中（如1e5）的场景；不适用浮点数未离散化、负数未偏移、值域极大样本极少等情况。
桶排序适合什么数据场景
桶排序不是万能的，它只在输入数据均匀分布在某个范围时才高效。如果你要排序的是 std::vector<int></int>，且已知所有值都在 [0, 1000) 范围内、数量级在 1e5 左右，桶排序就比 std::sort 更快；但若数据极度偏斜（比如 99% 的数集中在 0~10，剩下分散在 900~1000），桶数没设好就会退化成链表遍历，性能反而更差。
- 适用前提：数据可映射到有限整数区间，且分布相对均匀
- 不适用：浮点数未做离散化、负数未偏移、值域极大（如
int全范围）却样本极少 - 常见误用：直接对
std::vector<double></double>做桶，没做归一化或缩放，导致下标越界或桶空满不均
如何正确分配桶和映射元素
核心是把每个元素 x 映射到桶索引 index = (x - min_val) / bucket_range，其中 bucket_range 是每个桶覆盖的数值宽度。必须确保 index 不越界，且最后一个桶能收容最大值。
- 先遍历一次找
min_val和max_val，避免假设数据从 0 开始 - 桶数量通常取
sqrt(n)或n（n 是元素个数），太多浪费内存，太少失去并行优势 - 映射时用整数除法，但要注意：若
x == max_val，(x - min_val) / bucket_range可能等于桶总数，需手动截断为bucket_count - 1
C++ 实现中容易崩的三个细节
很多网上代码在边界、类型、内存上栽跟头，不是逻辑错，而是运行时崩溃或结果错位。
-
bucket_range必须是double类型计算，否则整数除法导致映射错误（例如(999 - 0) / 1000得 0） - 桶容器建议用
std::vector<:vector>></:vector>，不要用std::vector<:list>></:list>——std::vector局部性更好，且插入末尾均摊 O(1) - 最后合并时，不能对每个桶调用
std::sort后再insert，而应先reserve总容量，再用std::move或std::copy避免重复拷贝
#include <vector>
#include <algorithm>
#include <cmath>
<p>std::vector<int> bucket_sort(std::vector<int> arr) {
if (arr.size() <= 1) return arr;</p><pre class='brush:php;toolbar:false;'>int min_val = *std::min_element(arr.begin(), arr.end());
int max_val = *std::max_element(arr.begin(), arr.end());
int n = arr.size();
int bucket_count = std::max(1, static_cast<int>(std::sqrt(n)));
double bucket_range = static_cast<double>(max_val - min_val + 1) / bucket_count;
std::vector<std::vector<int>> buckets(bucket_count);
for (int x : arr) {
int idx = static_cast<int>((x - min_val) / bucket_range);
if (idx >= bucket_count) idx = bucket_count - 1; // 防止 max_val 溢出
buckets[idx].push_back(x);
}
std::vector<int> result;
result.reserve(n);
for (auto& bucket : buckets) {
if (!bucket.empty()) {
std::sort(bucket.begin(), bucket.end()); // 小桶用快排足够
result.insert(result.end(), bucket.begin(), bucket.end());
}
}
return result;}
立即学习“C++免费学习笔记（深入）”；
什么时候该放弃桶排序改用其他方法
当你发现需要额外做太多预处理，就说明桶排序不是最优解。比如：
- 输入含大量负数和正数，且你不想手动平移（
+offset），那基数排序或std::sort更省心 - 数据是字符串或自定义结构体，无法自然映射到数值区间，强行哈希分桶会破坏稳定性且难调试
- 内存受限环境（如嵌入式），而桶数量设为
n导致空间复杂度 O(n²)，此时归并排序的 O(n) 额外空间反而更可控
桶排序真正的价值不在“一定更快”，而在“你知道数据特性时，能把它压到接近 O(n)”。一旦不确定分布，先跑一遍直方图分析，再决定桶数和映射方式——这点常被跳过，结果就是写了一堆代码，效果还不如 std::sort。
