非比较排序三兄弟：计数排序、桶排序、基数排序详解与C实现

排序算法里的“非比较排序三兄弟”，我愿称之为算法面试和工程项目里性价比被严重低估的一组工具。大多数人一提到排序就条件反射式地写快排，但真遇到特定形态的数据时，快排反而成了下策。这篇文章我把计数排序、桶排序、基数排序从原理到C语言实现再到避坑细节，完整拆一遍，希望能帮你彻底通关这三兄弟。

1. 为什么排序不止快排：先看比较排序的O(n log n)天花板

1.1 比较排序为什么卡在O(n log n)？

很多人第一次听说“排序不可能快过O(n log n)”时，都觉得是经验结论，其实这是一个有严格数学证明的结论，而且证明逻辑很简单。任意一个基于比较的排序算法，每次比较只能得到两个结果：要么大，要么小，相当于做了一次二选一的判断。n个元素一共有n!种可能的排列，理论上算法必须能区分出每一种排列，才能保证排序正确。这就好比一棵二叉树，叶子节点至少要有n!个，而树的高度就对应了最坏情况下需要比较的次数。叶子数等于n!，高度至少是log2(n!)，用斯特林公式化简一下，就得到O(n log n)。

这个下界管的是快排、归并、堆排这些“靠两两比大小来决定顺序”的算法。不管你怎么优化常数、怎么做pivot选型，复杂度这个天花板是实打实的。很多人忽略了一个关键问题：这个结论的前提是“基于比较”。如果算法根本不依赖比较元素之间的大小，那这个下界就不适用了，这也正是非比较排序能突破O(n log n)的根本原因。

1.2 非比较排序的破局思路：不比较，直接定量归位

非比较排序的思路和比较排序完全不同。它不再问“a和b谁大”，而是直接利用输入数据的结构特征，把数据放到它该去的位置上。数据如果是取值范围有限的整数，我就开一个计数数组，统计每个数值出现的次数，然后按顺序倒出来；数据如果均匀分布在某个区间内，我就把区间切成若干段，把数据扔进对应的段里排序；数据如果是多位数，我就从最低位开始，一位一位地做稳定排序，最后自然会整体有序。

这三种思路分别对应着计数排序、桶排序和基数排序。它们的共同点是：不需要在元素之间做“比较”这个动作，所以复杂度不再被O(n log n)锁死。实际使用中，它们往往能把几千万条数据的排序时间从秒级压到毫秒级，代价是通常需要额外的内存空间，典型的以空间换时间。

1.3 计数排序、桶排序、基数排序的定位关系

很多人觉得这三个算法是独立的知识点，其实它们是一条思路上的连续演化。计数排序是按“值”开格子，一个值占一个格子，适合值域很窄的整数；桶排序是按“区间”开桶，一个区间一个桶，把数值范围细分之后逐个处理；基数排序是按“位”多次切分，每次切分都借助计数排序来做稳定搬运。

我习惯这么理解：计数排序是“一个萝卜一个坑”，桶排序是“一堆萝卜一箩筐”，基数排序是“分轮次按特征挑萝卜”。三者不是孤立的，而是同一思想在不同粒度下的展开。学会了一个，另外两个很快就能融会贯通。

2. 计数排序：小值域海量数据的最强快排替代

2.1 三步走原理：统计频率、前缀和定位、稳定回填

计数排序的核心可以拆成三步。第一步，扫描一遍原始数组，找到最小值和最大值，算出值域范围range = max - min + 1，然后分配一个长度为range的计数数组。第二步，再扫一遍原始数组，统计每个值出现的次数，存进计数数组；接着把计数数组原地改成前缀和，也就是让count[i]变成“小于等于当前值的元素总个数”，等价于该值在排序结果中的最后一个位置。第三步，从原数组的末尾开始往前扫描，每遇到一个元素，根据它的值定位到计数数组中的位置，放到临时数组里，同时把对应位置的计数减一。

关键是第三步为什么一定要从后往前。如果从前往后扫，同一个值的多个元素被依次放进临时数组中，原数组里靠前的会先被放进去，位置却更靠后，相同元素的相对顺序就颠倒了，排序不稳定。而从后往前扫时，后出现的元素会被放到更靠后的位置，先出现的元素由于计数还没减到，会落在前面，正好保持了原始顺序。

2.2 计数排序C语言实现：从后往前遍历保住稳定性

直接上代码，这段实现同时考虑了负数和稳定性，可以直接用在工程里。

#include <stdio.h> #include <stdlib.h> #include <string.h> void countingSort(int *arr, int n) { if (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]; } int range = max - min + 1; int *count = (int *)calloc(range, sizeof(int)); if (!count) return; for (int i = 0; i < n; i++) { count[arr[i] - min]++; } for (int i = 1; i < range; i++) { count[i] += count[i - 1]; } int *tmp = (int *)malloc(n * sizeof(int)); if (!tmp) { free(count); return; } for (int i = n - 1; i >= 0; i--) { int value = arr[i] - min; tmp[--count[value]] = arr[i]; } memcpy(arr, tmp, n * sizeof(int)); free(tmp); free(count); }

