桶排序适合均匀分布的数据，如0–999整数或[0.0,1.0)浮点数；值域偏斜、稀疏或无界时性能退化；需先求min/max、防负数映射、钳位边界、慎用浮点归一化。
桶排序适合什么数据分布？
桶排序不是万能的，它只在输入数据**均匀分布在某个区间内**时才能达到线性时间。比如对 0–999 之间的整数、或 [0.0, 1.0) 区间的浮点数做排序，效果最好。一旦数据严重偏斜（比如全集中在 1–10，但范围声明为 0–10000），桶就大量空转，空间浪费且实际性能退化到 O(n²)。
- 适用场景：
vector<int></int>中元素值域明确且相对紧凑；或已知数据服从近似均匀分布 - 不适用场景：值域极大（如
int64_t全范围）、稀疏、或完全随机无界（如用户输入的任意长字符串哈希） - 关键判断点：你能否用 O(1) 时间把每个元素映射到一个桶索引？不能就别硬套
怎么写一个安全的 int 桶排序实现？
直接开 vector<vector>></vector> 容易崩——如果数据含负数或值域没预估准，bucket[i] 下标越界是常事。正确做法是先扫一遍找 min_val 和 max_val，再按需分配桶数。
- 桶数量建议设为
n（输入长度），避免单桶过大；每个桶用vector<int></int>动态存，不预分配容量 - 映射公式必须防负数：
index = (val - min_val) * n / (max_val - min_val + 1)，注意分母加 1 防除零 - 别忘了边界处理：当
val == max_val时，index可能等于n，要手动钳位到n-1 - 示例片段：
int index = (val - min_val) * n / (max_val - min_val + 1); if (index >= n) index = n - 1;
为什么 std::sort 比手写桶排序还快？
实测中，对小于 10⁵ 的 vector<int></int>，std::sort 常比桶排序快 2–3 倍。不是因为算法理论慢，而是现代 std::sort 是混合排序（introsort），缓存友好、分支预测高效，而桶排序涉及多次内存跳转、动态分配、以及小数组上插入排序的常数开销更大。
- 桶排序优势只在 n > 10⁶ 且数据高度可控时才稳定显现
- 编译器对
std::sort的优化极深（如 SSO、内联、向量化比较），手写很难超越 - 如果真要极致性能，优先考虑
std::sort+ 自定义比较器，而非过早换桶排序
float 类型桶排序怎么避免精度坑？
对 float 或 double 做桶排序，最常见错误是直接用 (x - min) / (max - min) 算归一化位置，结果因浮点误差导致 x == max 时算出 1.0000001，乘以桶数后越界。
立即学习“C++免费学习笔记（深入）”；
- 务必用
std::nextafter(max_val, std::numeric_limits<double>::max())</double>扩展上界再归一化 - 更稳妥做法：转成整数桶——比如保留 6 位小数，
static_cast<long long>(x * 1e6)</long>，再按整数桶排 - 注意
NaN和无穷大会直接让整个映射崩溃，排序前必须过滤或抛异常 - 错误现象举例：
std::out_of_range报在bucket.at(index)，其实根源是浮点映射溢出
桶排序真正的难点不在代码长短，而在值域预判和边界钳位——少一次 if (index >= n) index = n - 1，就可能让程序在特定输入下静默错排。
