桶排序适合数据均匀分布、范围已知且相对集中的场景，如0~999的整数排序；不适用于值域远大于元素个数、稀疏或含未平移负数的数据。
桶排序适合什么数据场景
桶排序不是万能的，它只在数据均匀分布、范围已知且相对集中时才有明显优势。比如对 vector<int></int> 中 0~999 的整数排序，开 1000 个桶就非常高效；但若数据是 {1, 1000000, 5, 999999}，桶数组会极度稀疏，空间浪费严重，甚至直接 OOM。
- 数据必须是非负整数（或能映射为非负整数索引，如浮点数归一化后 × 桶数取整）
- 值域范围
max_val - min_val 不宜远大于元素个数 n，否则桶太多、空桶多、缓存不友好
- 若含负数，需整体平移：先遍历得
min_val，所有数减 min_val，排序后再加回
手写核心逻辑：分配 + 局部排序 + 合并
桶排序本质是「分而治之」：把值域切分成若干区间（桶），每个桶内用快排/插入排序，最后按桶序合并。C++ 中最轻量的做法是用 vector<vector>></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() <= 1) return;
int min_val = *min_element(arr.begin(), arr.end());
int max_val = *max_element(arr.begin(), arr.end());
int n = arr.size();
int bucket_count = n;
vector<vector<int>> 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;
}
}
max_val - min_val 不宜远大于元素个数 n，否则桶太多、空桶多、缓存不友好min_val，所有数减 min_val，排序后再加回vector<vector>></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() <= 1) return;
int min_val = *min_element(arr.begin(), arr.end());
int max_val = *max_element(arr.begin(), arr.end());
int n = arr.size();
int bucket_count = n;
vector<vector<int>> 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 之间），才值得手写定制桶排序
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，多次调用函数时残留旧数据std::sort 快，除非你确定数据满足强假设（均匀、整数、值域可控）且已做过 profiling 验证。
- 时间复杂度理论是 O(n + k)，k 是桶数，但常数大：多次内存分配、二级指针跳转、缓存不连续
-
std::sort是混合排序（introsort），对随机数据实际更快，且无额外空间 - 如果只是想稳定、少写代码，直接用
std::sort；只有当你明确知道输入模式（比如传感器采样值总在 200~220 之间），才值得手写定制桶排序
边界情况比想象中多，尤其是索引截断和空桶跳过——别省那几行 if (!bucket.empty())。
