当下程序员求职、算法竞赛、大数据处理都绕不开排序算法,快排、归并排序等“经典款”早已被大家熟知,但有一种能实现线性时间复杂度的排序算法——计数排序,却常被忽视。它的原理是什么?作为线性时间排序的代表,又适用于哪些场景?本文为你详细拆解。

计数排序的核心逻辑是“以空间换时间”,完全跳出了传统排序的“两两比较”模式,适合数据范围明确且集中的场景。 具体来说,它的执行分为三步:第一步是统计,遍历待排序数组,统计每个元素出现的次数,存入一个临时的“计数数组”中——计数数组的下标对应原数组的元素值,值对应该元素的出现次数;第二步是前缀和计算,将计数数组转换为前缀和数组,此时每个位置的值代表“小于等于该下标的元素的总个数”,本质是确定元素的最终排位;第三步是反向填充,从原数组的末尾开始遍历,根据前缀和数组的定位,将元素放入结果数组的对应位置,每放置一个元素,就将对应计数减1,避免重复放置。
传统比较排序(如快排、归并)的时间复杂度下限是O(nlogn),这是因为基于比较的排序,最坏情况下需要至少log₂n!次比较,而计数排序之所以能实现线性时间(O(n+k),n为元素个数,k为数据范围),核心是它利用了元素的数值信息,而非仅依赖比较。 它的时间复杂度由两个变量决定:n(遍历原数组的次数)和k(遍历计数数组的次数)。当k远小于n时,计数排序的速度会远超比较排序;但如果k过大(比如对范围是1到1亿的数组排序),计数数组的空间成本会急剧上升,反而得不偿失。
计数排序并非“万能排序”,它的适用场景有明确限制:首先,待排序元素必须是整数(或可转换为整数的离散值),且数据范围k远小于元素个数n;其次,适合需要稳定排序的场景(稳定排序指相等元素的相对顺序不变),比如按年龄排序学生、按分数排序考生排名等。 举个典型例子:高考成绩排序,考生分数范围固定(一般为0到750分),考生人数(n)远大于分数范围(k=751),此时用计数排序排序,速度比快排快数倍,还能保证同分考生的原有顺序不变。而如果对范围分散的浮点数、字符串排序,或数据范围极大(如随机整数),计数排序则不适用。
1. 计数排序和快排的核心区别是什么? 答:核心区别是排序逻辑和时间复杂度:快排基于两两比较,时间复杂度为O(nlogn),空间复杂度O(logn),适合通用场景;计数排序基于统计计数,时间复杂度为O(n+k),空间复杂度O(k),仅适合数据范围集中的整数场景。
2. 计数排序一定比快排快吗? 答:不一定。当数据范围k远小于n时,计数排序更快;但如果k过大(如数据范围是1到100万,n只有1000),计数数组的空间成本极高,且O(n+k)的时间复杂度会高于快排的O(nlogn),此时快排更优。
3. 计数排序是稳定排序吗? 答:是。计数排序的第三步采用反向填充的方式,保证了相等元素的相对顺序与原数组一致,因此是稳定排序,适合需要保留相对顺序的场景(如按次关键字排序)。