计数排序与基数排序线性时间算法

可视化演示

计数排序和基数排序是非比较排序算法，可在特定条件下实现线性时间排序。本文讲解计数排序的计数数组与累加映射、基数... 切换模式查看不同维度。

非比较排序

小明整理书架时，发现如果采用快速排序，每本书都要和其他书比较编号。假设有 100 本书，比较次数大概是 100×log100，也就是六百多次。他郁闷地想：难道就不能少比几次吗？仔细想想，比较排序每次比较只能排除一半的可能性，就像猜数字游戏每次问“大还是小”只能得到两个回答，所以至少需要 log₂(100!) 次比较，这就是比较树的高度。

这个“至少需要多少次比较”的结论，就是比较排序的下界。它告诉我们：任何基于两两比较的排序算法，在最坏情况下都不可能少于 n log n 次比较。于是小明意识到，如果真想突破这个限制，就必须彻底抛弃“比较”这个动作。非比较排序利用数据本身的数值分布规律，直接计算每个元素应该去的位置，从而绕开了比较下界。

$$\displaystyle T(n) \geq \Omega(n \log n)$$

1. T(n) 含义：整个式子表示排序 n 个元素所需的时间（最少比较次数）。

$$T(n)$$

2. Ω 下界符号：Ω 表示“渐近下界”，意思是时间至少是这么多，不可能更少。

$$\Omega$$

3. n log n 来源：n 个元素有 n! 种排列，每次比较最多区分两种结果，所以比较次数至少是 log₂(n!)，约等于 n log n。

$$n \log n$$

小明想通了：如果想更快，就要用“编号本身的信息”，而不是问“谁大谁小”。他决定用计数的方法，让每本书直接跳到自己的位置。非比较排序从此改变了他的整理方式。

计数排序

小明开始行动：他发现编号只有 0 到 9 十种，于是先做一张“书名统计表”。他快速扫过一百本书，记录编号 0 的书有 3 本，编号 1 的有 2 本……这张表就是计数排序的计数数组。有了它，小明不必比较任何两本书，就可以知道每种编号的书有多少本。

计数排序的思路是：假设待排序数组 A 的长度为 n，所有元素的值都在 0 到 k-1 之间。我们创建一个长度为 k 的计数数组 C，初值全为 0。然后遍历 A，每遇到一个值 v，就给 C[v] 加一。这样 C[v] 就记录了值 v 出现的次数。这一步的时间是 O(n)，完全不需要比较。

$$C[v] = \sum_{i=0}^{n-1} [A[i] = v]$$

1. C[v] 含义：计数数组中索引 v 对应的值，表示 v 出现的个数。

$$C[v]$$

2. 累加求和：从第 0 个元素遍历到第 n-1 个元素，把所有满足 A[i]=v 的 i 都计入。

$$\sum_{i=0}^{n-1}$$

3. 艾弗森括号：[条件] 在条件成立时等于 1，否则等于 0，用于把真/假转化为计数。

$$[A[i] = v]$$

小明看着计数表，心里有了谱——但仅仅知道每种编号有多少本还不够，还得知道每种编号应该放在哪个位置。计数排序的下一步，就是把这些次数变成位置。这就像老师拿到各年级学生人数后，要先算每个年级从第几个座位开始坐。

累加映射

小明现在有了计数数组 C，知道编号 0 有 3 本，编号 1 有 2 本，编号 2 有 2 本，编号 3 有 1 本。他想：编号 0 的书应该占据 0、1、2 号位置，编号 1 的书应该占据 3、4 号位置……只要把前面的本数累加起来，就能知道每种编号的最后一本书该放在哪里。这个“累加”操作，就是计数排序的关键。

具体来说，我们修改计数数组 C，让 C[i] 变成“小于等于 i 的值的总个数”。数学上就是前缀和：从 1 到 k-1，依次执行 C[i] = C[i] + C[i-1]。这样，对于任意值 v，它的元素在输出数组中的位置范围就确定了，最后一个 v 应该放在 C[v]-1 的位置上。

$$\displaystyle C[i] = \sum_{j=0}^{i} count(j)$$

1. 前缀累加：从第一个元素开始，把前一个累加值加到当前值上，形成累计分布。

$$C[i] = C[i] + C[i-1]$$

2. 总和表示：C[i] 的值等于 j 从 0 到 i 的所有 count(j) 之和，代表值 ≤ i 的元素个数。

$$\sum_{j=0}^{i} count(j)$$

3. 位置确定：值为 v 的元素应放在 C[v]-1 的位置，因为 C[v] 是包含 v 在内的总数。

$$\text{pos} = C[v] - 1$$