代码里的arr[i] - min是核心，它把所有数值都映射到非负下标，负数也能正确处理。tmp[--count[value]]这一步既要定位，又要更新计数，这里最容易写错。很多人会写成tmp[count[value]--]或者直接tmp[count[value]]，前者会导致相同值被放到同一个位置然后覆盖，后者会让重复值越界。

2.3 能用来排负数吗？边界条件与适用限制

负数完全能排，上面的实现已经处理了min偏移。真正要警惕的是值域过大。假设数据范围从-100000000到100000000，即使只有几百个元素，你也得开一个两亿长度的计数数组，内存直接爆炸。所以计数排序的适用条件非常明确：n大、k小，也就是数据量很大但取值范围很窄。

典型的例子是给几百万个年龄在0到100岁的用户排序，给几十万考生按0到750分的高考成绩排序，或者给一批固定范围内的IP段计数。如果你是给一个包含几万个浮点数的数组排序，计数排序就完全派不上用场。判断标准就一条：max - min这个范围是否在可接受的内存范围内。

我实际用计数排序最多的场景是做数据仓库里的临时分桶，先把用户按某种固定枚举值分组，再对组内做后续处理。这种情况下，计数排序不是作为最终排序算法出现，而是作为分组的底层工具，速度非常可观。

3. 桶排序：把数据切成段，桶内各自为战

3.1 桶排序到底在分什么？均匀分布才是主场

桶排序的思路比计数排序更灵活。计数排序是一个值一个格子，桶排序则是把一个区间看作一个桶，数据按大小扔进不同的桶里，然后每个桶内部排序，最后按桶的顺序依次收集。可以把它理解为先进行一轮粗排序，让所有数据大致落在正确区间，再做细排序。

桶排序表现最好的前提是数据分布比较均匀。如果数据在取值范围内近似均匀分布，那么每个桶里的元素数量大致相当，总时间复杂度接近O(n)。反之，如果所有数据都挤在同一个桶里，那一轮粗分等于白做，复杂度直接退化成桶内排序算法的复杂度，插入排序的话就是O(n²)。

这也就是为什么桶排序常常出现在浮点数排序的教科书例题里，因为浮点数据天然适合按区间分桶。处理0到1之间的均匀分布浮点数时，把区间等分成n个桶，每个桶期望只有一个元素，排序几乎是线性的。

3.2 桶数怎么定、桶内排序用什么？我的选型建议

桶数需要权衡。桶太少，每个桶里元素太多，桶内排序压力大；桶太多，内存浪费严重，收集时也会增加遍历开销。我一般建议桶数取n或者略小于n的平方根量级，具体看数据量和值域。数据量不大时，桶数等于n最省事；数据量大时，桶数取sqrt(n)左右，每个桶平均元素数保持在可接受范围。

桶内排序我强烈推荐插入排序。原因有两个：一是桶内元素通常不会太多，插入排序在小规模数据上的实际运行速度非常快，常数很小；二是插入排序实现简单，不容易出错。虽然理论上可以用快排、归并来排桶内，但那是大炮打蚊子，函数调用和递归栈的开销反而拖慢整体速度。

3.3 桶排序C语言实现：基于动态桶的完整示例

下面这个示例假设待排序的是[0, 1)区间内的浮点数，用动态二维结构来管理桶。

#include <stdio.h> #include <stdlib.h> void insertionSort(float arr[], int n) { for (int i = 1; i < n; i++) { float key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } void bucketSort(float arr[], int n) { if (n <= 1) return; int bucketNum = n; float **buckets = (float **)malloc(bucketNum * sizeof(float *)); int *bucketSize = (int *)calloc(bucketNum, sizeof(int)); for (int i = 0; i < bucketNum; i++) { buckets[i] = (float *)malloc(n * sizeof(float)); } for (int i = 0; i < n; i++) { int idx = (int)(arr[i] * bucketNum); if (idx >= bucketNum) idx = bucketNum - 1; buckets[idx][bucketSize[idx]++] = arr[i]; } int k = 0; for (int i = 0; i < bucketNum; i++) { insertionSort(buckets[i], bucketSize[i]); for (int j = 0; j < bucketSize[i]; j++) { arr[k++] = buckets[i][j]; } free(buckets[i]); } free(buckets); free(bucketSize); }

