前四天我们学了快排、归并、堆排它们都是比较排序——靠两两比大小决定顺序。但计算机科学早就证明任何基于比较的排序最坏情况下不可能快于 O(nlogn)。那有没有办法掀桌子有——不比较直接“数”。今天介绍的计数排序和基数排序就是利用“值域”信息硬生生把排序拉到O(n)级别。当然这有个前提数据范围得可控。一旦满足它们会快得让快排怀疑人生。我们用LC.1122「数组的相对排序」来实战计数排序顺便把基数排序和桶排序一并收编。 题目速览30 秒读懂给定arr1和arr2arr2中的每个元素都出现在arr1中。要求对arr1排序使得在arr2中出现的元素按arr2的顺序排列未在arr2中出现的元素按升序排在末尾。示例arr1 [2,3,1,3,2,4,6,7,9,2,19],arr2 [2,1,4,3,9,6]输出[2,2,2,1,4,3,3,9,6,7,19]约束元素值域 0~1000长度 ≤ 1000。关键信号值域有限且小 → 计数排序的天然舞台。 核心思路计数 往格子里扔排序 按格子倒出来比较排序的“笨”在哪每两个元素都要比一下才知道谁大谁小整个过程像打擂台。计数排序的“聪明”在哪给每个可能的值准备一个“格子”桶遍历一次数组每个数直接扔进对应的格子——扔进去的同时排序就已经完成了。类比给全班同学按身高排队不需要两两比较。你只需在墙上从 150cm 到 200cm 每隔 1cm 贴一个格子每人站进自己的格子然后从左到右依次报数队伍自然有序。本题的特殊之处顺序不是按数值大小而是按arr2给定的优先级。所以分三步计数统计arr1中每个值出现的次数。按arr2输出遍历arr2每个元素输出count[x]次输出完清零。剩余升序垫后扫描计数数组下标天然有序把还没输出的值按升序输出。三步完美贴合题目两个要求。️ 图解算法手把手走一遍arr1 [2,3,1,3,2,4,6,7,9,2,19],arr2 [2,1,4,3,9,6]Step 1计数值域 0~19开 20 个格子值123467919次数13211111Step 2按 arr2 顺序输出arr2 遍历到输出动作2 → 输出 3 次2,2,2count[2]01 → 输出 1 次1count[1]04 → 输出 1 次4count[4]03 → 输出 2 次3,3count[3]09 → 输出 1 次9count[9]06 → 输出 1 次6count[6]0当前结果[2,2,2,1,4,3,3,9,6]Step 3剩余值升序垫后扫描计数数组还有 7 和 19最终[2,2,2,1,4,3,3,9,6,7,19]✅ 代码实现Python JavaPython 版计数排序最简写法classSolution:defrelativeSortArray(self,arr1:List[int],arr2:List[int])-List[int]:# 值域 0~1000开 1001 个格子count[0]*1001forxinarr1:count[x]1res[]# 按 arr2 顺序输出forxinarr2:res.extend([x]*count[x])count[x]0# 清零避免重复# 剩余值升序垫后forvinrange(1001):ifcount[v]0:res.extend([v]*count[v])returnresJava 版计数排序 基数排序完整示例// LC.1122 计数排序解法classSolution{publicint[]relativeSortArray(int[]arr1,int[]arr2){int[]countnewint[1001];for(intx:arr1)count[x];int[]resnewint[arr1.length];intidx0;for(intx:arr2){while(count[x]--0)res[idx]x;// 注意count[x] 自减到 -1之后需要重置为 0count[x]0;}for(intv0;v1000;v){while(count[v]--0)res[idx]v;}returnres;}}// 基数排序LSD处理非负 intclassRadixSort{publicvoidradixSort(int[]nums){if(nums.length0)return;intmaxArrays.stream(nums).max().getAsInt();// 从个位到最高位每轮做一次稳定的计数排序for(intexp1;max/exp0;exp*10){countingSortByDigit(nums,exp);}}privatevoidcountingSortByDigit(int[]nums,intexp){intnnums.length;int[]countnewint[10];// 每位 0~9int[]outputnewint[n];for(intx:nums)count[(x/exp)%10];// 前缀和转成位置信息for(inti1;i10;i)count[i]count[i-1];// 逆序回填保证稳定性for(intin-1;i0;i--){intd(nums[i]/exp)%10;output[--count[d]]nums[i];}System.arraycopy(output,0,nums,0,n);}}⚠️防坑提醒计数数组大小必须覆盖值域上限本题 1000。按arr2输出后要清零不然第三步会重复输出。基数排序中逆序回填是保证稳定性的关键不能省略。⏱️ 复杂度分析面试必问算法时间空间前提计数排序O(n k)O(k)值域k可控基数排序O(d·(n k))O(n k)d为位数k 为基数通常10桶排序期望O(n)O(n)数据分布均匀比较排序理论下界O(nlogn)计数/基数/桶排序通过“不比较”绕开了这个限制代价是额外空间和对值域的依赖。 举一反三3 道高频变种题题目变化点应对策略LC.164最大间距求排序后相邻元素最大差值要求线性时间标准解是基数排序或桶排序鸽巢原理证明桶间必有一个答案LC.274H指数统计引用次数分布用计数数组统计O(n) 求解LC.791自定义字符串排序按自定义字母表顺序重排字符串与LC.1122同构计数解法平移 面试追问模拟提前准备Q1为什么比较排序的下界是O(nlogn)n个元素有n! 种排列比较排序每比一次只获得1bit信息大于/小于决策树深度至少log₂(n!) ≈ nlog₂n。计数排序不比较直接用值定位绕开了这个下界。Q2计数排序的适用场景和局限适用值域小且已知年龄、成绩、IP段、数据量大、整数或可离散化的键。局限值域太大则空间爆炸比如32位整数要开40亿个格子、浮点数无法直接使用。Q3基数排序为什么每轮必须稳定举例排序[21, 12]。按个位排完是[21, 12]个位12。如果十位排序不稳定可能把12换到21前面导致结果错误[12,21]虽然也对但换个例子[21, 12, 13]就会乱。高位只定大局低位次序靠稳定性保留这是基数排序的命门。Q4桶排序和计数排序有什么区别计数排序每个值一个桶桶内只有一个值桶排序把值域分成若干区间每个桶内可能有多个元素需要单独排序或递归。计数排序是桶排序的一种特例桶大小1。 实战小技巧刷题党必备口诀值域小计数好位数定基数巧分布匀桶有戏。模板看到“值域 ≤ 10⁵”且要求线性时间优先考虑计数。防坑基数排序记得处理负数取补码或转无符号桶排序桶内排序用插入排序更稳定。 实际应用场景不止是刷题数据库低基数列统计如性别、省份的聚合查询。图像处理颜色直方图均衡化计数排序。后缀数组构建倍增 基数排序是标准工程实现。IP地址限流按IP段计数统计访问量。成绩分段排名高考分数统计0~750分。 今日思考题如果数据范围是[-10^5, 10^5]计数排序还能用吗要做什么调整提示可以整体偏移把负数映射到非负下标。如果数据是小数浮点数计数排序还能用吗有什么替代方案