专题进阶 · 排序算法推荐总顺序 · 第 31 / 148 课

由频次表推到稳定放置位置,明确值域大小与空间限制。

先学会这些,再进入本课 数组 前缀和
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 排序算法

计数排序Counting Sort

统计离散整数频次,复杂度 O(n+k),要求值域 k 可控。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

由频次表推到稳定放置位置,明确值域大小与空间限制。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

输入是很多个小范围整数,比如班级成绩 0 到 100。为什么不必两两比较也能排序?

02一步步得到方法

用值作为下标

为每个可能值保存出现次数。若最小值为 lo、最大值为 hi,用 x−lo 映射到从零开始的桶,值域宽度 k=hi−lo+1。频次表将 n 个元素压成 k 个计数。

只输出整数时,按值从小到大重复输出各次数即可。但若元素还带姓名等附加信息,需要稳定放置,不能只输出值丢掉记录。

累加计数得到位置边界

将频次做前缀和后,count[v] 表示值不大于 v 的元素数量,也就是 v 对应输出区间的右端点。遇到值 v 时先让端点减 1,再放入该位置。

从输入右向左扫描,后出现的同键元素先占据更右位置,因此原相对次序得到保留。若仍按这个递减端点公式却从左向右扫,同键元素会倒序。

从频次到稳定的最终位置

频次数组只知道每个值出现多少次;累计频次还能告诉你每个值所在分段的结束位置。按原输入逆序放置相同键,可让较晚出现的元素占较晚位置,从而保留稳定性。

值域宽度 R 与元素个数 n 是不同参数。少量数分布在极大整数区间时,O(n+R) 的计数数组可能完全不划算,需要比较排序或其他表示。

03把一个小例子完全算清楚

[2,0,2,1],值域 0..2。

步骤计算与状态为什么这样做
频次[1,1,2]0 一次,1 一次,2 两次
累计[1,2,4]三类区间右端点
反向放置 1、21 放下标 1,2 放下标 3先递减对应端点
放置 0、20 放下标 0,2 放下标 2最终 [0,1,2,2]

窄屏可左右滑动表格,阅读完整计算与理由。

计数决定每类元素占据的连续区间,反向扫描保证稳定性。

04为什么这个方法成立

  1. 前缀计数给出每个值应该占据的输出区间。
  2. 每放一个元素就消耗该值区间最右边的空位,不会跨到别的值区间。
  3. 每个输入被放置一次;同值保持先后,因此结果有序且稳定。

05把推导翻译成代码

Python · 可独立运行的教学实现

def counting_sort(a):
    if not a:
        return []
    lo, hi = min(a), max(a)
    count = [0] * (hi - lo + 1)
    for x in a:
        count[x-lo] += 1
    for i in range(1, len(count)):
        count[i] += count[i-1]
    out = [0] * len(a)
    for x in reversed(a):
        count[x-lo] -= 1
        out[count[x-lo]] = x
    return out

逐个理解关键决定

x-lo
平移负值,不是取绝对值;例如 −2、−1 会映射为 0、1。
reversed(a)
配合从右端递减的位置公式保证稳定。

06时间、空间与实现范围

初始化和累加 k 个桶,扫描与输出 n 个元素,时间 O(n+k),空间 O(n+k)。

若只有两个数却相差十亿,k 远大于 n,计数排序通常不合适。比较排序的下界不约束利用小整数值域的模型。

07改变条件,检查哪里会出错

O(n+k) 被简写为永远 O(n)

只有 k 受控时才接近线性;先看值域,再看样本数量。

负数直接作为桶下标

Python 负下标会指向末尾,造成隐蔽错误,必须平移。

允许负数却直接作为数组下标

应将最小值作为偏移,或明确接口仅接受非负整数;Python 的负下标不会自动报错,尤其容易隐藏问题。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

[-2,0,-2,-1] 的频次是多少?

需要一点提示

lo=-2。

查看解析与答案

偏移后桶为 [2,1,1],输出 [-2,-2,-1,0]。

练习 2 · 边界与辨析

姓名记录按年龄排序,如何保留原先后?

需要一点提示

桶依据年龄,输出放完整记录。

查看解析与答案

将取键与放置对象分开,仍右向左扫描,放回原记录而不是只放年龄。

练习 3 · 变式与迁移

[1,1000000000] 适合吗?

需要一点提示

先计算 k。

查看解析与答案

不适合,桶需要十亿个位置;用比较排序或压缩映射更合理,压缩自身也有成本。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 排序

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。