企业官网建设流程全解析

前言

桶排序（bucket sort）不是"比较排序"里的那种两两比较，它先把元素按值域分散到若干个桶里，每个桶内部再单独排序，最后按桶的顺序把结果拼起来。它的平均复杂度可以做到 O(n + k)（k 为桶数），比 O(n log n) 的比较排序更快——但这个结论有前提：元素要均匀分布在值域上，且桶的划分要合理。

常见的误解有两个。第一，把桶排序当成"永远线性"的算法：如果所有元素都落进同一个桶，桶内排序退化成对 n 个元素排序，整体就是 O(n log n)，最坏情况甚至因为桶内使用插入排序而达到 O(n²)。第二，把桶排序和计数排序、基数排序混为一谈：计数排序按"每个可能的值"计数，桶排序按"值域区间"分桶，基数排序按"每一位"分轮。

本文讲清三件事：分桶的映射怎么设计、复杂度在什么条件下成立、以及浮点与整数两种输入的实现细节。代码以 C++17 为基准，只用标准库。

一、原理：分散、桶内排序、按序合并

桶排序分三步：

1. 
   
2. 分桶：把值域[min, max]均匀划分成k个区间，每个元素按自己的值落到对应桶里；
3. 
   
4. 桶内排序：对每个非空桶单独排序（元素少时常用插入排序，多时可直接用std::sort）；
5. 
   
6. 合并：按桶的区间从小到大，把各桶元素依次写回原数组。
7. 
   

正确性依赖一个显然的性质：第i个桶里的所有元素都不大于第i+1个桶里的任何元素。因此只要桶内有序，整体就有序，不需要跨桶比较。

和另外两种"非比较"排序的区别：

计数排序可以看作"桶数等于值域大小、每个桶至多一个值"的特例；基数排序可以看作"多轮桶排序，每轮按一位分桶"。

二、复杂度与成立条件

设元素个数为n，桶数为k。分桶是 O(n)，合并是 O(n + k)，桶内排序的总代价取决于分布：

• 
  
• 均匀分布时，每个桶期望有n/k个元素，桶内排序总代价约为k · (n/k) log(n/k) = n log(n/k)。取k ≈ n时接近 O(n)。
• 
  
• 全部集中在一个桶时，退化为一次 O(n log n) 的排序（若桶内用插入排序则是 O(n²)）。
• 
  
• 桶数k过大时，空桶的遍历与内存开销占主导，复杂度里的+k不可忽略。
• 
  

空间上需要k个桶的容器，加上元素本身的一份副本，是 O(n + k)。桶排序不是原地排序。

稳定性取决于桶内排序算法与合并顺序：合并时按桶的顺序、桶内按排序结果的顺序写出，只要桶内排序稳定，整体就稳定。std::sort不保证稳定，需要稳定语义时应使用std::stable_sort。

三、浮点数版本

最典型的场景是把[0, 1)区间的浮点数排序。映射很直接：idx = floor(x * k)。

// 适用于 C++17：要求所有元素位于 [0, 1)
#include <algorithm>
#include <cstddef>
#include <vector>

void bucket_sort_unit(std::vector<double>& a) {
if (a.size() < 2) return;

const std::size_t n = a.size();
std::vector<std::vector<double>> buckets(n);

for (double x : a) {
std::size_t idx = static_cast<std::size_t>(x * static_cast<double>(n));
if (idx >= n) idx = n - 1; // x 恰为 1.0 或浮点舍入越界
buckets[idx].push_back(x);
}

std::size_t k = 0;
for (auto& bucket : buckets) {
std::sort(bucket.begin(), bucket.end());
for (double x : bucket) {
a[k++] = x;
}
}
}

两点要注意。第一，x * n在x非常接近 1 时可能因舍入得到n，必须把下标夹到n - 1，否则越界写是未定义行为。第二，static_cast<std::size_t>对负数是未定义的转换结果，所以函数要求输入非负；如果值域含负数，应当先做平移，或者用下面整数版本里的按min归一化。

桶数取n是一种常见选择：元素均匀时每桶期望一个元素，桶内排序几乎无开销；但桶的容器本身有开销，n很大时内存占用也线性增长。

四、整数版本：按值域归一化

整数输入的值域可能很宽，也可能含负数。做法是先求min与max，把每个值映射到[0, k)：

