<p>桶排序适用于非负整数、最大值在10⁵以内、元素个数与值域跨度同数量级的场景；关键依据是max_val - min_val决定桶数，需正确偏移索引并合理选择桶内排序方式。</p>
桶排序适合什么范围的整数数组
桶排序不是万能的，它只在数据分布相对均匀、值域可控时才有明显优势。如果你的 int 数组里有负数、极大值（比如超过 10⁶）、或者大量重复值但跨度极大，直接套桶排序会浪费内存或崩溃。典型适用场景是：非负整数、最大值 max_val 在 10⁵ 量级以内、元素个数 n 和 max_val 处于同一数量级。
关键判断点：max_val - min_val 决定桶数量，不是数组长度。别误以为“n 个元素就开 n 个桶”——那是计数排序的思路。
用 vector> 实现桶的常见错误
新手常写成 vector<int> buckets[max_val + 1]</int>（C 风格变长数组），这在 C++ 标准里不合法；或用 vector<int> buckets(max_val + 1)</int>，结果得到的是一个装了 max_val+1 个空 int 的一维 vector，不是“桶容器”。
- 正确做法是：
vector<vector>> buckets(max_val - min_val + 1)</vector>，每个buckets[i]是一个vector<int></int>，存落在第 i 桶里的原始值 - 映射公式必须处理偏移：元素
x落入桶索引x - min_val，不是x直接当索引 - 如果漏掉
min_val偏移，遇到[5, 8, 6]这种数组，min_val=5，你开 9 个桶（0~8），但实际只需桶 0~3（对应 5~8），浪费且易越界
桶内排序选 sort 还是插入排序
单个桶里元素少时，用 std::sort 开销反而比手动插入大；元素多但整体桶数少时，std::sort 更稳。没有银弹，取决于桶的负载均衡程度。
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
实操建议：
- 如果预估每桶平均 ≤ 5 个元素，直接用
for循环 +insert维持桶内有序（省去调用sort的函数栈开销） - 否则统一用
std::sort(buckets[i].begin(), buckets[i].end())，别自己写快排——容易出错且编译器优化过的std::sort在小数组上也不慢 - 注意：桶排序的稳定性取决于桶内排序算法是否稳定。
std::sort不稳定，std::stable_sort可选，但多数场景不需要保序
内存和性能的实际取舍点
桶排序的“线性时间”是理论假设——前提是桶数 k 和输入规模 n 同阶，且每个桶排序是 O(1)。现实中，vector<vector>></vector> 的动态分配、缓存不友好、以及 push_back 的均摊扩容，会让常数项明显增大。
值得检查的细节：
- 提前 reserve：对每个桶
buckets[i].reserve(expected_count)，避免多次 realloc - 避免深拷贝：输出时用
result.insert(result.end(), buckets[i].begin(), buckets[i].end())，而不是循环push_back - 如果值域极大（如
INT_MAX），改用哈希桶（unordered_map<int vector>></int>），但失去 O(1) 索引访问，退化为平均 O(n + k log k)
真正上线前，拿真实数据跑 std::chrono 对比 std::sort，别只看教科书复杂度。桶数设得过大或过小，都可能比直接快排慢。
