在各类算法竞赛、大厂技术面试及工程实践中,计数排序(Counting Sort)作为典型的非比较排序算法,凭借其线性时间复杂度(O(n+k))在特定场景下展现出显著优势。本文将围绕计数排序Java实现展开系统性阐述,深入剖析其核心思想、实现细节、性能边界与工程适用性,结合真实代码示例、性能测试数据与高频面试题解析,帮助开发者构建完整的知识体系。全文内容超过4000字,涵盖从理论推导到工程落地的全链路知识。
与快速排序、归并排序等基于比较的排序不同,计数排序通过统计元素出现频次间接完成排序,规避了比较操作的下限限制(nlogn),但其适用前提是数据范围可控、整数类型为主。在Java开发中,合理选用该算法可显著提升特定业务场景(如年龄排序、分数统计、ID映射)的性能表现。本文将逐层拆解其设计逻辑,并提供可直接复用的高质量代码实现。
计数排序的本质是“以空间换时间”的典型范例。其核心思想可概括为三步:
设输入数组为arr,长度为n;元素取值范围为[0, k](k为最大值)。计数数组长度为k+1。例如对arr = [2,5,3,0,2,3,0,3]排序:
步骤1:频次统计
count = [2,0,2,3,0,1] → 表示0出现2次,1出现0次,2出现2次,3出现3次,4出现0次,5出现1次
步骤2:前缀和转换
count = [2,2,4,7,7,8] → 表示≤0的有2个,≤2的有4个,≤3的有7个,≤5的有8个
步骤3:逆序填充
从arr末尾开始:3→count[3]为7,填入output[6],count[3]减为6;下一个3→output[5];0→output[1]……最终output = [0,0,2,2,3,3,3,5]
关键点在于:前缀和数组count[i]表示的是“值≤i的元素个数”,即最后一个i应放置在output[count[i]-1]位置。由于计数数组记录的是“最后一个位置”,因此必须从原数组尾部开始遍历,以维持相同值元素的原始相对顺序——这正是计数排序具备稳定性的根本原因。
以下为严格遵循Java编码规范、具备完整边界检查与泛型适配能力的计数排序实现:
该实现满足:①原地排序(结果写回原数组);②空间复杂度O(n+k);③时间复杂度O(n+k);④稳定排序。特别注意第3步前缀和计算的必要性——若仅用频次数组直接填充,将丢失位置信息导致错误。
### 时间复杂度分析
设输入数组长度为n,元素最大值为k:
总时间复杂度为O(n + k),当k = O(n)时,退化为O(n),实现线性时间排序。
### 空间复杂度分析
总空间复杂度为O(n + k),这是其空间换时间特性的直接体现。
### 与比较排序的下限对比
任何基于比较的排序算法,其最坏时间复杂度下限为Ω(nlogn)。计数排序通过不进行元素比较,转而利用整数键的离散性,突破了该理论限制,属于“非比较排序”的典型代表。
稳定性指:相等元素在排序后保持原有相对顺序。计数排序通过“逆序填充”实现稳定性:
示例输入:[(id=1, score=90), (id=2, score=90), (id=3, score=85)]
按score排序后应为:[(id=3,85), (id=1,90), (id=2,90)]——id=1和id=2的相对顺序未颠倒
若省略逆序步骤(正序填充),则会导致相同分数的学生顺序颠倒,破坏业务逻辑中的时间先后关系。在Java中,若对自定义对象排序(如Student对象),需基于其可比较字段(如score)构建映射,此时稳定性对多级排序(先按班级再按分数)至关重要。
### 工程优化建议
错误实现:
for(int i=0; i<=max; i++)
for(int j=0; j
后果:无法保证稳定性(相同值元素顺序可能颠倒),且无法处理带附加信息的对象排序。
错误:count[i] = count[i] + count[i+1](正向累加)
正确:count[i] = count[i] + count[i-1](反向前缀)
后果:导致填充位置偏移,输出数组索引越界或数据丢失。
未处理空数组、单元素数组、全相同元素数组(如[5,5,5]);
未校验k值过大导致内存溢出(如k=10^9)。
| 算法 | 时间复杂度(平均) | 时间复杂度(最坏) | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | ✓ 稳定 | 整数、范围小 |
| 快速排序 | O(nlogn) | O(n²) | O(logn) | ✗ 不稳定 | 通用场景 |
| 归并排序 | O(nlogn) | O(nlogn) | O(n) | ✓ 稳定 | 需要稳定性的场景 |
| 堆排序 | O(nlogn) | O(nlogn) | O(1) | ✗ 不稳定 | 内存受限 |
| 基数排序 | O(d*(n+k)) | O(d*(n+k)) | O(n+k) | ✓ 稳定 | 多位整数排序 |
### 关键结论
答:稳定性源于“逆序填充”步骤。前缀和数组count[i]表示值≤i的元素个数,即最后一个i应放在output[count[i]-1]位置。逆序遍历原数组时,相同值的元素按原顺序依次占据连续位置,从而保持相对顺序不变。若正序填充,则第一个元素会占据最后位置,导致顺序颠倒。
答:通过偏移量平移。设最小值为minVal,则实际计数时将x映射为x-minVal,计数数组长度为maxVal-minVal+1。填充时再将结果减去minVal还原。例如输入[-2,0,3,-1],minVal=-2,则映射为[0,2,5,1],计数数组长度=3-(-2)+1=6。
答:严格意义上的原地排序(O(1)额外空间)不可行。因计数排序依赖额外计数数组(O(k)空间),且输出数组需暂存结果。但可通过“就地重建”减少空间:仅保留count数组(O(k)),再遍历count重建原数组,此时原数组被覆盖,但空间仍为O(k),非O(1)。
答:计数排序是桶排序的特例。桶排序将元素分到若干有序桶中,每个桶内可采用其他排序;而计数排序为每个可能值分配一个桶,且桶内仅计数不排序。当桶大小为1时,桶排序退化为计数排序。计数排序适用于整数、范围小;桶排序更通用(可处理浮点数),但需合理设计桶划分策略。
public static void sort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int min = findMin(arr);
int max = findMax(arr);
int range = max - min + 1;
int[] count = new int[range];
for (int num : arr) count[num - min]++;
for (int i = 1; i < range; i++) count[i] += count[i - 1];
int[] output = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
int num = arr[i];
output[--count[num - min]] = num;
}
System.arraycopy(output, 0, arr, 0, arr.length);
}
对无法一次性载入内存的数据(如日志流),可分块计数后合并:先处理每块生成局部count数组,再合并所有count数组(逐位相加),最后按合并后的count数组生成结果。此方案需额外存储每块的边界信息,适用于分布式场景(如Hadoop MapReduce的Combiner阶段)。
在高频调用场景(如每秒百万级排序请求),可通过ThreadLocal缓存count数组,避免重复分配内存。示例代码:
private static final ThreadLocal<int[]> COUNT_BUFFER = ThreadLocal.withInitial(() -> new int[10001]);
public static void sort(int[] arr) {
int max = findMax(arr);
int[] count = COUNT_BUFFER.get();
if (count.length <= max) {
count = new int[max + 1];
COUNT_BUFFER.set(count);
}
Arrays.fill(count, 0);
// ...后续步骤
}
可间接实现:将字符串映射为整数(如ASCII码序列),但需处理变长问题。更推荐直接使用String.compareTo()结合归并排序(Java的String排序基于TimSort)。若字符串长度固定且较短(如3位字母),可将字符串视为26进制数转换为整数后计数排序。
TreeMap底层为红黑树,插入复杂度O(logn),总排序O(nlogn);计数排序O(n+k)。当n大且k小时,计数排序快;但TreeMap支持动态插入、范围查询等,而计数排序需静态数据集。二者适用场景不同,不可直接比较。
需扁平化处理:将二维数组视为一维数组(如int[m][n] → int[m*n]),或基于某维度排序(如按第二维排序)。若需多关键字排序(先按行再按列),应使用基数排序。
Java 8起:对象数组用TimSort(O(nlogn)稳定排序),原生类型数组用Dual-Pivot Quicksort(快排变种,O(nlogn)不稳定)。计数排序需手动实现。
是!前提是实现时采用“逆序填充”步骤。若正序填充则不稳定。本实现保证稳定性。
可转换:将浮点数乘以10^d(d为小数位数)转为整数(如3.14→314),但需注意精度损失。更稳妥方案是自定义比较器结合其他稳定排序。
当关键字位数d较小时,Radix Sort(O(d*(n+k)))可能优于计数排序(O(n+k))。例如排序3位数(d=3),Radix Sort需3次计数排序,总复杂度O(3n);单次计数排序为O(n),但k可能更大。实际性能需基准测试确定。
① 检查数据范围是否异常(如max=10^9);② 改用基数排序;③ 分块计数+合并;④ 使用外部排序(磁盘临时文件)。
为保证稳定性。前缀和count[i]表示最后一个i的位置。逆序遍历时,相同值的元素按原顺序依次占据连续位置;若正序填充,第一个元素会占据最后位置,导致顺序颠倒。
Java标准库无直接实现。Apache Commons Math提供CountingSort(需引入依赖),但通用性低。生产环境建议按需定制实现。