这段代码里有两个细节值得说。一个是idx = (int)(arr[i] * bucketNum)，当arr[i]等于1.0时，idx会等于bucketNum，造成数组越界，所以必须加if (idx >= bucketNum)的保护。另一个是每个桶都预先分配了n个float空间，这是为了简化管理，但内存使用量会比较大，数据量达到百万级别时建议改用链表或者动态增长的桶结构，否则浪费严重。

如果你处理的是非均匀分布数据，可以改为“平方根分桶”或“百分位分桶”，先扫描一遍数据，找到合适的分桶边界，这样数据分布再歪也基本能保住线性性能。

4. 基数排序：多关键字稳定排序的经典套路

4.1 LSD思路：先排低位，再排高位，稳定是灵魂

基数排序的核心思想是“多关键字排序”，最常见的实现是LSD，也就是从最低有效位到最高有效位，逐轮进行稳定排序。以三位数排序为例，先按个位排序，再按十位排序，最后按百位排序。每轮排序都必须保持稳定性，否则前一排好的低位顺序就会被破坏。

为什么稳定性是灵魂？因为每一轮排序其实是在处理一个“关键字”，个位是第一关键字，十位是第二关键字，百位是第三关键字。只有当处理高位时，低位已经排好的相对顺序仍然被保持，最终结果才能像字典序一样，高位优先、次高位其次、低位兜底。如果某轮排序不稳定，前面几轮的工作就白做了。

基数排序的时间复杂度是O(d * (n + k))，d是数字位数，k是基数大小，典型取10或256。这正好解释了为什么它适合固定长度的整数、手机号、身份证号这类数据，因为这些数据的位数固定，每一轮都是线性复杂度，整体依然远快于比较排序。

4.2 基数排序C语言实现：用计数排序当子过程

基数排序的每一轮排序，本质上就是一次按某个位进行的计数排序。下面是比较经典的十进制LSD实现。

#include <stdio.h> #include <stdlib.h> int getMax(int arr[], int n) { int mx = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] > mx) mx = arr[i]; } return mx; } void countingSortForRadix(int arr[], int n, int exp) { int count[10] = {0}; int *tmp = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) { count[(arr[i] / exp) % 10]++; } for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; } for (int i = n - 1; i >= 0; i--) { int k = (arr[i] / exp) % 10; tmp[--count[k]] = arr[i]; } for (int i = 0; i < n; i++) { arr[i] = tmp[i]; } free(tmp); } void radixSort(int arr[], int n) { int maxVal = getMax(arr, n); for (int exp = 1; maxVal / exp > 0; exp *= 10) { countingSortForRadix(arr, n, exp); } }

这里的exp从1开始，依次取10、100、1000，代表当前处理的位。maxVal / exp > 0作为循环条件，可以保证所有位数都处理完。每轮的子过程就是一次按位计数排序，count数组大小固定为10，因为十进制每位的取值只有0到9。

C语言中变长数组tmp[n]在C99标准下可以直接使用，但如果你用C++或部分嵌入式环境，建议改成malloc动态分配，上面代码里已经用了malloc，兼容性更好。

4.3 负数、可变长字符串与按字节优化

负数处理是基数排序最常见的坑。直接对负数取模，结果可能是负数，比如(-3) % 10结果是-3，直接拿去做count数组下标就崩了。我建议先统一偏移：扫描出最小值min，如果min是负数，就把每个元素都减去min，让最小值变成0，再执行基数排序，排完再统一加回min。这样实现简单，而且不改变元素之间的相对大小关系。

字符串排序也可以用基数排序，但要注意方向。固定长度的字符串适合LSD，从最后一位开始往前排，长度不足的补零字符。如果字符串长度差异很大，更推荐MSD思路，先按第一个字符分桶，再递归处理每个桶内字符串，类似字典树的遍历。不过MSD处理不好容易栈溢出，工程上通常不会对很长的字符串用基数排序。

4.4 按字节排序的进阶：int32只需四趟

如果你处理的是一批32位整数，十进制逐位排序至少要排10趟，而int32一共只有4个字节，完全可以直接按字节排。基数不取10，取256，每轮取数字的一个字节作为计数排序的键，4轮就能完成排序。这样既能把循环次数从10降到4，又可以用位运算取字节，速度提升非常明显。

核心取字节逻辑大概是这样的：

uint32_t u = (uint32_t)arr[i]; int byte = (u >> (pass * 8)) & 0xFF;

最高字节有符号位干扰，需要做一次异或翻转来保证排序正确性。这种按字节排序的方案在实际项目中非常常见，处理大规模int数据时比快排还要快很多。如果面试时你能说出这层优化，效果会很加分。

5. 三兄弟怎么选：复杂度对比与实际使用场景

5.1 三兄弟复杂度与稳定性对比表

我把三者放在一起做一个直接对比，方便快速查阅。

从表里能清楚看到，稳定性最好的就是计数排序和基数排序，因为它们的回填过程天然保证相同值的原始顺序。桶排序的稳定性完全取决于桶内排序，如果桶内用插入排序则是稳定的，用快排则不稳定。