小明最喜欢的技巧是：从原始数组的最后一个元素开始倒着处理，每放好一个元素，就让对应的 C[v] 减 1。这样相同编号的书仍然保持原来的相对顺序，也就是排序是稳定的。累加映射不仅告诉小明位置，还保证了稳定性，为后面基数排序埋下了伏笔。

基数排序

书架上的编号很快变成了两位数，从 00 到 99。小明发现计数排序的 k 变成了 100，数组一下子变大很多。于是他换了一种思路：不要直接对整体排序，而是先按个位数字排序，再按十位数字排序。因为每位数字都只有 0 到 9 十种，用计数排序处理每一位非常轻松。

这就是基数排序：把整数按位拆分成多个关键字，然后从低位到高位依次做稳定排序。每轮排序只关注一个位，假设这一位的取值范围是 0 到 k-1，就用计数排序处理这一位。由于每轮都是稳定排序，低位排好后的相对顺序会在高位排序中被保留，最终得到全局有序。如果是 d 位数字，总共要排序 d 轮。

$$\displaystyle T(n) = O(d \cdot (n + k))$$

1. d 轮循环：每一轮处理一位数字，共 d 轮，所以时间是 d 乘以每轮时间。

$$d$$

2. 每轮计数排序：每轮对 n 个元素按位计数，范围是 k，耗时 O(n+k)。

$$n + k$$

3. 乘法整体：总复杂度就是轮数乘以每轮复杂度。

$$O(d \cdot (n + k))$$

小明用基数排序对付两位数编号，每轮只需额外用一个 10 格的小表，比直接开 100 格的计数表省多了。他体会到：把大任务拆成多次小范围排序，是一种更灵活的策略。

LSD与MSD

小明在整理三位数编号时，尝试了两种顺序。第一种从个位开始，叫 LSD（Least Significant Digit，低位优先）；第二种从百位开始，叫 MSD（Most Significant Digit，高位优先）。他发现 LSD 需要完整跑完所有位，而 MSD 每处理一位就会把数据划分成多个子组，再对每个子组递归处理更低位。

LSD 策略好理解：只要每一轮按位使用稳定排序，低位顺序不会被打乱，跑完所有位自然有序。MSD 则更符合人类直觉：先看最高位分类，各个类内部的顺序再用次高位决定。MSD 适合字符串等变长数据，因为可以提前结束，但递归处理子组会带来额外开销，实现也复杂一些。

$$\displaystyle \text{LSD}: \text{sort by } d_i \text{ from rightmost to leftmost}$$

$$\displaystyle \text{MSD}: \text{sort by } d_i \text{ from leftmost to rightmost, recursively}$$

1. LSD 过程：从最右边（最低位）开始逐位向左排序，每轮用稳定计数排序。

$$\text{rightmost} \to \text{leftmost}$$

2. MSD 过程：从最左边（最高位）开始，先按高位分成若干组，再对每组递归排低位。

$$\text{leftmost} \to \text{rightmost, recursive}$$

3. 稳定性前提：无论哪种策略，每轮排序必须是稳定的，否则之前位数排好的顺序会被破坏。

$$\text{stable sort required}$$

小明通常选 LSD，因为实现简单、性能稳定；MSD 则像给书按大类分架，适合字符串或键长不一的场景。理解了这两种策略，他面对任何“可拆位的键”都能选择最顺手的方案。

桶排序

有时候编号没有明确的位数，例如书的价格从 1 元到 100 元不等。小明想出一个新招：把 100 元的价格范围划分成 10 个区间，比如 0-10 元一个桶，10-20 元一个桶……然后把每本书按价格丢进对应的桶。每个桶里的书数量很少，用插入排序或快速排序非常快。最后按桶的顺序倒出来，整个书架就整齐了。

桶排序的前提是数据在范围内分布比较均匀。如果所有书都挤进同一个桶，那桶内排序又会退化成 O(n log n)。因此桶排序的期望时间复杂度为 O(n)，但最坏情况会退化。它非常像公司里先按部门分文件，每个部门内部再按日期整理。

$$\displaystyle T(n) = O(n) \quad \text{当数据均匀分布时}$$

1. 均匀分布：每个桶大约获得 n/m 个元素，这是期望时间的前提。

$$\frac{n}{m}$$

2. 桶内排序：每个桶内排序时间约为 O((n/m) log(n/m))，m 个桶合计近似 O(n)。

$$m \cdot O\!\left(\frac{n}{m} \log \frac{n}{m}\right)$$

3. 线性结论：当 m 接近 n 时，每个桶元素为常数，整体时间即为 O(n)。

$$T(n) = O(n)$$

小明把桶排序看作“先分类再细化”的思维。他提醒自己：如果数据分布极不均匀，例如 99% 的书都掉进一个桶，桶排序就会失去线性优势。所以使用桶排序前，一定要观察数据的分布情况。

复杂度分析

