计数排序详解：原理、代码与时间复杂度

计数排序解决什么问题

任何只比较元素对的排序，最坏情况下都需要 Ω(n log n) 次比较。计数排序完全不比较，从而突破了这个限制：它把键本身用作数组下标。当键是小整数时，例如 0 到 100 的考试分数、年龄、0 到 255 的字节或星级评分，它比任何比较排序都快。

代价是内存与键的取值范围成正比。如果要对少量分布在整个 64 位范围内的整数排序，需要的计数数组会大到不可能。

思路与示例

对 [4, 2, 2, 8, 3, 3, 1] 排序，其值落在 0 到 8 的范围内（k = 9）。

1. 统计每个值：count[v] 是 v 出现的次数。
2. 前缀和：把每个计数换成小于或等于该值的元素个数。此时 count[v] 就是 v 应放位置的最后一格再往后一位。
3. 放置元素：从右向左遍历输入；对每个值 v，先把 count[v] 减 1，再把 v 写到该位置。从右向左遍历能让相等的值保持原有顺序。

于是 1 放到下标 0，两个 2 放到下标 1 和 2，两个 3 放到下标 3 和 4，4 放到下标 5，8 放到下标 6。结果：[1, 2, 2, 3, 3, 4, 8]。

Python 实现

这个稳定的版本可以按 0 到 k - 1 之间的整数键，对任意对象排序。

def counting_sort(items, k, key=lambda x: x):
    """Stable sort of items by integer key in range(k)."""
    count = [0] * k
    for x in items:
        count[key(x)] += 1
    for v in range(1, k):                # prefix sums
        count[v] += count[v - 1]
    out = [None] * len(items)
    for x in reversed(items):            # right to left: stable
        count[key(x)] -= 1
        out[count[key(x)]] = x
    return out

print(counting_sort([4, 2, 2, 8, 3, 3, 1], k=9))
# [1, 2, 2, 3, 3, 4, 8]
people = [("Ana", 3), ("Bo", 1), ("Cy", 3), ("Di", 2)]
print(counting_sort(people, k=4, key=lambda p: p[1]))
# [('Bo', 1), ('Di', 2), ('Ana', 3), ('Cy', 3)]

如果只对普通整数排序，又不要求稳定，可以用更简单的版本，根据计数重建输出。这个变体还通过减去最小值进行平移，来处理负数：

def counting_sort_ints(nums):
    if not nums:
        return []
    lo, hi = min(nums), max(nums)
    count = [0] * (hi - lo + 1)
    for x in nums:
        count[x - lo] += 1
    out = []
    for offset, c in enumerate(count):
        out.extend([offset + lo] * c)
    return out

print(counting_sort_ints([3, -1, 2, -1, 0]))   # [-1, -1, 0, 2, 3]

时间与空间复杂度

当 k 是 O(n) 时，计数排序是线性的。如果 k 远大于 n，例如在 0 到 10⁹ 的范围内只有 1,000 个值，计数数组就会成为主要开销，此时比较排序或基数排序更好。

计数排序与其他排序算法的比较

这里 k 是键范围的大小，d 是位数，b 是基数排序所用的基数。当用前缀和并从右向左放置元素时，计数排序是稳定的。简单的由计数重建的版本，对普通整数能得到同样的结果，但无法让其他数据跟随键一起移动。

变体与常见错误

• 基数排序对每一位运行一次稳定的计数排序，把这一思路推广到大整数和定长字符串。
• 桶排序按范围把值分散到若干桶中，再对每个桶排序；当值均匀分布时很快。
• 只计数不排序：很多时候你只需要计数本身，例如绘制直方图或求众数。collections.Counter 可以直接做到。

何时使用计数排序

当键是整数，且其范围相对于元素个数较小时使用：成绩、年龄、月份中的日期、字节、0 到 255 的颜色通道值，或小的枚举值。它也是基数排序和后缀数组构造算法的内部步骤。面试中，它出现在颜色分类（值为 0、1、2）、按频率排序、H 指数等题目中，也出现在「如何突破比较排序 O(n log n) 下界」这个经典问题中。