ex12 计数排序

要学习的知识点

计数排序及值域限制
列表下标作为计数槽
enumerate() 遍历下标和值
extend() 批量追加
频次统计

题目

练习 12：对 0 到 100 范围内的整数进行计数排序并统计频次。

输入：第一行 n，第二行 n 个整数。

参考程序：ex12.py；空白练习：lx12.py。

完整代码

以下内容与 ex12.py 一致，可对照右侧讲解阅读。

"""练习 12：对 0 到 100 范围内的整数进行计数排序并统计频次。
输入：第一行 n，第二行 n 个整数。

学习说明：
- 计数排序适合整数取值范围较小且已知的情况；counts[i] 记录数字 i 出现的次数。
- 遍历输入时先检查数值范围，再把对应计数加一。
- 从 0 到 100 顺序查看计数，把每个数重复 count 次，便得到升序列表。
- 最后一段只打印出现次数不为 0 的数字。
"""
n = int(input())
values = list(map(int, input().split()))[:n]
counts = [0] * 101

# 统计每个数字出现的次数；范围检查防止下标超出计数表。
for value in values:
    if not 0 <= value <= 100:
        raise ValueError("所有输入值必须在 0 到 100 之间")
    counts[value] += 1

sorted_values = []
# 按数值从小到大展开频次，完成排序。
for value, count in enumerate(counts):
    sorted_values.extend([value] * count)

print("sorted:", *sorted_values)
print("frequencies:")
for value, count in enumerate(counts):
    if count:
        print(value, count)

进阶写法

这版与初学版解决同一道题，使用更精炼的语法或标准库工具。

进阶源码：ex12_adv.py

"""练习 12 进阶版：用列表解析按计数表重建有序结果。"""
n = int(input())
values = list(map(int, input().split()))[:n]
counts = [0] * 101

for value in values:
    if not 0 <= value <= 100:
        raise ValueError("所有输入值必须在 0 到 100 之间")
    counts[value] += 1

sorted_values = [value for value, count in enumerate(counts) for _ in range(count)]
print("sorted:", *sorted_values)
print("frequencies:")
for value, count in enumerate(counts):
    if count:
        print(value, count)

嵌套列表解析按数值从小到大遍历计数表，并将每个数重复 count 次，形成排序结果；值域检查仍在计数前完成。

运行结果

示例输入：

6
4 1 4 0 2 1

程序输出：

sorted: 0 1 1 2 4 4
frequencies:
0 1
1 2
2 1
4 2

逐个认识函数

下表根据程序中实际调用的函数和方法整理；自定义函数的实现与算法细节见后续说明。

函数形式	功能与返回值	注意事项
`ValueError(message)`	内置异常类型，用来表示参数值不符合要求。	raise ValueError(...) 会立即抛错并停止当前程序流程。
`enumerate(iterable, start=0)`	遍历时同时得到下标和元素。	本题用于同时取得计数表的数值下标与频次。
`input(prompt='')`	读取一行文本，返回 str；若提供 prompt 会先显示提示。	返回值默认是字符串，计算前通常要做类型转换。
`str.split(sep=None)`	按分隔符拆分字符串，返回字符串列表。	默认按连续空白拆分并忽略首尾空白。
`int(value, base=10)`	把整数文本或数值转换为整数。	int('3.5') 不合法；按指定进制解析时可传 base。
`list(iterable=())`	从可迭代对象创建列表。	列表有顺序、可修改，允许重复元素。
`map(function, iterable)`	逐个应用函数，返回惰性迭代器。	常与 list() 一起使用以立即取得结果。
`print(*objects, sep=' ', end='\n')`	把对象转换为文本显示；返回 None。	默认空格分隔并在末尾换行。
`list.extend(iterable)`	把可迭代对象中的各项逐个追加；返回 None。	与 append(iterable) 不同，extend 不会把整个对象作为单个元素。

为什么这样能排序

普通排序关心“两个数谁大”；计数排序换一种想法：每种数分别出现几次？数完以后从最小的值开始，把它按次数写出来。由于按数值从小到大扫描，结果天然有序。

创建 101 个计数位置，对应 0、1、...、100。
每读到 value，就给 counts[value] 加一。
从下标 0 扫到 100，把下标重复 count 次追加到排序结果。
再打印非零频次，作为统计信息。

函数与方法说明

函数 / 方法	参数和返回值	本题中的使用方式
`int(input())`	读入并转换为整数。	读取元素数量 n。
`input().split()`	input 返回 str；split 默认按空白分割，返回字符串列表。	把一行整数切成一项项的文本。
`map(int, iterable)`	逐项调用 int，返回 map 迭代器。	再用 list 生成可切片的整数列表。
`[0] * 101`	列表乘整数会重复列表内容。	得到 101 个独立整数槽位；整数不可变，所以槽位能各自赋值。
`enumerate(iterable)`	返回依次包含“下标、元素”的迭代器。	遍历计数表时得到 value 下标和 count 计数。
`list.extend(iterable)`	把 iterable 的每个元素追加到列表；原地修改，返回 None。	`extend([value] * count)` 一次加入 count 个 value。
`print(*values)`	解包序列作为多个输出参数。	输出数字时以空格分隔。

计数表示例

counts = [0] * 5       # 假设只允许 0 到 4
value = 2
counts[value] += 1     # 对应格子加一
# 如果数据为 [2, 0, 2]，计数表最终是 [1, 0, 2, 0, 0]

计数排序受值域大小影响。若输入值很大或跨度极宽（如 1 和十亿），就不适合建立从最小值到最大值的巨大计数表。它的空间大约与值域大小有关，而不是只与输入个数有关。

代码如何运行

先按左侧题目给出的格式输入数据；程序通过 input() 读取，并在需要时转换数据类型。
程序自上而下执行语句；遇到条件、循环或函数调用时，按照右侧算法说明更新变量和处理数据。
最后由 print() 输出计算结果。可将左侧示例输入与输出逐项对照。

先自己跟踪一组小数据，记录循环前后变量的值；这比只看最终答案更容易理解程序。

自己动手试一试

测试数值 0 和 100；将输入改成 -1 或 101，观察范围检查如何阻止错误下标。

先在 lx12.py 中独立完成，再运行参考程序比较结果。修改程序时一次只改一个条件或步骤。