Olverae Assets

1 先看：不比较，只"数数"就能排好

前面学的排序都靠两两比较。但如果数据是范围很小的整数（比如成绩 0~5 分），其实根本不用比——只要数一数"每个值出现了几次"，再按从小到大把它们写回去就排好了。点「下一步」：先逐个统计计数，再按桶顺序把值倒出来。

输入数组

计数桶 count[值] —— 桶下标 = 值，桶里 = 出现次数

输出（已排序）

点「下一步」：逐个读输入元素，给它对应的计数桶 +1。

计数排序：对小范围整数，先统计每个值出现的次数（计数桶），再按值从小到大把它们依次输出——全程不做元素间比较。

设元素个数为 n、值域大小为 k（最大值+1）。计数是 O(n)，输出是 O(n+k)，总共 O(n+k)。当 k 与 n 同量级时，它比 O(n log n) 的比较排序更快。

比较排序有 O(n log n) 的理论下界，因为它只能靠"比大小"获取信息。计数排序换了条路：直接用值本身当数组下标。

计数：O(n)

扫一遍输入，每个元素 count[值]++。一次遍历就拿到了完整的频次分布。

输出：O(n+k)

从值 0 到 k-1 依次看每个桶，桶里有几个就写几个该值。遍历 k 个桶、写出 n 个元素。

没有比较 = 绕过下界

O(n log n) 下界只约束基于比较的排序。计数排序不比较，所以不受它限制，能做到线性。

想做成稳定排序（保持相等元素原顺序，且能携带"附带数据"如学生记录）：把 count 改成前缀和得到每个值的起始落点，再从后往前扫输入放置即可。本演示用的是最朴素的"按桶倒出"版本，足以说明核心思想。

计数排序很快，但有明确的前提条件。

✅ 适合

键是小范围非负整数（或能映射成小范围整数），且 k 不远大于 n。如年龄、成绩、字节值 0~255。

✅ 稳定可携带数据

前缀和版本是稳定的，可作为基数排序（radix sort）按位排序的子过程。

⚠️ 空间 O(k)

要开一个大小为 k 的计数数组。值域大时很费内存。

别用的情况：值域 k 远大于 n（例如 8 个数但取值可达十亿）——计数数组会爆炸且大量为空，得不偿失。也不能直接排浮点数、任意字符串等没有"小整数键"的数据。这类情况回到 O(n log n) 的比较排序（快排/归并/堆排序）。

三道题，点选项即时判对错。

去做例题：把数组升序排好（小范围整数可用计数排序实现）

去做例题

一句话带走：

计数排序 = 不比较，先数每个值出现几次，再按值从小到大倒出来。时间 O(n+k)、空间 O(k)，靠"用值当下标"绕过比较排序的 O(n log n) 下界。前缀和版本稳定，是基数排序的基石。只适用于小范围整数键；值域 k 远大于 n 时不要用。