【真题算法·第十期】计数排序和桶排序
01 知识点详解
1. 什么是计数排序？
投票唱票——在黑板上写下所有候选人的名字（值的范围），每念到一票就在对应名字下画"正"字（计数），最后按得票数宣布结果。
计数排序（Counting Sort）不通过比较来排序，而是统计每个值出现的次数，再按值的顺序还原出有序序列。充分利用了数组下标的有序性。计数排序是特殊的桶排序。
核心思想：用一个计数数组 c[值] 记录每个值出现了几次，
然后按值从小到大的顺序，根据 c[值] 输出对应个数的该值。
2. 标准代码模板
# 成绩范围 0~100，统计每个分数的出现次数
c = [0] * 101 # 计数数组，c[i] 表示分数 i 的人数
for i in range(n):
c[a[i]] += 1 # 统计
# 输出排序结果（按值从小到大输出每个值的所有副本）
for i in range(101):
for j in range(c[i]):
print(i, end=' ') # 输出 c[i] 个 i
# 从高到低计算名次
mc = 1 # 名次从 1 开始
b = [0] * 101 # b[i] 表示分数 i 的名次
for i in range(100, -1, -1):
if c[i] != 0:
b[i] = mc # 分数 i 的名次为 mc
mc += c[i] # 下一个分数的名次 = 当前名次 + 当前分数人数
# 输出每个学生的名次
for i in range(n):
score = a[i]
print(f"学生{i}: 分数{score}, 第{b[score]}名")
3. 计数排序的适用条件
计数排序的适用条件
4. 什么是桶排序？
桶排序（Bucket Sort）将数据按值域分配到若干个「桶」中，每个桶内部再排序，最后按桶的顺序合并。
计数排序 vs 桶排序：
- 计数排序：每个值一个桶（桶数 ≥ 值域大小），适合值域小的场景
- 桶排序：值域划分为若干区间（桶数 < 值域大小），适合值域大但分布均匀的场景
在浙江选考中，考查最多的是计数排序的思想——用数组下标表示值、用数组元素值表示出现次数。纯「桶排序」几乎不考，但「桶思想」（分类统计）是高频考点。2024年1月压轴题利用“计数排序思想”优化分组算法是考查的巅峰。
[观点]“桶思想”在算法领域本质上是分类（Classification）与哈希映射（Mapping）思想。在浙江选考的有限数据范围场景下（如成绩统计、年龄排序），它衍生出计数排序和标记数组等考法。也因此，遇到类似问题，或者处理方法时，大多数老师称之为“桶思想”，实际上并不准确，我建议使用：属性下标化（或者状态索引化）。其含义是：在值域较小且离散的前提下，利用数组下标的O(1)随机访问特性，将原本需要通过遍历比较才能确定的“业务属性”或“数据类别”，直接转化为数组的“逻辑存储地址”。这样就能把复杂的查找/比较操作，降维为一次简单的数组寻址，从而极大提升效率。
5. 计数 vs 比较排序
计数排序 vs 比较排序
◆ ◆ ◆
02 真题举例
【2018年11月·第12题】字符升序序号计算
来源：201811-Q12-计数排序
【Python版】下列Python程序功能为：输入一个字符串，计算各字符升序排列的序号，并将序号保存在数组y中。如文本框内容为"2011"，程序运行后y[0]~y[3]各元素的值分别为"4,1,2,3"。
s = input("输入字符串：")
n = len(s)
y = [1] * n
for i in range(___(1)___):
for j in range( ___(2)___ , n):
if ___(3)___ :
y[j] = y[j] + 1
else:
y[i] = y[i] + 1
print(y[1:])
A. （1）n （2）1 （3）s[j] >= s[i] B. （1）n （2）1 （3）s[j] > s[i] C. （1）n-1 （2）i+1 （3) s[j] >= s[i] D. （1）n-1 （2）i+1 （3） s[j] > s[i]
📝 解析
外层循环无需遍历到n，到n-2即可避免重复比较，故(1)是n-1；内层循环从i+1开始，只和后续字符比较，故(2)是i+1；字符比较条件为>=，满足则对应序号+1，故(3)是s[j]>=s[i]；答案选C。
📌 考点：计数思想在两两比较中的应用——每次比较，较小的字符序号+1（排名后退），等价于统计"有多少个字符比我小"。
◆ ◆ ◆
【2017年04月·第17题】属性下标化和数组应用
来源：201704-Q17-数组操作-计数排序
【Python版】小王编写了一个依据成绩计算名次的Python程序，成绩为0到100之间的整数。算法的基本思想：先统计每个分数的个数，然后按照分数从高到低依次计算每个有效分数对应的名次，分数相同时名次并列。最高分为第1名，该分数的名次与个数之和为下一个有效分数的名次，以此类推。程序用数组A存放每个分数对应的个数，数组B存放每个分数对应的名次。
实现上述功能的Python程序如下，请回答下列问题： （1）如表所示，若分数93的个数为2，则该分数对应的名次为________ （2）请在划线处填入合适的代码。
sName = ["陈立港","李小宝","历乐天","杨加惠","许兴天","潘恩西","高力军","杨红婷"]
sScore = [75,87,100,85,76,100,65,96]
____①____ # 学生人数
# 统计分数个数、计算名次
A = [0] * 101 # A[i]表示分数i的人数
B = [0] * 101 # B[i]表示分数i的名次
for i in range(n):
____②____
mc = 1
for i in range(100, -1, -1):
if A[i] != 0:
B[i] = mc
____③____
# 输出学生姓名、分数、名次
for i in range(n):
score = sScore[i]
mc = B[score]
print(sName[i], score, "第", mc, "名")
📝 解析
（1）分数93个数为2，名次为：7。
（2）① n = len(sName)：使用len()函数得到学生人数。
② A[sScore[i]] += 1：统计每个分数出现次数。
③ mc += A[i]：更新下一个分数名次 = 当前名次 + 当前分数人数。
📌 考点：计数排序的完整流程——统计频次→从高到低计算名次→输出。值域0~100正好适合计数数组。
◆ ◆ ◆
【2021年06月·第16题】小组成绩计算
来源：202106-Q16-计数排序
【Python版】有 n 个小组（编号 1 至 n），每个小组有 m 个成员，每个成员都有一个大于等于 0 的得分。现要求按下列规则计算每个小组的成绩，并找出成绩最高的小组。
小组成绩的计算规则是：若小组成员中得分最高的前 k 人得分都不低于 k，且其他成员得分都不超过 k，则该小组成绩为 k。例如，第 1 小组共有 8 个成员，得分依次为"5，2，7，11，8，6，5，1"，由此可知最高的前 5 人得分为"11，8，7，6，5"，其他 3 人得分为"5，2，1"，因此该小组成绩为 5。程序运行如下图所示：
（1）若第 2 小组各成员得分依次为"0，4，12，1，5，9，3，9"，则该小组的成绩是______。 （2）请在划线处填入合适的代码。
n = 6
m = 8
a = [] # 按组别顺序存放所有成员得分，代码略
ans = [0] * n
def group_score(w):
c = [0] * (m + 1)
for i in range(w * m, (w + 1) * m):
k = a[i]
if k > m:
___①___
c[k] += 1
k = m
while c[k] < k and k > 0:
k -= 1
___②___
return k
maxg = -1
p = -1
for i in range(n):
g = group_score(i)
if g > maxg:
maxg = g
p = 0
___③___
elif g == maxg:
p += 1
ans[p] = i + 1
for i in range(p + 1):
print(f"第{ans[i]}组，成绩：{maxg}")
📝 解析
（1）4。第2组得分排序：12,9,9,5,4,3,1,0。当k=4时，前4人(12,9,9,5)均不低于4，其余(4,3,1,0)均不超过4，成绩为4。
（2）① k = m：超过m的得分压到m档统计。
② c[k] += c[k+1]：把"至少k+1分的人数"累加到"至少k分的人数"中。
③ ans[p] = i + 1：记录当前成绩最高的小组编号。
核心思路：计数排序统计各分数段人数，从高到低累加，找到满足"前k人不低于k"的最大k值。
📌 考点：计数思想的高级应用——不仅统计频次，还通过累加（c[k] += c[k+1]）来回答"至少k分的有多少人"。
◆ ◆ ◆
【2024年01月·第15题】浙江选考压轴题
来源：202401-Q15-算法综合
15.某项活动有 个单位（编号 到 ）参加，需要将员工分成若干个小组，每个小组的人数上限为 ，小组编号按新建次序从 开始编号。分组时，首先按单位编号次序依次在各单位内部分组，每 人分配到一个新建小组中，不足 人的剩余员工暂不分配；然后按剩余员工人数由大到小的顺序，依次为各单位剩余员工分配小组。
若某单位剩余员工人数为 ，则分配方法为：在已建的小组中查找空位数（该小组还可容纳的人数）大于或等于 的小组，如果找到的小组有多个，则选择空位数最少的小组，将此 人分配到该小组中；如果没有找到，则新建一个小组，将此 人分配到该小组中。
设 为 ， 为 ，各单位员工人数及单位内部的分组过程如第 15 题图 a 所示，完成第 15 题图 b 的问题
编写程序：给定各单位编号及员工人数，根据上述方法进行分组处理，按单位编号次序输出各单位所分配的分组编号。请回答下列问题：
（1）由题意可知，若仅将第 15 题图 a 中 1 号单位的员工人数修改为 25，然后对图中 5 个单位重新分组，则 1 号单位所分配的分组编号为____。
（2）定义如下 bubble_sort(lst) 函数，参数 lst 的每个元素由单位编号和剩余员工人数 2 个数据项构成。函数的功能是根据每个单位的剩余员工人数，对 lst 进行降序排序。
def bubble_sort(lst):
n = len(lst)
for i in range(0, n-1):
#------------------------------#
for j in range(n-1, i, -1):
if lst[j-1][1] < lst[j][1]:
tmp = lst[j]
lst[j] = lst[j-1]
lst[j-1] = tmp
if lst[i][1] == 0:
break
#------------------------------#
return
调用该函数，若 lst 为 [[1, 0], [2, 0], [3, 18], [4, 0], [5, 19], [6, 17]]，请回答 1 和 2 两个问题。
A. lst[0][1] 数值最小 B. lst[0][1] 数值最大 C. lst[5][1] 数值最小 D. lst[5][1] 数值最大
虚线框中的程序段执行的次数为 ______。
（3）实现分组功能的部分 Python 程序如下，程序中用到的列表函数与方法如第 15 题图 c 所示，请在程序中划线处填入合适的代码。
def group(data, m):
n = len(data)
a = []
for i in range(n + 1):
a.append([]) #a[i]初始化为空列表，存放编号为i的单位所分配的分组编号
gnum = 0
for i in range(n): #各单位内部分组
while data[i][1] >= m:
gnum += 1
k = data[i][0]
a[k].append(gnum)
____①___
bubble_sort(data)
b = []
for i in range(m):
b.append([])
i = 0
while i < n and data[i][1] != 0: # 对剩余员工分组
____②___
while j < m and len(b[j]) == 0:
j += 1
if j < m:
v = b[j].pop()
else:
gnum += 1
v = gnum
a[data[i][0]].append(v)
____③____
i += 1
#输出各单位的分组编号，代码略
'''
读取小组人数上限存入m，读取1至n号单位的数据，依次存入列表data的data[0]至data[n-1]中。data[i]包含2个数据项，data[i][1]分别存放单位编号及员工人数，代码略
'''
group(data, m)
函数与方法功能
w.append(x)在列表 w 末尾添加元素 x
x = w.pop()在列表 w 末尾元素赋值给 x，并将其从 w 中删除
📝 解析
答案：（1）1，8 （2）① B ② 4 （3）① data[i][1] -= m ② j = data[i] ③ b[j - data[i][1]].append(v)
详细文字解析及图解参考相关真题解析材料：
【真题解析】2024年01月浙江技术选考信息技术第15题超详细解析
【真题图解】2024年01月浙江技术选考信息技术第15题图示解析
◆ ◆ ◆
03 解题要点
值域决定可行性
计数排序的前提是值域已知且不太大——成绩0-100、字母A-Z是典型场景。
计数数组下标 = 值本身
这是计数排序最核心的思想——用数组位置表示数据值，用元素值表示出现次数。建议把这类赋予下标特殊含义的思想统一为：属性下标化（或状态索引化）。它把原本需要通过遍历、比较才能找到的"业务属性"，直接变成了数组的"物理地址"。
累加方向决定名次
从高到低累加 → 名次从前往后排；从低到高累加 → 名次从后往前排。
计数不比较
计数排序的 O(n+k) 远快于比较排序的 O(n²)，但空间换时间——需要额外的计数数组。
如果这篇文章对你有帮助，欢迎 点赞、分享、推荐。
