如果让我在九大排序算法里选一个最容易被低估的家伙，我大概率会投桶排序一票。冒泡排序、快速排序这些名字一听就知道靠的是交换和分治，可桶排序（Bucket Sort）听起来像把数据往桶里一扔就完事，实际上它恰恰是最需要理解数据分布的那个排序算法，也是九大排序算法里少有的能把平均时间复杂度压到O(n)的非比较排序思路。这篇文章从原理讲到C语言实现，再延伸到负数、浮点数、数据分布不均等边界情况，最后聊聊它在海量数据里的工程用法，适合正在复习数据结构排序算法、准备面试题，或者想给特定类型数据提速的同学参考。文里所有代码我都实际跑过，你可以直接复制到本地验证。
1. 桶排序的核心思想：先分桶，再排序
1.1 从快递分拣理解桶排序原理
如果你去快递分拣中心看过，会发现他们从不把所有包裹集中在一个大池子里统一排序。先按省份扔到不同格口，到了下一级再按城市分拣，最后才到派送员手里。这个过程本质上就是桶排序：先根据某个规则把数据分类成多个类别，每个类别是一个“桶”，等数据都进了各自区域后，再在桶内做更细的整理，最后把各个格口按顺序串起来，整体就有序了。
桶排序也是同样的三步：第一步确定桶的数量和每个桶对应的范围；第二步按映射函数把待排序元素分到对应桶里；第三步每个桶内做排序，再按桶的顺序依次把元素取回，此时数组已经全局有序。它和快速排序、归并排序最大的不同在于：把原本需要跨全局反复比较的问题，拆成了“一次归类 + 若干个局部小排序”，用归类动作换取比较次数的大幅下降。
1.2 桶排序到底解决了什么问题
九大排序算法里，快速排序、归并排序、堆排序都是基于比较的排序，理论下界是O(n log n)。也就是说当数据量翻倍，比较次数不会跟着线性增长，而是以略高于线性的速度膨胀。桶排序换了个思路：先不做比较，用哈希式的映射把元素分到桶里，桶内再做比较。当数据集满足某些分布特征时，它就能绕过比较排序的下界，跑出线性的平均表现。
桶排序特别适合处理“范围已知、分布相对均匀、数据量大”的场景，比如学生成绩统计、用户年龄分布、传感器采集值等。这些问题如果硬用快速排序当然也能排，但桶排序的优势在于：局部有序之后你往往只需要处理局部信息就够了，比如查Top K、统计区间频率，根本没必要把整个序列排整齐。这也是它在工程里经常被低估的原因——大家只顾着让它“排序”，却忘了它最擅长的是“分桶”。
1.3 时间复杂度为什么能接近O(n)
把复杂度算清楚，面试时就不会答错。设有n个数据，分成m个桶，理想状态下数据均匀分布在每个桶里，每个桶大概有k=n/m个元素。桶内如果用一个O(k log k)的排序，总时间就是 m × (n/m) log(n/m)，约等于 n log(n/m)。当m取到接近n的数量级时，n log(n/m)就会趋近于O(n)。这就是桶排序能跑得飞快的原因。
最坏情况呢？如果所有数据都被映射到同一个桶里，桶排序就退化成那一桶内排序。假设桶内用了插入排序，复杂度就是O(n²)。空间复杂度方面，需要额外存储所有桶，常见实现下是O(n + m)。所以桶排序不是无条件O(n)，它的前提是数据能均匀进桶。这一点决定它和计数排序、基数排序一样，属于“吃数据分布红利”的排序算法。
2. 写桶排序前先想清楚：桶数、映射函数、桶内排序
2.1 桶的数量怎么定才合适
第一个要决策的问题是m到底取多少。如果只凭感觉取10个桶，数据范围很大的时候桶里会塞满，效率一下就崩了；如果桶取到上千个，每个桶又可能只有一个元素，排序很快但内存开销膨胀。工程上常用三种经验策略：一是取 sqrt(n)，对n=10000的数据就是100个桶，每个桶平均100个元素，桶内排序成本可控；二是按数据范围除以期望桶容量来定，比如想让每个桶不超过50个元素，就取 (max-min)/50 + 1；三是两手抓，先抽样算一下数据的实际范围，再结合内存上限定桶数。
至于“目标桶容量”，要看桶内排序的开销。如果用插入排序，单个桶里几十个元素时非常快，几百个也能接受；如果桶内想用快速排序，桶数可以少一点，因为快排本身能消化较大的局部规模。实际项目里我通常会先抽样1000个点，估算min/max和大致分布，再决定桶数量，很少拍脑袋直接定。
2.2 映射函数：正确只是及格线，均匀才是关键
映射函数决定每个元素进哪个桶，这是桶排序里最容易踩坑的地方。经典写法是把数据线性归一化到[0,1)区间，再乘上桶数。以整数数组为例，先找到min和max，然后这样算桶号：
int idx = (int)((double)(a[i] - min) / (max - min) * (bucket_count - 1));
这样最小值一定落在0号桶，最大值会落在 bucket_count-1 号桶，不会越界。如果你图省事写成a[i] * bucket_count，一旦数据里有等于1的浮点数，就会算出 bucket_count，直接访问越界，这是新手最常见的崩溃原因之一。
映射函数要求的不仅是“正确”，更是“均匀”。因为桶排序的时间复杂度依赖数据均匀落到各桶，如果原始数据集中在一个很小区间，线性映射会让大量数据挤到同一个桶，效率立刻崩掉。判断映射是否合理，我建议先打印每个桶的元素计数，看一眼分布再继续调，不要等到排序耗时爆炸了才回头查。
2.3 桶内排序怎么选，为什么这么选
桶内排序几乎可以任选，选什么样的算法直接决定桶排序的整体表现和稳定性。量少的时候我首选插入排序：代码简单，对于基本有序的小数组效率高，而且它本身是稳定排序，配合按桶序收集就能让整个桶排序保持稳定。它有一个缺点是最坏情况O(n²)，但桶内元素少，这个理论弱点在实践中往往体现不出来。
如果数据量大、单个桶里几百甚至上千个元素，插入排序会出现明显变慢，这时候换成快速排序更合适，代价是稳定性没了。还有一个更“懒”的写法：桶内不排序，只把桶当作一个区间，桶内递归调用桶排序，这就是递归分治的思路。不过为了讲清楚九大排序算法之间的区别，我建议代码里明确注明桶内排序用的是什么，面试官非常喜欢追问这个点。
3. C语言实现：从插入排序到完整桶排序
3.1 先准备一个可靠的插入排序作为桶内排序
桶排序主函数里有大量模板代码，真正需要动脑子的其实是映射和收集。桶内排序如果临时去写快速排序，代码会变得很长，所以我习惯先准备一个干净的插入排序。对于整数数组，这样写就够用：
void insertion_sort(int a[], int n) { for (int i = 1; i < n; i++) { int key = a[i]; int j = i - 1; while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; } }这段代码在数组几乎有序时接近O(n)，最坏是O(n²)。用在桶排序里时，由于每个桶里的元素数量都远小于n，整体时间一般都能压得住。如果你要在C语言里面对更复杂的结构体数组按某个字段排序，只需要把循环里的比较改成a[j].key > key.key即可。这段代码我用了很多年，基本没有改过。
3.2 桶排序主流程的完整代码
完整实现我按“找范围-建桶-入桶-桶内排序-收集-释放”六步来写。下面这个版本采用最直观的“每个桶都预留n个位置”的做法，先保证逻辑正确好理解，下一节再解决内存浪费问题。
void bucket_sort(int a[], int n, int bucket_count) { if (n <= 1) return; int min = a[0], max = a[0]; for (int i = 1; i < n; i++) { if (a[i] < min) min = a[i]; if (a[i] > max) max = a[i]; } if (max == min) return; int **buckets = (int **)malloc(bucket_count * sizeof(int *)); int *sizes = (int *)calloc(bucket_count, sizeof(int)); for (int i = 0; i < bucket_count; i++) { buckets[i] = (int *)malloc(n * sizeof(int)); } for (int i = 0; i < n; i++) { long long diff = (long long)a[i] - min; int idx = (int)(diff * (bucket_count - 1) / (max - min)); buckets[idx][sizes[idx]++] = a[i]; } for (int i = 0; i < bucket_count; i++) { insertion_sort(buckets[i], sizes[i]); } int pos = 0; for (int i = 0; i < bucket_count; i++) { for (int j = 0; j < sizes[i]; j++) { a[pos++] = buckets[i][j]; } } for (int i = 0; i < bucket_count; i++) free(buckets[i]); free(buckets); free(sizes); }注意idx的计算：先用diff乘以 bucket_count-1，再除以 max-min，相当于计算该元素在整个范围里的比例位置。强制转换成int时会把小数部分截断，所以最小值进0号桶，最大值进最后一个桶，不会越界。这里我把diff声明成long long，是为了防止数据范围很大时(a[i]-min) * (bucket_count-1)在int乘法中溢出，这个细节能帮你省去很多莫名其妙的问题。
3.3 测试程序与结果验证
写完主流程，必须用一个能验证正确答案的测试程序跑起来。下面这个例子里的数据覆盖了普通整数、重复值和边界值：
#include <stdio.h> #include <stdlib.h> int main(void) { int arr[] = {78, 17, 39, 26, 72, 94, 21, 12, 23, 68, 5, 88, 5, 100}; int n = sizeof(arr) / sizeof(arr[0]); printf("排序前: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); bucket_sort(arr, n, 4); printf("排序后: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); return 0; }这里我故意把桶数设成4，让每个桶里多放几个元素，验证桶内插入排序确实在干活。跑出来的排序前是78 17 39 26 72 94 21 12 23 68 5 88 5 100，排序后是5 5 12 17 21 23 26 39 68 72 78 88 94 100。建议你再生成几个随机数组，拿系统自带的qsort结果做对照，能顺手发现映射越界之类的问题。我当时第一次跑桶排序时，就是靠这种对照测试找到了一个边界值导致的越界bug。
3.4 更省内存的两趟扫描版本
上面每个桶都开了n个int，m个桶就是m×n个int，数据量大时内存非常恐怖。一个工程上常用的优化是两趟扫描：第一趟只统计每个桶最终会有多少个元素，第二趟再给每个桶精确分配空间。这种“先计数、再分配”的思路，其实就是计数排序和桶排序的交叉应用。
void bucket_sort_opt(int a[], int n, int bucket_count) { int min = a[0], max = a[0]; for (int i = 1; i < n; i++) { if (a[i] < min) min = a[i]; if (a[i] > max) max = a[i]; } if (max == min) return; int *count = (int *)calloc(bucket_count, sizeof(int)); for (int i = 0; i < n; i++) { long long diff = (long long)a[i] - min; int idx = (int)(diff * (bucket_count - 1) / (max - min)); count[idx]++; } int **buckets = (int **)malloc(bucket_count * sizeof(int *)); int *cursor = (int *)malloc(bucket_count * sizeof(int)); for (int i = 0; i < bucket_count; i++) { buckets[i] = (int *)malloc(count[i] * sizeof(int)); cursor[i] = 0; } for (int i = 0; i < n; i++) { long long diff = (long long)a[i] - min; int idx = (int)(diff * (bucket_count - 1) / (max - min)); buckets[idx][cursor[idx]++] = a[i]; } for (int i = 0; i < bucket_count; i++) { insertion_sort(buckets[i], cursor[i]); } int pos = 0; for (int i = 0; i < bucket_count; i++) { for (int j = 0; j < cursor[i]; j++) { a[pos++] = buckets[i][j]; } } for (int i = 0; i < bucket_count; i++) free(buckets[i]); free(buckets); free(cursor); free(count); }这个版本的桶数量如果取到n的量级，内存是O(n)，时间稳定在O(n log(n/m))。实际项目中我基本直接用这个优化版当模板，很少用上一节的简单版。它多写的几行代码不多，但能把内存占用从m×n降到n，在大数据量下是质的差别。
4. 边界场景：负数、浮点数、分布不均匀
4.1 负数和浮点数怎么归一化
上面代码对于正整数是安全的，但数据里一旦有负数，直接用a[i] * bucket_count这种映射就全乱了。我处理负数的方式很简单：不管数据范围落在哪里，都先做归一化。先用min把整个范围平移到0开始，再按比例映射，负数就退化成普通的线性映射问题，代码完全不用为负数专门写分支。
浮点数方面的坑是精度。如果max和min非常接近，分母max - min可能因为浮点误差变成0，或者idx算出来溢出。我会在代码里对max - min < 1e-12的情况直接返回，表示这些数已经基本相等，不需要排序。处理浮点数据时，建议把映射写成(int)((double)(a[i] - min) / (max - min) * (bucket_count - 1))，并且对等于max的元素做一次clamp，确保它不会跑出最后一个桶的边界。
4.2 数据分布严重不均时如何避免退化
最典型的数据分布失衡例子是考试成绩：全班大部分学生挤在85到95这个分段，如果用线性映射按0到100分分成10个桶，七八成数据会集中到同一个桶里，其他桶几乎空着。这时候桶排序近似退化成O(n²)，比快速排序还慢。遇到这种数据，我会先做一次简单的直方图统计，如果发现数据扎堆，就改用两种方案之一：一种是自适应分桶，在数据密集区间细分更多桶，稀疏区间用大桶；另一种是干脆换计数排序或基数排序，它们在范围小但数据量大时是更合适的线性排序算法。
我判断一个数据集合适不适合用桶排序，标准里有一条硬指标：数据范围已知，且抽样后分布还算均匀。如果分布未知，我不会贸然用桶排，宁可用快速排序保底。这个习惯帮我在线上避免了好几次性能事故，因为桶排序的“快”是建立在数据配合的前提上的，数据不配合，它比很多基础排序都慢。
4.3 稳定性到底怎么判断
面试里经常问桶排序是不是稳定排序。我的答案始终是：取决于实现。桶排序的“桶间顺序”天然稳定，因为收集时按桶号从0到bucket_count-1顺序取，先进入某个桶的元素也一定先被取出来。但“桶内顺序”取决于桶内排序算法：如果桶内用了插入排序，整体就是稳定的；如果桶内用了快速排序或者堆排序，整体就变成不稳定的。一句话记忆法：稳定桶排序 = 稳定的桶内排序 + 按序收集。
这一点在工程上很重要。假设你要对一组结构体先按班级分桶，再按学号排序，如果桶内用了不稳定排序，最后得到的班级顺序虽然对，但同班级内的学号顺序可能和原数据不一致，导致整体有序性被破坏。需要稳定排序时，我习惯在桶内用插入排序或者归并排序，虽然慢一点，但至少语义是对的。
5. 工程实战：桶排序在海量数据中的三个典型用法
5.1 海量数据Top K，快速定位目标区间
我处理过一批线上日志，数量在一亿条左右，要按接口耗时找出最慢的100条。最直接的办法是全量快排再取前100，但浪费了大量算力。我的做法是先分桶：把耗时按区间分到几百个桶里，先统计每个桶的元素数量，从耗时最大的桶往前累加计数，一上升到100就锁定目标区间，然后只对这一两个桶做精细排序。这样需要完整排序的数据量从一亿条骤降到几千条，速度提升非常明显。
这个思路在线上很常见：先分桶确定“最值落在哪个区间”，再对局部排序。它本质上是在利用桶排序“部分有序”的特性，而不是要求整个数组都排好。每次有人问我桶排序工程上有啥用，我第一个例子永远是Top K，因为它最能体现“桶”作为一个中间态的价值。
5.2 近似分位数统计：不排序也能算P99
海量日志响应时间的P99（百分之九十九分位数）怎么算？很多人第一反应是排序后取第99%个元素，但在每秒上千万条数据的流式场景下，全量排序根本跑不动。借助桶排序的思路，可以把所有耗时按区间分桶，统计各桶计数，然后从低区间往高区间累加，跨过数据总量的某个百分比时，就找到了近似分位数所在的桶。如果还想更精确，再对该桶内部排序取对应位置。
这种“不排序也能算分位数”的办法，在监控系统和实时告警里是标准操作。桶排序里的“桶”在这里更像一个直方图，牺牲一点精度，换回O(n)的统计能力。很多同学学桶排序只记得排序本身，没意识到它最值钱的是分桶直方图这个副产品，这其实才是桶排序在工业界最常见的实际应用形态。
5.3 外部排序与分布式排序里的分桶思想
当单机内存放不下整个数据集时，桶排序的思路也能自然迁移。外部排序里有一种经典流程：把大文件按范围映射成多个小文件，每个小文件读入内存单独排序，最后多路归并。这不就是桶排序的磁盘版本吗？分布式框架的shuffle阶段同样如此：Map阶段按key分区，相当于分桶；Reduce阶段把每个分区的数据做局部合并排序。理解了桶排序，再看这些系统的设计会很有亲切感。
当然不能把桶排序直接等同于外部排序或分布式排序，但它的“分而治之”思想确实是那些复杂系统的一块地基。我自己在读书笔记里写过一句话：桶排序教给我们的不是排序本身，而是用空间换时间、用分布换效率的思路。当你真正理解了分桶，会发现很多大数据组件里的排序设计都能一眼看穿。
6. 常见问题与排查技巧实录
6.1 排序结果不对，先查映射函数
桶排序结果不对，九成是映射函数出问题。最常见的是idx越界：数据里有等于max的元素，但公式算出来刚好等于bucket_count，数组越界后程序要么崩溃要么乱写内存。排查方法是打印每个元素对应的桶号，再确认桶号范围确实在[0, bucket_count-1]之内。其次是收集顺序没按桶号走，有人为了省事把桶存在哈希表里，取数据时顺序全乱了。记住：桶排序的收集必须严格按桶序号递增来，这是它能够全局有序的最后一个环节。
如果是自己写的映射公式，建议先用一组已知数据人工算一遍入桶编号，然后再跑大数据。我在调试阶段通常会临时加一行打印，把每个元素的原始值、min、max、idx都打出来，和手算结果对比定位。这个小习惯看起来笨，但比盯着内存发呆有效得多。
6.2 内存占用异常大，检查桶容量分配
很多第一次写桶排序的人，图省事给每个桶分配了n个空间，相当于m个桶共占m×n个int，数据量一大直接溢出。排查时先看总内存估值：如果n=100万，m=100，每个桶分配100万个int，那就是100×100万×4字节，约400MB，很难撑得住。解决办法就是我第3章写的两趟扫描法，先统计再分配，内存从m×n降到O(n)。如果连两个数组都不想多开，还可以用链表做桶，入桶时动态申请节点。
另外要留意编译器优化的坑：int乘法溢出。数据范围很大时，(a[i]-min)*(bucket_count-1)完全可能超过int上限，我用long long先转换再运算，基本从这个坑里解放了。平时测数据小看不出来，一旦上线跑真实数据就会暴露，所以代码里提前防御是值得的。
6.3 数据全挤进同一个桶，速度骤降
当你发现桶排序跑起来和O(n²)没区别，先别急着怀疑程序，大概率是数据分布出了问题。打印每个桶的容量统计看一眼，如果某个桶的容量超过总数据量的80%，说明映射函数不适合当前数据。临时手段是把桶分得更细，或者改成二次映射，把数据密集区间放大；彻底手段是换计数排序、基数排序，或者干脆退回快速排序。真实业务里我一般先用采样估计分布，再决定要不要上桶排序，很少写完才发现崩了。
换个角度看，这个“崩了”的现象也能当检测工具用：如果某个桶容量超大，说明数据在某个区间内集中分布，这种数据往往意味着业务上有些值得关注的特征，比如接口耗时大多集中在200毫秒附近。桶排序有时候不只是排序工具，还能帮你发现数据分布的秘密。
6.4 面试高频题速查表
把桶排序相关的考试高频问题整理成一张表，方便你复习：
| 考查点 | 建议答案 |
|---|---|
| 时间复杂度 | 平均O(n log(n/m))，桶数m接近n时为O(n)；最坏退化为O(n²) |
| 空间复杂度 | 额外O(n+m) |
| 稳定性 | 取决于桶内排序，桶内稳定则整体稳定 |
| 适用场景 | 数据范围已知、分布均匀、数据量大 |
| 核心操作 | 确定桶数、映射入桶、桶内排序、按序收集 |
| 与计数排序关系 | 计数排序是桶数等于值域范围的特例 |
| 与基数排序关系 | 基数排序可以看成按位分桶的多次桶排序 |
面试官如果追问“数据分布极不均匀怎么办”，你可以从自适应分桶、增加桶数、改用其他线性排序三个角度回答，基本上就能过关。再补充一点：如果问桶排序和快速排序谁更适合作为默认排序，我会选快速排序，因为桶排序对数据分布有额外要求，快速排序则几乎无假设。只有确认数据分布符合预期时，桶排序的优势才能彻底发挥出来。
最后分享一个我自己的习惯：在处理任何需要排序的数据之前，我都会先打印一份直方图看看分布。有时候代码根本不用写完整的桶排序，光靠分桶统计就能解决问题，而桶排序正是教给我这个思路的老师。排序归根结底是手段，洞察数据分布才是目的，希望这篇关于九大排序算法之一桶排序的文章，能让你在实际编码里少走几步弯路。
