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、2 | 1 放下标 1,2 放下标 3 | 先递减对应端点 |
| 放置 0、2 | 0 放下标 0,2 放下标 2 | 最终 [0,1,2,2] |
窄屏可左右滑动表格,阅读完整计算与理由。
计数决定每类元素占据的连续区间,反向扫描保证稳定性。
04为什么这个方法成立
- 前缀计数给出每个值应该占据的输出区间。
- 每放一个元素就消耗该值区间最右边的空位,不会跨到别的值区间。
- 每个输入被放置一次;同值保持先后,因此结果有序且稳定。
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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
[-2,0,-2,-1] 的频次是多少?
需要一点提示
lo=-2。
查看解析与答案
偏移后桶为 [2,1,1],输出 [-2,-2,-1,0]。
姓名记录按年龄排序,如何保留原先后?
需要一点提示
桶依据年龄,输出放完整记录。
查看解析与答案
将取键与放置对象分开,仍右向左扫描,放回原记录而不是只放年龄。
[1,1000000000] 适合吗?
需要一点提示
先计算 k。
查看解析与答案
不适合,桶需要十亿个位置;用比较排序或压缩映射更合理,压缩自身也有成本。