小明整理完所有排序方法，坐下来画了一张对比表。计数排序时间复杂度是 O(n+k)，这里 n 是书的数量，k 是编号范围；空间复杂度是 O(k)。当 k 相对于 n 很小时，计数排序几乎就是线性的，但如果 k 很大，比如编号范围是上亿，计数数组就会浪费大量内存。

基数排序的时间是 O(d(n+k))，其中 d 是位数。如果 d 是常数，它也是线性的，而且 k 通常很小（比如十进制每位 k=10）。桶排序在均匀分布下是 O(n)，但最坏情况会变成 O(n log n)。相比快速排序的 O(n log n)，这些方法在特定条件下拥有明显优势，但它们都对数据形态有额外要求。

$$\displaystyle T_{\text{count}} = O(n + k), \quad S_{\text{count}} = O(k)$$

$$\displaystyle T_{\text{radix}} = O(d \cdot (n + k)), \quad S_{\text{radix}} = O(n + k)$$

1. 计数排序时间：遍历一遍数组统计次数 O(n)，加上初始化 k 个计数器 O(k)，总和为 O(n+k)。

$$O(n+k)$$

2. 计数排序空间：需要一个长度为 k 的计数数组，因此额外空间为 O(k)。

$$O(k)$$

3. 基数排序时间：每位执行一次计数排序，共 d 轮，所以是 d 乘以 O(n+k)。

$$O(d \cdot (n+k))$$

小明在对比中发现，非比较排序并非万能。它们要么空间开销大，要么对数据分布有苛刻要求。但一旦条件满足，它们能把原来的 O(n log n) 压缩成 O(n)，就像给算法装上了涡轮增压器。

应用限制

小明的书架越管越大，遇到了一些奇怪的需求。他注意到，如果一本书的编号范围极大（比如 ISBN 的 13 位数字），直接用计数排序需要开一个巨大数组，显然不现实。这时他改用基数排序，把 13 位拆成 13 轮，每轮只需 10 个计数器，问题迎刃而解。

不过，非比较排序也不是银弹。计数排序只适合非负整数且范围受限的数据；基数排序要求键可以拆分成独立的位，而且每轮排序必须是稳定的；桶排序则强烈依赖数据的均匀分布。在实际的 AI 工程和大数据处理中，这些算法常用于构建索引、对 ID 排序、处理定长字符串等场景，而面对浮点数、复杂对象时，通常还是会回到比较排序。

$$\displaystyle k \gg n \;\Rightarrow\; O(n+k) \approx O(k)$$

1. k 远大于 n：如果编号范围比书籍数量大得多，计数数组的大部分空间都被浪费。

$$k \gg n$$

2. 时间复杂度退化：O(n+k) 中 k 占主导，近似等于 O(k)，这通常大于 O(n log n)。

$$O(n+k) \approx O(k)$$

3. 空间代价：计数数组长度 k 可能超出内存限制，导致算法不可行。

$$S(n) = O(k)$$

小明总结了经验：选择排序算法前，先问三个问题——数据的值域大不大？键能不能拆位？分布是否均匀？只要有一项答不好，就谨慎使用非比较排序。他的整理工作从此又快又稳，这正是指南针式的排序选型逻辑。

AI 应用场景

Python 演示

def counting_sort(arr, exp):    n = len(arr)    output = [0] * n    count = [0] * 10    for i in range(n):        idx = (arr[i] // exp) % 10        count[idx] += 1    for i in range(1, 10):        count[i] += count[i - 1]    for i in range(n - 1, -1, -1):        idx = (arr[i] // exp) % 10        output[count[idx] - 1] = arr[i]        count[idx] -= 1    for i in range(n):        arr[i] = output[i] def radix_sort(arr):    max_val = max(arr)    exp = 1    while max_val // exp > 0:        counting_sort(arr, exp)        exp *= 10    return arr if __name__ == "__main__":    data = [170, 45, 75, 90, 802, 24, 2, 66]    print("原始数据:", data)    sorted_data = radix_sort(data)    print("排序结果:", sorted_data)

1. def counting_sort(arr, exp):定义按位计数排序函数，exp 决定当前处理哪一位。
2. idx = (arr[i] // exp) % 10提取数字在当前位（个位、十位…）上的值作为桶索引。
3. count = [0] * 10因为每一位只有 0-9 十种可能，所以计数器固定长度为 10。
4. for i in range(1, 10): count[i] += count[i - 1]前缀累加，把频次转化为位置信息。
5. for i in range(n - 1, -1, -1):倒序遍历原始数组，保证稳定性。
6. output[count[idx] - 1] = arr[i]根据累加位置把元素放入输出数组。
7. while max_val // exp > 0:当 exp 超过最大值的位数时，所有位都处理完毕。
8. exp *= 10从个位移到十位、百位，逐步推进。

常见误区

面试题