前言
桶排序的基础版本很好理解：把元素按值域分到若干桶里，桶内排序，再按桶顺序拼起来。但在「大数据」语境下，数据量往往超过内存，基础版本里那个vector<vector<T>>根本放不下。这时桶排序的角色会发生变化——它不再是一段排序函数，而是一种分治式的数据处理流程：先按关键字把数据分散到多个可独立处理的分区，再对每个分区在内存中排序，最后做多路归并。
常见的误解有三个。第一，以为桶排序的 O(n) 是无条件的，忽略了「数据均匀分布」这个前提；数据倾斜时，某个桶可能仍然大到放不进内存。第二，以为分桶只是排序的前置步骤，没意识到分桶本身要读写磁盘，I/O 成本可能远高于比较成本。第三，以为桶数越多越好，忽略了文件句柄、随机写和打开文件数量的限制。
本文侧重工程处理：如何判断能不能用桶、如何做外部分桶、桶内放不下时怎么办、如何归并。基础桶排序的原地实现另有专文，这里不重复。所有代码都是按标准语义写出的示例，没有经过编译或运行。
一、什么时候桶排序才值得用
先看三个条件。第一，关键字能映射到一个有序的值域，或者至少能定义一个稳定的分区函数；第二，数据在分区上大致均匀，否则需要额外的倾斜处理；第三，每个分区处理完能落在内存预算内。
分区函数有两种常见选择。范围分区按关键字的数值区间切分，例如 Age 落在 [0,10)、[10,20) 等，好处是分区之间天然有序，归并时只需按分区顺序拼接；缺点是数据倾斜时某个区间可能爆掉。哈希分区按hash(key) % n切分，好处是分布更均匀，缺点是分区之间无序，最后必须做多路归并。
| 分区方式 | 分区内有序 | 分布均匀性 | 代价 |
|---|
| 范围分区 | 是，可按序拼接 | 依赖数据分布 | 倾斜时需要再切分 |
| 哈希分区 | 否，必须归并 | 通常较好 | 多一次归并 |
实际系统里常见的做法是「范围分区 + 倾斜检测」：先采样估算分位数，按分位数切分，而不是等宽切分。采样只需要读少量数据，能显著降低某个桶过大的概率，但无法完全消除。
二、第一遍：把数据分散到分区文件
下面是一个简化的外部分桶示例。记录是定长的二进制结构，按关键字的高位分到bucket_count个文件。桶数取 2 的幂，这样可以用位运算代替取模。
// 适用于 C++17
#include <cstdint>
#include <filesystem>
#include <fstream>
#include <stdexcept>
#include <string>
#include <vector>
struct Record {
std::uint64_t key;
std::uint32_t payload;
};
// bits 满足 bucket_count == (1u << bits)
void partition_file(const std::string& input, const std::string& dir,
unsigned bits) {
const unsigned bucket_count = 1u << bits;
std::filesystem::create_directories(dir);
std::vector<std::ofstream> outs;
outs.reserve(bucket_count);
for (unsigned i = 0; i < bucket_count; ++i) {
const std::string path =
dir + "/part-" + std::to_string(i) + ".bin";
outs.emplace_back(path, std::ios::binary | std::ios::trunc);
if (!outs.back()) throw std::runtime_error("cannot open bucket file");
}
std::ifstream in(input, std::ios::binary);
if (!in) throw std::runtime_error("cannot open input");
Record r{};
while (in.read(reinterpret_cast<char*>(&r), sizeof r)) {
const unsigned idx = static_cast<unsigned>(
(r.key >> (64 - bits)) & (bucket_count - 1u));
outs[idx].write(reinterpret_cast<const char*>(&r), sizeof r);
}
}几个工程要点。缓冲区：每个ofstream自带缓冲，但桶数很多时仍会频繁触发系统调用；可以给每个桶配一个内存缓冲，攒够一批再写。文件句柄：同时打开几千个文件可能超过系统限制，桶数应当按「预期数据量 / 单桶内存预算」估算，而不是盲目取大。二进制格式：reinterpret_cast直接写结构体只适合同机临时文件，结构体有填充、字节序依赖平台；一旦要跨机器或长期存储，必须定义明确的字段编码。
写完后要统计每个桶的记录数。如果某个桶明显超过预算，有两个选择：对该桶按次高若干位再分一层，或者对桶内数据做哈希再分。递归深度要设上限，否则极端倾斜会让分区过程本身变成瓶颈。
三、第二遍：桶内排序与多路归并
每个桶能放进内存时，直接读进std::vector，用std::sort排序，再写回。std::sort的平均复杂度是 O(m log m)，m 是桶大小；所有桶加起来是 Σ mᵢ log mᵢ，均匀分布时接近 n log(n/k)，比整体排序少一些比较，但真正的收益主要来自「每个桶可以独立处理」——可以并行，也可以分批。
如果采用范围分区且分区之间有序，排完直接按编号顺序拼接即可，不需要归并。如果采用哈希分区，或者桶内又做了二次分桶，就需要 k 路归并。归并时用一个最小堆维护每个输入文件的当前记录：
// 适用于 C++17
#include <cstddef>
#include <cstdint>
#include <fstream>
#include <queue>
#include <string>
#include <vector>
struct Head {
Record rec;
std::size_t src = 0;
};
struct Cmp {
bool operator()(const Head& a, const Head& b) const {
return a.rec.key > b.rec.key; // 最小堆：键小的优先
}
};
void merge_files(const std::vector<std::string>& inputs,
const std::string& output) {
std::vector<std::ifstream> ins;
ins.reserve(inputs.size());
for (const std::string& path : inputs)
ins.emplace_back(path, std::ios::binary);
std::priority_queue<Head, std::vector<Head>, Cmp> heap;
for (std::size_t i = 0; i < ins.size(); ++i) {
Head h;
h.src = i;
if (ins[i].read(reinterpret_cast<char*>(&h.rec), sizeof(Record)))
heap.push(h);
}
std::ofstream out(output, std::ios::binary | std::ios::trunc);
while (!heap.empty()) {
Head h = heap.top();
heap.pop();
out.write(reinterpret_cast<const char*>(&h.rec), sizeof(Record));
if (ins[h.src].read(reinterpret_cast<char*>(&h.rec), sizeof(Record)))
heap.push(h);
}
}std::priority_queue默认是大顶堆，比较器返回a.key > b.key时堆顶才是最小键。每次弹出一个记录、写一个记录、再从同一文件补一个，堆的大小始终等于文件数，内存占用与总数据量无关。归并的 I/O 是顺序读写，但多个输入文件交替读取，实际表现受页缓存和磁盘调度影响，文件数不宜过多。
四、倾斜、失败与资源边界
大数据场景里，最需要提前设计的是「不正常情况」：
| 情况 | 表现 | 处理 |
|---|
| 单桶过大 | 读进内存时 OOM | 按次高位再分，或桶内哈希二次分桶 |
| 分区数过多 | 打开文件失败 | 按内存预算反推桶数，分批处理 |
| 数据倾斜 | 个别桶远大于均值 | 采样分位数切分，而非等宽 |
| 磁盘不足 | 写分区失败 | 先估算总大小，预留临时空间 |
| 过程中断 | 临时文件残留 | 用独立目录，启动时清理，写成功后再提交 |
还有一个常被忽略的点：桶排序的「线性」只描述比较次数，不描述 I/O 次数。外部分桶至少要把数据完整读一遍、写一遍，归并再读一遍、写一遍；当数据量很大时，这些顺序 I/O 才是主要成本。压缩、批量写、减少中间落盘次数，往往比优化桶内排序更有效。
常见坑点
- ❌ 不分情况直接开
vector<vector<int>> buckets(n)，数据一大就 OOM。
✅ 先估算内存，超过预算就落盘分桶。
- ❌ 桶数取 1000，同时打开 1000 个文件，超过句柄上限。
✅ 按系统限制和单桶预算确定桶数，必要时分批处理。
- ❌ 等宽范围分区，遇到长尾数据导致单桶爆炸。
✅ 采样后按分位数切分，并给单桶大小设阈值触发二次分桶。
- ❌ 认为桶排序一定 O(n)，忽略倾斜与 I/O。
✅ 把分桶、桶内排序、归并的成本分别计入。
- ❌ 直接把结构体二进制写出，跨平台读取时字段错位。
✅ 临时文件可接受；跨平台时定义明确的序列化格式。
- ❌ 哈希分区后按桶编号直接拼接，结果无序。
✅ 哈希分区必须做 k 路归并；只有范围分区才能顺序拼接。
- ❌ 归并时把所有输入一次性读进内存。
✅ 每个文件只保留当前记录，用堆做多路归并。
- ❌ 任务失败后残留分区文件，下次运行读到旧数据。
✅ 每次运行使用独立临时目录，成功后原子替换输出。
总结
| 阶段 | 关键决策 | 主要成本 |
|---|
| 分区 | 范围还是哈希、桶数多少 | 一次全量读写 |
| 桶内 | 能否放进内存、是否需要二次分桶 | 比较与内存 |
| 归并 | 是否需要、文件数多少 | 多路顺序 I/O |
| 异常 | 倾斜、句柄、磁盘、残留 | 额外分片与清理 |
大数据下的桶排序，本质是「用一次可控的分散，把大问题拆成一批能独立解决的小问题」。它的线性时间只在分布均匀、I/O 可控时成立；真正决定成败的，是分区的均匀性、单桶的内存预算和失败后的清理策略。
