终于有人问到点子上了。面试官抛出“100万条成绩分数0~100要求稳定排序不能用快排”这种题的时候大多数人脑子里只有归并排序实际上这里最快的答案是另一套思路非比较排序。计数排序、桶排序、基数排序这三个家伙不靠元素之间两两比较来决定先后而是直接利用数据的取值范围、分布特征和数字位权把时间复杂度拉到 O(n) 这个量级。这篇文章就从原理讲起给出可以直接抄的C语言实现再聊聊选型、边界条件和我在真实工程里踩过的坑适合数据结构课程还没吃透的学生也适合面试前临时抱佛脚或者被海量数据排序搞到头大的开发者。1. 先搞懂为什么非比较排序能打破 O(n log n) 的“天花板”1.1 比较排序的硬地板两次比较只能解决“二选一”先聊一个很多人忽略的底层事实凡是基于“两两比较”的排序算法比如快排、归并、堆排最坏情况下都不可能低于 O(n log n)。道理不复杂你可以把排序想象成一次“猜谜”n个元素一共有 n! 种排列顺序排序就是要从这么多可能性里锁定正确的那一个。而一次比较比如“a 和 b 谁大”结果只有两种a在前或者b在前相当于只帮你排除了大约一半的可能性也就是只提供了 log2(2)1 比特的信息。所以无论算法写得多精巧最坏也要做大约 log2(n!) 次比较而 n! 用斯特林公式展开之后就是 n log n 这个量级。这就是为什么快排、归并、堆排再优化大 O 复杂度都卡在 O(n log n)。很多人不知道的是这个“天花板”只对比较排序成立。如果允许我们绕过比较直接利用数据本身的结构就有机会把它击穿。计数排序、桶排序、基数排序本质上都在干这件事不走“两两比较”的老路而是先观察数据长什么样再选择一条更短的路。1.2 三兄弟的定位不是替代比较排序而是“看菜下饭”这三兄弟经常被放在一起讲但它们的思路其实差得很远计数排序把每个值出现的次数统计出来然后用“前缀和”推算出每个值最终应该放在哪里。适合值域很小的整数序列。桶排序把数据按区间均匀地分到若干“桶”里桶内各自排序最后按顺序倒出来。适合数据分布比较均匀的浮点数或大范围整数。基数排序把数字按位拆开从低位到高位逐位做稳定排序。适合位数固定或可以拆成多关键字的整数、手机号、日期字符串。一句话概括计数排序关注“值域”桶排序关注“分布”基数排序关注“位数”。它们的共同点是都依赖额外的辅助空间用空间换时间而且只要实现正确都是稳定排序。这里说的稳定是指相同值的元素排序后仍然保持原来的相对顺序这个性质在基数排序里尤其重要后面你会看到。排序算法核心思路平均时间复杂度空间复杂度稳定性典型场景计数排序值域打表 前缀和定位O(n k)O(k)稳定成绩、年龄、状态码等小范围整数桶排序按区间分桶桶内排序O(n k)平均O(n k)稳定取决于桶内排序均匀分布的浮点数、大数据量分片基数排序按位多次稳定排序O(d × (n k))O(n k)稳定手机号、定长字符串、多关键字排序表里的 k 是值域范围或基数大小d 是数字的最大位数。从复杂度上看它们都有机会做到 O(n)但前提是 k 或 d 不能太大。这也是后面所有工程问题的最核心矛盾数据本身的形态决定了你能不能用非比较排序。1.3 一句话判断范围小用计数分布均匀用桶能拆位用基数判断方法其实可以压缩成三个问题数据的取值范围小吗小到可以给每个值都开一个计数格子就用计数排序。数据的分布够不够均匀如果数据在区间里不会扎堆就用桶排序。数据能不能拆成多位比如手机号、学号、日期只要位数可控就用基数排序。需要提醒的是非比较排序并不是银弹。比如给100万个随机分布在 0 到 2^31 之间的整数排序值域大到计数排序直接内存爆炸随机整数又没什么“位”可利用这时候老老实实快排反而更稳。所以在实际项目里我一般会先把数据分布看一遍再决定而不是上来就套算法。后面第五部分会专门给一套选型判题法。2. 计数排序把“大小比较”变成“座位编号”2.1 原理先数人头再按编号入座计数排序的思路非常直白我用一个例子说明。假设一个班级的成绩只有0到5分最终成绩单是 3, 1, 3, 5, 1, 0, 2。第一步统计每个分数出现了几次0分1次1分2次2分1次3分2次4分0次5分1次。第二步做前缀和也就是把每个分数段“累计包含的人数”算出来≤0分的有1人≤1分的有3人≤2分的有4人≤3分的有6人≤4分的有6人≤5分的有7人。这个前缀和数组其实是一张“座位图”最后一个3分应该坐在第6个位置最后一个1分应该坐在第3个位置最后一个0分坐在第1个位置。只要从右往左扫描原数组每看到一个元素就根据前缀和把它放到正确位置上同时把座位号减一就能排好序。整个过程没有比较任何两个元素的大小只是查表、定位、放人。2.2 稳定版计数排序 C 实现可以直接抄的代码下面这份代码是我在工程里常用的稳定版本支持负数因为很多实际数据并不是从0开始。代码关键点都写在注释里。#include stdio.h #include stdlib.h void counting_sort(int *arr, int n) { if (arr NULL || n 1) return; // 1. 先找最小值和最大值确定值域 int min arr[0], max arr[0]; for (int i 1; i n; i) { if (arr[i] min) min arr[i]; if (arr[i] max) max arr[i]; } int range max - min 1; // 值域宽度 int *count (int *)calloc(range, sizeof(int)); int *output (int *)malloc(n * sizeof(int)); if (count NULL || output NULL) { free(count); free(output); return; } // 2. 统计每个值出现的次数用 min 做偏移量 for (int i 0; i n; i) { count[arr[i] - min]; } // 3. 前缀和count[i] 变成“小于等于 mini 的元素个数” for (int i 1; i range; i) { count[i] count[i - 1]; } // 4. 从后往前扫描放入 output保证稳定性 for (int i n - 1; i 0; i--) { int idx arr[i] - min; output[--count[idx]] arr[i]; } // 5. 拷回原数组 for (int i 0; i n; i) { arr[i] output[i]; } free(count); free(output); }代码里第一步找 min 和 max 是为了把任意区间的整数映射到从0开始的数组下标。比如数据范围是 1000 到 2000直接拿 1500 当下标就越界了必须先做 arr[i] - min 的偏移。第三步前缀和是整个算法的灵魂它把“频次表”变成了“位置表”。2.3 为什么回填要倒着走稳定性的关键很多人初学计数排序时会写一个更简单的版本统计完频次后直接按照 count 里的次数把对应数值连续写回数组。比如统计出 1分有2个就往结果里连续写两个1。这样写当然也能排好序但它是不稳定的因为相同值的元素会被随机地放到连续空间里原有相对顺序一旦打乱就找不回来了。而上面这份代码用前缀和加倒序回填就是为了保住稳定性。前缀和告诉我们“某个值的最后一个元素落在哪个位置”那么从后往前扫原数组时遇到相同值的元素总是先把靠后的那个放到更靠后的空位再把前一个放到前一个空位这样它们的相对顺序就保持原样。稳定性这个东西单独用在计数排序上似乎无所谓但你要知道基数排序内部就是要反复调用这种稳定计数一旦这层稳定性丢了整个基数排序就错了。2.4 计数排序的边界和几个坑计数排序最大的局限就是值域。假设有10万个数据但数值范围是 0 到 1亿那你需要开一个1亿长度的计数数组光 int 就要400MB内存直接把自己搞崩。所以在真实场景里我使用计数排序前一定会先算 range如果 range 大于 n 的几十倍就果断换方案。另外几个坑我基本都踩过负数处理没有做 min 偏移就直接用 arr[i] 当下标负数一进来就是数组越界程序稀碎。空数组和单元素数组不提前 return后面找 min/max 直接读 arr[0] 越界。内存分配失败C语言里 calloc、malloc 要判空不能默认为成功。输出数组和 count 数组都用完后忘记 free在小程序里看不出问题在长驻服务里就是内存泄漏。3. 桶排序把连续区间切成“格子”逐格排整齐3.1 桶排序与计数排序的关系桶排序和计数排序其实是一家人。你可以把计数排序理解为“每个值一个桶”的特例值域多大就开多少个桶。桶排序则是把连续区间切成长度相等的若干段每一段一个桶桶里可能装着多个不同但相近的值。这么做的好处是不要求值域小只要求数据在这些桶里分布得比较均匀。举个例子给100万个 [0, 1) 区间的随机浮点数排序。如果计数器需要开的“格子”没法枚举。但如果把它均匀切成 n 个桶第一个桶装 [0, 0.01) 的数第二个桶装 [0.01, 0.02) 的数……因为数据均匀分布平均每个桶只装一个元素装完后再按桶序号把桶内数据倒出来就是有序的。整个过程近似 O(n)非常漂亮。而数据一旦集中到几个桶里桶内如果再用插入排序最坏就退化成 O(n²)这点必须心里有数。3.2 装桶策略桶数、桶宽怎么定桶内用什么排工程里桶数怎么选我一般默认取 n 或 n/2 个桶。桶数太少每个桶里数据太多桶内排序压力大桶数太多空间浪费而且最后遍历空桶的开销也不小。取 n 个桶是一个性价比很高的经验值特备是在均匀分布场景下。桶宽则用公式(max - min 1) / bucket_count计算注意用浮点数免得整数除法导致最后一个桶容量过大。桶内排序的选择取决于每个桶的数据量。当桶内数据量小比如几个、几十个时插入排序反而最快因为它的常数极小如果某个桶的数据量特别大说明数据分布不均匀这时候桶内递归调用桶排序或者改用快排、归并都比硬扛插入排序好。在实际项目中很多实现甚至会在每个桶内直接用快排牺牲一点理论复杂度换取最坏情况的安全性。3.3 C 语言示例代码从分组到回流下面这份 C 代码使用动态扩容的桶数组兼容任意整数序列。我故意把桶内排序写成插入排序因为对这种小数组来说它已经足够快代码也更直观。#include stdio.h #include stdlib.h typedef struct { int *data; int len; int cap; } Bucket; void bucket_sort(int *arr, int n, int bucket_count) { if (arr NULL || n 1) return; int min arr[0], max arr[0]; for (int i 1; i n; i) { if (arr[i] min) min arr[i]; if (arr[i] max) max arr[i]; } if (max min) return; // 所有值相同无需排序 if (bucket_count 0) bucket_count n; Bucket *buckets (Bucket *)calloc(bucket_count, sizeof(Bucket)); if (buckets NULL) return; double bucket_width (double)(max - min 1) / bucket_count; // 装桶 for (int i 0; i n; i) { int idx (int)((arr[i] - min) / bucket_width); if (idx bucket_count) idx bucket_count - 1; // 防止最大值溢出到桶外 if (buckets[idx].len buckets[idx].cap) { buckets[idx].cap buckets[idx].cap 0 ? 4 : buckets[idx].cap * 2; int *tmp (int *)realloc(buckets[idx].data, buckets[idx].cap * sizeof(int)); if (tmp NULL) { /* 实际工程里要做完整释放逻辑这里从简 */ } buckets[idx].data tmp; } buckets[idx].data[buckets[idx].len] arr[i]; } // 桶内插入排序再按顺序回流 int pos 0; for (int i 0; i bucket_count; i) { for (int j 1; j buckets[i].len; j) { int key buckets[i].data[j]; int k j - 1; while (k 0 buckets[i].data[k] key) { buckets[i].data[k 1] buckets[i].data[k]; k--; } buckets[i].data[k 1] key; } for (int j 0; j buckets[i].len; j) { arr[pos] buckets[i].data[j]; } free(buckets[i].data); } free(buckets); }装桶公式最需要注意的是idx (arr[i] - min) / bucket_width可能算出 bucket_count因为 max 正好落在最后一个桶的上边界时除法结果会等于 bucket_count。所以必须在装桶时做一个idx bucket_count的兜底否则数组越界。这是我一开始写桶排序踩得最狠的坑没有之一。3.4 对数据分布的“敏感体质”均匀分布快到飞起扎堆就拉胯桶排序是一个看“数据脸色”的算法。我在本地用100万个 [0, 10000) 的随机整数做过测试分成1000个桶装桶加回流的总耗时跟快排差不多但优势在于桶多时几乎逼近线性。可如果换成100万个集中在 [0, 100) 的数只开1000个桶前几个桶直接塞爆后面的桶全空桶内插入排序一跑复杂度立刻崩到 O(n²) 量级比快排慢了几十倍。所以我想强调用桶排序之前至少要能回答两个问题数据在区间内是不是大致均匀桶数量够不够如果数据存在明显的局部聚集要么增加桶数要么改用其他排序。工程上还有一种更稳的用法就是先把数据分片到多个文件或内存分区再在每片内部用快排这本质上是“分布未知时先用桶做粗排再用比较排序做细排”的妥协方案。4. 基数排序从最低位开始逐位稳定地赢4.1 LSD 与 MSD先排个位还是先排最高位基数排序的核心是“拆位”把一次整体排序拆成多次按位排序。具体有两种方向。LSDLeast Significant Digit从最低位开始依次往高位排比如先按个位排再按十位排再按百位排前提是每一轮都使用稳定排序。MSDMost Significant Digit从最高位开始排排完最高位后各个高位分组内部再递归排序更适合字符串字典序和求 Top K 这种只需要部分结果的场景。这里容易产生的疑问是先按个位排最后怎么就整体有序了我用三位数举个例子。想象你有一堆扑克牌第一轮按个位数放进10个槽里再按顺序收起来虽然此时顺序只保证个位有序但第二轮按十位数稳定排序时十位相同的元素会保持上一轮的个位顺序。第三轮按百位稳定排序后百位大的天然排在后面百位相同的又保持十位顺序所以整体就完全有序了。这就是为什么 LSD 必须依赖稳定排序稳定性在这里不是锦上添花而是轮转数字顺序的粘合剂。4.2 基于计数排序的 LSD 基数排序 C 实现基数排序的每一轮都可以用计数排序实现因为每一轮我们只关心“某一位的数字”它的取值范围固定是0到9。下面的代码是对非负整数数组的经典写法#include stdio.h #include stdlib.h int find_max(int *arr, int n) { int max arr[0]; for (int i 1; i n; i) { if (arr[i] max) max arr[i]; } return max; } void counting_sort_by_digit(int *arr, int n, int exp) { int count[10] {0}; int *output (int *)malloc(n * sizeof(int)); if (output NULL) return; for (int i 0; i n; i) { int digit (arr[i] / exp) % 10; count[digit]; } for (int i 1; i 10; i) { count[i] count[i - 1]; } for (int i n - 1; i 0; i--) { int digit (arr[i] / exp) % 10; output[--count[digit]] arr[i]; } for (int i 0; i n; i) { arr[i] output[i]; } free(output); } void radix_sort(int *arr, int n) { if (arr NULL || n 1) return; int max find_max(arr, n); for (int exp 1; max / exp 0; exp * 10) { counting_sort_by_digit(arr, n, exp); } }exp表示当前处理的位的权重1对应个位10对应十位100对应百位。(arr[i] / exp) % 10就是取出当前位的数字。每一轮都是一次完整的稳定计数排序只是比较的“键”从整个数变成了某一位。这个实现的时间复杂度是 O(d × n)d 是最大值的十进制位数。比如最大数不超过99999就只需要5轮每轮扫描两次数组加一次拷贝整体非常线性。4.3 负数、浮点、字符串常见扩展怎么处理上面的代码只支持非负整数因为 C 语言里负数做除法和取模的结果容易把人绕晕-123 / 10是-12-123 % 10是-3根本没法和 0~9 的位数字直接对接。最简单的变通是先把整个数组加上一个偏移量比如最小值为 -500就把所有数加500排序完再整体减500。不过要注意偏移后可能超过 int 上限稳妥一点可以先把数组换成 long long 再处理。字符串和手机号这类数据基数排序更常用 LSD把它看成多个关键字从最后一个字符往第一个字符做稳定排序。长度不等时可以在末尾补一个特殊结束符把它当成比所有正常字符都小的值。这样“abc”和“abd”这类数据就能正确处理。浮点数也可以排序思路是借用 IEEE 754 的位结构把它转成无符号整数后再基数排序但因为符号位和指数位的处理有点绕工程里我一般直接换桶排序省心。另外提一句十进制并不是唯一选择。基数取10的好处是好理解但实际性能上取256按字节处理通常更快因为每一轮处理的是8位而不是1位十进制轮数会从 10 次左右降到 4 次左右内存访问也更友好。代价是每轮需要一个长度为256的计数数组完全可接受。4.4 三兄弟的复杂度对比与内存权衡排序算法时间最优/平均/最坏空间稳定性主要限制计数排序O(n k) / O(n k) / O(n k)O(k)稳定值域 k 不能太大桶排序O(n) / O(n k) / O(n log n) 或 O(n²)O(n k)取决于桶内排序数据分布需要均匀基数排序O(d × (n k))O(n k)稳定需要能拆位d 不能太大这三个算法的共同点是用空间换时间。稍微有点反直觉的是桶排序最坏情况并不一定都是 O(n²)如果桶内改用快速排序最坏可以控制在 O(n log n)。所以我在项目里更看重桶排序的“可组合性”外层分桶负责均匀切分内层用成熟比较排序保底整体能扛住各种意外数据。5. 实战选型与避坑清单5.1 面试或工程里的“选型判题法”面试时遇到排序题我会快速问自己四个问题全部过完再动手值域大不大分布有没有规律能不能拆位要不要稳定性100万个 0~100 的整数 → 计数排序稳准快。100万个 [0,1) 的均匀浮点数 → 桶排序分布天然均匀。100万个11位手机号 → 基数排序把它当定长字符串处理。100万个 0~2^31 的随机整数 → 老实快排/堆排数据形态不适合非比较排序。100万个重复率极高的整数 → 计数排序很可能最好因为值域取决于不同值的数量而不一定是最大数。工程里也一样。我接手过一个数据导出功能需要把几十万条记录按“状态码 原始序号”排序状态码只有几十种。当时第一版用了归并后来换成计数排序配合原始序号做稳定性排序性能提升非常明显。核心经验是不要因为某个算法“理论上 O(n log n)”就觉得它稳妥先看看数据形态再下结论。5.2 C 语言工程里的内存、链表与文件排序细节用 C 语言写这些排序最需要警惕的是内存而不是算法逻辑。算法题里 int tmp[1000000] 可能侥幸能跑但真实工程项目里动不动就百万级数据直接在栈上开大数组很容易爆栈。建议统一用 malloc/calloc 在堆上分配并且每次分配后都要判空。我看到太多同事写 calloc 失败后直接往下走程序在后续越界崩溃半天查不出原因。另外在数据结构教材里基数排序经常跟链表搭配出题也就是“链式基数排序”。用链表的好处是每轮分配无需整块连续内存按位分配到10个链表头节点里收拢时只需改指针。如果你在处理动态数据比如日志流的近实时排序这种链式实现很值得参考。外部排序场景下桶排序也很有价值把巨大文件先按区间切到多个小文件分别排好后再合并本质上就是桶排序思想在大数据量下的延伸。5.3 调试技巧与稳定性验证这三兄弟调试起来有一个通用技巧不要直接在几万条数据上排错先把数据规模压到10个左右并且在每个元素后面带上一个唯一的序号比如用结构体{value, seq}。排序完成后先检查整体是否有序再检查相同 value 的 seq 是否仍然递增这样稳定性对不对一目了然。我调试时还会在关键节点打印现场数据计数排序打印 count 数组和 output 数组桶排序打印每个桶的长度分布基数排序打印每一轮排序前后的完整数组。打印一两次之后问题基本就暴露了。另外随机生成测试数据时不要只测正数、只测均匀分布一定要覆盖负数、重复值、最大值、最小值、空数组、单元素数组这些边界。我见过不少实现平时跑得挺欢一遇到全是相同元素就跪了。5.4 我踩过的三个坑第一个坑是计数排序里前缀和覆盖了原始计数。调试时我想同时看“每个值的频次”和“累计位置”发现 count 经前缀和之后已经不是原始频次了导致我在脑内推演时对不上。后来我改用两个数组或者直接用注释把阶段标清楚思路就顺了。第二个坑是桶排序的除零问题。当 max 和 min 相等时(max - min 1) / bucket_count是0用来算桶下标会直接除零崩溃。所有值相同本来就不需要排序提前 return 就解决了。另一个相关问题是bucket_width用整数除法会把最后一个桶弄得很拥挤用浮点数计算才稳定。第三个坑是基数排序里exp * 10的溢出。当最大值接近 INT_MAX 时exp最后一次乘以10可能直接溢出成负数循环条件就乱了。解决方案是把 exp 声明成 long long或者每次循环前判断if (exp INT_MAX / 10) break;。这些都是不跑边界永远不会发现的细节。我个人在实际项目里的体会是非比较排序最迷人的地方在于“看清数据再选路”的思维方式而不是某段代码本身。三兄弟各有各的应用前提但它们的共同价值是让你在面试题里多一条降维打击的路径当别人还在考虑快排和归并谁更稳的时候你已经能根据数据形态直接给出更优解。最后分享一个练手建议找一天时间把这三个排序算法的 C 语言实现各默写一遍每写完一个就随机生成十万条数据验证稳定性和边界条件这套动作做完以后再遇到排序选型题基本不会再犹豫。