// 适用于 C++17
#include <algorithm>
#include <cstddef>
#include <vector>

void bucket_sort_int(std::vector<int>& a) {
if (a.size() < 2) return;

auto minmax = std::minmax_element(a.begin(), a.end());
const long long lo = *minmax.first;
const long long hi = *minmax.second;
const long long range = hi - lo + 1; // 用 long long 防溢出

const std::size_t n = a.size();
std::size_t k = std::min<std::size_t>(
n, static_cast<std::size_t>(range)); // 桶数不超过值域
if (k == 0) k = 1;

std::vector<std::vector<int>> buckets(k);
for (int x : a) {
long long offset = static_cast<long long>(x) - lo;
std::size_t idx = static_cast<std::size_t>(
offset * static_cast<long long>(k) / range);
if (idx >= k) idx = k - 1; // 理论上不会发生，防御
buckets[idx].push_back(x);
}

std::size_t pos = 0;
for (auto& bucket : buckets) {
std::sort(bucket.begin(), bucket.end());
for (int x : bucket) {
a[pos++] = x;
}
}
}

几个细节：

• 
  
• range用long long：hi - lo在int上可能溢出（例如hi = INT_MAX、lo = INT_MIN）。
• 
  
• 桶数取min(n, range)：值域比元素还小时，桶数没必要超过值域，否则大量空桶白白占用内存。
• 
  
• offset * k也可能溢出long long？offset < range ≤ 2^32，k ≤ n，若n达到 2^31，乘积接近 2^63，处在边界上。工程上元素个数远小于这个量级；严谨写法可以用long double或先除后乘，但会引入精度问题。知道这个上界即可。
• 
  
• range == 1（所有元素相等）时k = 1，所有元素进一个桶，排序后原样写回，结果正确。
• 
  

五、怎么选桶数

桶数没有标准答案，取决于数据分布与内存预算：

实践中可以先采样估计分布，或者干脆用std::sort——它在最坏情况下是 O(n log n)，且常数经过充分优化。桶排序的优势场景很明确：值域已知、分布均匀、数据量大，例如把大量[0,1)的评分、概率、归一化后的特征排序。

常见坑点

1. 桶数取 1

// ❌ 等价于对整个数组做一次排序，白折腾
std::vector<std::vector<double>> buckets(1);
// ✅ 桶数与数据量匹配
std::vector<std::vector<double>> buckets(a.size());

2. 浮点映射越界

// ❌ x 接近 1 时 idx 可能等于 n
std::size_t idx = static_cast<std::size_t>(x * n);
// ✅ 夹到最后一个桶
if (idx >= n) idx = n - 1;

3. 对负数直接做size_t转换

// ❌ 负数转无符号是回绕的大数，越界
std::size_t idx = static_cast<std::size_t>(x * n);
// ✅ 先按 min 归一化到非负
long long offset = static_cast<long long>(x) - lo;

4. 值域差用int计算

// ❌ INT_MAX - INT_MIN 溢出，属于有符号溢出
int range = hi - lo + 1;
// ✅ 用更宽的整数类型
long long range = static_cast<long long>(hi) - lo + 1;

5. 桶内用std::sort却声称稳定

// ❌ std::sort 不保证稳定
std::sort(bucket.begin(), bucket.end());
// ✅ 需要稳定语义时用 stable_sort
std::stable_sort(bucket.begin(), bucket.end());

6. 合并时按桶内元素个数而不是桶顺序

// ❌ 打乱桶间的大小关系，结果无序
for (auto& b : buckets) for (auto x : b) out.push_back(x);
// 若 buckets 被重新排序过，就会出错
// ✅ 桶的顺序必须与值域区间一致

7. 认为桶排序一定比std::sort快

// ❌ 分布不均时桶内元素集中，反而更慢
// ✅ 先确认分布，或做基准测试

8. 输入值超出约定范围却不检查

// ❌ 约定 [0,1)，实际传入 2.5，下标越界
bucket_sort_unit(data);
// ✅ 校验前置条件，或改用按 min/max 归一化的版本

总结

桶排序的价值在于把一次全局排序拆成若干次小规模排序，用空间换时间。它的性能高度依赖分布假设，所以使用前要问清楚：数据是否均匀、值域是否已知、内存是否允许额外的桶容器。三个条件都满足时它很有效；有一个不满足，std::sort往往是更稳的选择。