排序算法里的“非比较排序三兄弟”我愿称之为算法面试和工程项目里性价比被严重低估的一组工具。大多数人一提到排序就条件反射式地写快排但真遇到特定形态的数据时快排反而成了下策。这篇文章我把计数排序、桶排序、基数排序从原理到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 三兄弟复杂度与稳定性对比表我把三者放在一起做一个直接对比方便快速查阅。算法平均时间复杂度最坏时间复杂度额外空间稳定性最适合的数据形态计数排序O(n k)k为值域范围O(n k)O(k)稳定小值域整数、枚举值、年龄/分数桶排序O(n)数据均匀时O(n²)数据倾斜时O(n)取决于桶内排序均匀分布浮点数、海量外排序基数排序O(d(n k))d为位数O(d(n k))O(n k)稳定定长整数、定长字符串从表里能清楚看到稳定性最好的就是计数排序和基数排序因为它们的回填过程天然保证相同值的原始顺序。桶排序的稳定性完全取决于桶内排序如果桶内用插入排序则是稳定的用快排则不稳定。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范围快速缩小到某一个环节而不是对着最终结果猜。这三兄弟入门不难真正拉开差距的还是对边界条件的敏感度和对数据形态的判断力。希望这篇攻略能让你少踩我之前踩过的坑。
排序算法里的“非比较排序三兄弟”我愿称之为算法面试和工程项目里性价比被严重低估的一组工具。大多数人一提到排序就条件反射式地写快排但真遇到特定形态的数据时快排反而成了下策。这篇文章我把计数排序、桶排序、基数排序从原理到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 三兄弟复杂度与稳定性对比表我把三者放在一起做一个直接对比方便快速查阅。算法平均时间复杂度最坏时间复杂度额外空间稳定性最适合的数据形态计数排序O(n k)k为值域范围O(n k)O(k)稳定小值域整数、枚举值、年龄/分数桶排序O(n)数据均匀时O(n²)数据倾斜时O(n)取决于桶内排序均匀分布浮点数、海量外排序基数排序O(d(n k))d为位数O(d(n k))O(n k)稳定定长整数、定长字符串从表里能清楚看到稳定性最好的就是计数排序和基数排序因为它们的回填过程天然保证相同值的原始顺序。桶排序的稳定性完全取决于桶内排序如果桶内用插入排序则是稳定的用快排则不稳定。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范围快速缩小到某一个环节而不是对着最终结果猜。这三兄弟入门不难真正拉开差距的还是对边界条件的敏感度和对数据形态的判断力。希望这篇攻略能让你少踩我之前踩过的坑。
，环境配置)