5.2 实测场景一：千万级ID排序为什么选计数排序

有一次我在做数据清洗任务，要对几千万条用户ID做排序和去重。那些ID是一个自增字段，取值在某个固定区间内，范围只有几万。我第一次用快排试了下，几千万条数据排序要好几秒，而且内存占用也不小。换成计数排序后，先扫一遍找到min和max，分配几万个int的计数数组，再扫两遍完成排序，整个过程不到100毫秒，性能差距达到了几十倍。

这个例子很典型。数据量巨大，但值域窄，正是计数排序的绝对主场。如果当时我不了解非比较排序，就会老老实实用快排，白白浪费了数据本身的特征。

5.3 实测场景二：浮点特征打分排序为什么选桶排序

另一个项目里需要对模型输出的打分结果排序，分数是0到1之间的浮点数，数量大概几百万条，分布比较均匀。我一开始想用归并排序，但后来改成了桶排序，先按区间分了1000个桶，对每个桶做插入排序。分桶和桶内排序的总耗时比归并排序快了将近一倍，而且代码量还少很多。

浮点数不适合计数排序和基数排序，因为值的数量理论上无限。但桶排序天然适合区间切分的思路，尤其是分布相对均匀的连续型数据。如果数据分布歪得厉害，我就先做一次分位数扫描，调整桶边界，再排。

5.4 什么时候老老实实用快排？什么时候必须换？

我的判断标准很简单。数据是整数且值域远小于n，优先计数排序；数据是均匀分布的连续值，优先桶排序；数据是定长整数或定长字符串，优先基数排序；数据形态不满足以上任何一种，比如随机大整数、任意长度字符串，那就规规矩矩用快排或归并。

这里要提醒一句：不要为了炫技强行使用非比较排序。如果k值大得离谱，桶内大量退化，或者位数太长导致轮次太多，非比较排序的性能反而不如快排。工具没有绝对的好坏，只有合不合适。

6. 避坑笔记：非比较排序常见七宗罪与排查指南

6.1 高频BUG：越界、符号位、稳定性、内存爆表

我见过的非比较排序翻车现场，基本集中在七个方面。第一个是没有做min偏移，直接用原数组数值做count下标，遇到负数直接越界。第二个是前缀和处理时忘记之间隔过了自己，很多新手会写出count[i] = count[i-1]而不是count[i] += count[i-1]，导致结果少算了一个元素。

第三个是从前往后回填导致不稳定。这个问题在笔试里经常出现，面试官让你手写计数排序时，你从前往后写，得到的数组仍然有序，但相同值的相对顺序反了，稳定性这一条就被扣分。第四个是桶排序的边界处理，浮点值恰好等于区间右端点时idx会越界，必须做保护判断。第五个是基数排序对负数取模，C语言里负数取模结果是负数，必须统一偏移或者单独处理正负。第六个是内存爆表，计数数组开太大或者桶二维数组预分配过大，数据量一大就OOM。

第七个是忘记恢复偏移。基数排序做完后，如果之前做了统一偏移，一定要记得把每个元素加回偏移量，否则排出来的是一组错位的数值，结果对不上原始数据。这个错误特别隐蔽，因为数组看起来“有序”，但数值全部偏了，只有和原始数据对比时才会发现。

6.2 快速自查清单：面试上机前过一遍

每次写非比较排序，我建议你上机前花半分钟过一遍这个清单。第一个问题：数据是整数还是浮点数，有没有负数，值域大概多大？第二个问题：如果选计数排序，max和min是否都正确求出，count下标是否有偏移？第三个问题：如果选桶排序，分桶边界是否正确，桶内排序选用的是不是稳定算法？第四个问题：如果选基数排序，每轮取位是否正确，exp每次是否乘10，负数是否做偏移，临时数组是否释放？第五个问题：稳定性是否满足需求？

测试用例也很有讲究。空数组、单元素数组、全相同值数组、逆序数组、含负值数组，这五类都必须跑一遍。往往核心里就是最小值、最大值或者负数这种情况出问题。我自己以前写桶排序时，就是忘了考虑arr[i]恰好等于1.0的情况，最后排查了很久才发现是边界越界。

最后分享一个我个人的小习惯：写完排序算法后，我会顺手打印每一轮排序的中间结果。计数排序看前缀和数组是否正确，基数排序看每一轮之后的数组是不是“低位数有序”的状态，桶排序看每个桶的元素数量是否大致均匀。这样哪怕是出问题，也能把bug范围快速缩小到某一个环节，而不是对着最终结果猜。

这三兄弟入门不难，真正拉开差距的还是对边界条件的敏感度和对数据形态的判断力。希望这篇攻略能让你少踩我之前踩过的坑。