计数排序（Counting Sort）

线性时间非比较排序

算法分类： 非比较排序 / 线性时间排序

核心思想： 通过统计元素频率确定每个元素在输出序列中的位置

适用条件： 整数排序，且已知元素取值范围较小

关键词： 计数排序, Counting Sort, 非比较排序, 线性时间, 前缀和, 频率统计

一、概述

计数排序（Counting Sort） 是一种非比较排序算法，它突破了比较排序 O(n log n) 的下界，在特定条件下可以达到 O(n + k) 的线性时间复杂度。计数排序的核心思想是将输入数据的值转化为键，存储在额外开辟的数组空间中，通过统计每个元素出现的次数来完成排序。

计数排序不是基于比较的排序算法，因此它不受 O(n log n) 理论下界的限制。当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n + k)。计数排序在数据范围 k 远小于数据规模 n 的情况下非常高效，常被用作基数排序（Radix Sort）的子过程。

计数排序的概念最早可以追溯到 1954 年，由 Harold H. Seward 在其博士论文中提出。尽管这一算法历史悠久，但在面向整数的海量数据排序场景中仍然广泛使用，尤其适合 年龄排序、成绩排名、频率统计 等应用场景。

核心思想：

频率统计： 扫描输入数组，统计每个数值出现的次数
前缀和（Prefix Sum）： 对计数数组进行累加，确定每个元素在输出数组中的位置
回填输出： 根据计数信息将元素放置到正确位置
稳定性保障： 反向遍历输入数组，保证相同值的相对顺序不变

二、算法原理

计数排序的原理可以分解为三个核心步骤。我们以数组 [4, 2, 2, 8, 3, 3, 1] 为例，其中所有元素都在 0 到 8 之间。

2.1 步骤一：确定范围并统计频率

遍历输入数组，找出最大值和最小值，确定数值范围 range = max - min + 1。创建一个长度为 range 的计数数组 count[]，初始化为 0。再次遍历输入数组，对于每个元素 arr[i]，执行 count[arr[i] - min]++。

示例数组: [4, 2, 2, 8, 3, 3, 1]
范围: min=1, max=8, range=8

统计频率后 count[]:
索引(偏移): 0  1  2  3  4  5  6  7
对应值:    1  2  3  4  5  6  7  8
频率:     1  2  2  1  0  0  0  1

2.2 步骤二：计算前缀和（确定位置）

对计数数组进行顺序累加，使得 count[i] 存储的是"小于等于当前值的元素个数"。这一步至关重要，因为它直接确定了每个元素在输出数组中 应该存放的最后一个位置（第几个位置）。

计算前缀和后的 count[]:
索引(偏移): 0  1  2  3  4  5  6  7
前缀和:     1  3  5  6  6  6  6  7

解释:
  - 值 1 有 1 个，放在位置 0 (第1个)
  - 值 2 有 2 个，放在位置 1~2 (第2~3个)
  - 值 3 有 2 个，放在位置 3~4 (第4~5个)
  - 值 4 有 1 个，放在位置 5 (第6个)
  - 值 8 有 1 个，放在位置 6 (第7个)

2.3 步骤三：构建输出数组

创建一个与输入数组等长的输出数组 output[]。从后向前遍历输入数组（保证稳定性），对于每个元素 arr[i]：

查找前缀和数组获取位置：pos = count[arr[i] - min] - 1
将元素放入输出数组：output[pos] = arr[i]
将对应计数减 1：count[arr[i] - min]--

反向遍历过程:
原数组: [4, 2, 2, 8, 3, 3, 1]

i=6, val=1 -> count[0]=1, pos=0 -> output[0]=1, count[0]-- -> count[0]=0
i=5, val=3 -> count[2]=5, pos=4 -> output[4]=3, count[2]-- -> count[2]=4
i=4, val=3 -> count[2]=4, pos=3 -> output[3]=3, count[2]-- -> count[2]=3
i=3, val=8 -> count[7]=7, pos=6 -> output[6]=8, count[7]-- -> count[7]=6
i=2, val=2 -> count[1]=3, pos=2 -> output[2]=2, count[1]-- -> count[1]=2
i=1, val=2 -> count[1]=2, pos=1 -> output[1]=2, count[1]-- -> count[1]=1
i=0, val=4 -> count[3]=6, pos=5 -> output[5]=4, count[3]-- -> count[3]=5

最终 output[]: [1, 2, 2, 3, 3, 4, 8]

稳定性分析

计数排序的稳定性关键在于反向遍历输入数组并使用前缀和减一的策略。当我们从后向前遍历时，后出现的相同元素会被放置在更靠后的位置，从而保持了它们在原数组中的相对顺序。这是计数排序作为 稳定排序 的核心保证。

如果不要求稳定性，可以简单地根据频率统计直接展开填充，但标准实现中采用前缀和+反向遍历的方式确保了稳定性，使其可以作为基数排序的子过程。

三、算法实现

3.1 Python 实现

# -*- coding: utf-8 -*-
def counting_sort(arr):
    """
    计数排序（稳定版本）

    Args:
        arr: 待排序整数列表

    Returns:
        已排序的列表（升序）
    """
    if len(arr) == 0:
        return arr

    # 1. 确定数值范围
    min_val = min(arr)
    max_val = max(arr)
    range_size = max_val - min_val + 1

    # 2. 统计频率
    count = [0] * range_size
    for num in arr:
        count[num - min_val] += 1

    # 3. 计算前缀和（确定位置）
    for i in range(1, range_size):
        count[i] += count[i - 1]

    # 4. 反向遍历构建输出（保证稳定性）
    output = [0] * len(arr)
    for num in reversed(arr):
        idx = num - min_val
        count[idx] -= 1
        pos = count[idx]
        output[pos] = num

    return output

3.2 Java 实现

public class CountingSort {

    public static void countingSort(int[] arr) {
        if (arr == null || arr.length == 0) return;

        // 1. 确定范围
        int minVal = arr[0], maxVal = arr[0];
        for (int num : arr) {
            if (num < minVal) minVal = num;
            if (num > maxVal) maxVal = num;
        }
        int range = maxVal - minVal + 1;

        // 2. 统计频率
        int[] count = new int[range];
        for (int num : arr) {
            count[num - minVal]++;
        }

        // 3. 计算前缀和
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }

        // 4. 反向遍历构建输出
        int[] output = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int idx = arr[i] - minVal;
            count[idx]--;
            output[count[idx]] = arr[i];
        }

        // 5. 复制回原数组
        System.arraycopy(output, 0, arr, 0, arr.length);
    }
}

3.3 C/C++ 实现

// Counting Sort in C++ (稳定版本)
#include <vector>
#include <algorithm>
#include <cstring>

void counting_sort(std::vector<int>& arr) {
    if (arr.empty()) return;

    // 1. 确定范围
    auto [min_it, max_it] = std::minmax_element(arr.begin(), arr.end());
    int min_val = *min_it;
    int max_val = *max_it;
    int range = max_val - min_val + 1;

    // 2. 统计频率
    std::vector<int> count(range, 0);
    for (int num : arr) {
        count[num - min_val]++;
    }

    // 3. 计算前缀和
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }

    // 4. 反向遍历构建输出
    std::vector<int> output(arr.size());
    for (int i = arr.size() - 1; i >= 0; i--) {
        int idx = arr[i] - min_val;
        count[idx]--;
        output[count[idx]] = arr[i];
    }

    // 5. 复制回原数组
    arr = std::move(output);
}

3.4 简化版（不稳定，直接展开）

如果不要求稳定性，可以省略前缀和步骤，直接根据频率将元素依次填入输出数组。这种实现更简单，但会丢失稳定性。

def counting_sort_simple(arr):
    """计数排序简化版（不稳定，直接展开）"""
    if len(arr) == 0:
        return arr

    min_val, max_val = min(arr), max(arr)
    range_size = max_val - min_val + 1
    count = [0] * range_size

    for num in arr:
        count[num - min_val] += 1

    output = []
    for i in range(range_size):
        output.extend([min_val + i] * count[i])

    return output

四、复杂度分析

最好情况

O(n + k)

n = 数据规模
k = 数值范围

平均情况

O(n + k)

始终与分布无关

最坏情况

O(n + k)

与数据分布无关

空间复杂度

O(k)

需要计数数组和输出数组

4.1 时间复杂度详解

计数排序的时间复杂度由三个部分组成：

步骤	操作	时间复杂度
统计频率	遍历输入数组 n 次，对每个元素执行计数	O(n)
计算前缀和	遍历计数数组 k 次，执行累加	O(k)
构建输出	遍历输入数组 n 次，放置元素	O(n)
总计		O(n + k)

注意：虽然形式上计数排序是"线性时间"，但当 k 远大于 n 时（例如对范围 0~100000 中的 10 个元素排序），O(n + k) 退化为 O(k)，效率甚至不如 O(n log n) 的比较排序。因此计数排序只有在 k = O(n) 时才真正高效。

4.2 空间复杂度详解

计数排序需要额外的存储空间：

计数数组： 大小为 k，占 O(k) 空间
输出数组： 大小为 n，占 O(n) 空间
总计： O(n + k)。在稳定版本中输出数组不可省略；如果允许原地覆盖，可以优化为 O(k)，但会丧失稳定性

对于范围非常大的数据（如 k = 10^9），计数排序将消耗巨大的内存，不可行。

五、适用条件与优缺点

适用条件

整数类型： 元素必须可以映射为整数（包括字符、枚举等可以通过编码映射为整数的类型）
已知范围： 数据范围不能太大，最好 k = O(n)，否则空间开销过大
非负整数优先： 虽然可以处理负整数（通过偏移量映射），但处理负整数会增加复杂度
密集数据： 数据分布相对密集时效率更高，极端稀疏时浪费空间

优点

线性时间复杂度： O(n + k)，当 k 较小时显著优于比较排序
稳定排序： 标准实现可以保持相等元素的相对顺序
实现简单： 算法逻辑直观，代码易于编写和调试
适合基数排序子过程： 作为 LSD 基数排序的稳定子排序
适合特定场景： 年龄、成绩、优先级等有限范围的整数排序

缺点

适用范围窄： 仅适用于整数排序，无法直接用于浮点数或字符串
空间开销大： 需要 O(k) 的额外空间，k 很大时不可用
稀疏数据效率低： 仅对 3 个元素排序但数值范围是 0~10^6，浪费大量内存
非原地排序： 需要额外的输出数组，不是原地排序算法
无法对自定义对象直接排序： 除非可以将自定义对象映射到整数键

六、比较排序 vs 非比较排序

比较排序和非比较排序是排序算法的两大类别，它们在思想、性能和适用场景上有本质区别。

特性	比较排序	非比较排序（计数排序）
比较操作	依赖元素间的比较	不依赖比较，基于数值映射
下界	O(n log n)（理论下界）	O(n + k)（可突破 n log n）
数据要求	任意可比较类型	仅限整数或可映射类型
空间复杂度	O(1) 或 O(log n)	O(k)，与范围相关
稳定性	取决于具体实现	稳定（标准实现）
适用场景	通用排序需求	整数、有限范围内大量数据
典型算法	快速排序、归并排序、堆排序	计数排序、桶排序、基数排序

何时选择计数排序而非快速排序？

数据规模 n 很大（百万级）且数值范围 k 很小（如 k < 1000）时，计数排序远快于快速排序
需要稳定排序且数据为整数时，计数排序是更好的选择
数值范围 k 超过 n 时，计数排序的空间开销可能使其不再具有优势
通用场景下，快速排序 C++ STL 的 std::sort 仍是首选

七、计数排序在基数排序中的应用

计数排序最重要的应用之一是作为 基数排序（Radix Sort） 的子过程。基数排序通过按位（个位、十位、百位...）依次排序来实现整体排序，而每一轮的排序必须使用稳定排序才能保证正确性。

为什么计数排序适合基数排序？

稳定性： 基数排序要求每一轮子排序都是稳定的，计数排序符合要求
小范围特性： 基数排序的每一轮只针对 0~9（十进制）或 0~255（字节），k 恒为 10 或 256，非常小
线性效率： O(n + k) 在 k 很小的情况下几乎是 O(n)
实现简单： 计数排序的实现比桶排序等更简洁

计数排序作为基数排序子过程的实现

def counting_sort_for_radix(arr, exp):
    """
    基数排序中使用的计数排序子过程

    Args:
        arr: 待排序列表
        exp: 当前处理的位数（1=个位，10=十位，100=百位...）
    """
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # 只有 0-9 十个数字

    # 统计当前位数的频率
    for i in range(n):
        digit = (arr[i] // exp) % 10
        count[digit] += 1

    # 计算前缀和
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 反向遍历构建输出（稳定排序）
    for i in range(n - 1, -1, -1):
        digit = (arr[i] // exp) % 10
        count[digit] -= 1
        output[count[digit]] = arr[i]

    return output


def radix_sort(arr):
    """基数排序（LSD 最低位优先）"""
    if len(arr) == 0:
        return arr

    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        arr = counting_sort_for_radix(arr, exp)
        exp *= 10

    return arr


# 测试基数排序
data = [170, 45, 75, 90, 2, 24, 802, 66]
print(radix_sort(data))
# 输出: [2, 24, 45, 66, 75, 90, 170, 802]

基数排序的效率分析

当基数排序以 10 为基数（十进制位）时，对于最大值为 d 位的整数，需要执行 d 轮计数排序。每轮时间复杂度为 O(n + 10) = O(n)，因此总时间复杂度为 O(d * n)。由于 d 是常数（如 32 位整数 d=10），基数排序的整体时间复杂度也是 O(n)。这正是计数排序作为子过程的强大之处。

实际应用中，通常以 256 为基数（按字节排序），这样 d 最大为 4（32 位整数），每轮 k=256，效率更高。

八、代码示例与验证

8.1 完整测试用例

import random
import unittest


class TestCountingSort(unittest.TestCase):

    def test_empty(self):
        self.assertEqual(counting_sort([]), [])

    def test_single(self):
        self.assertEqual(counting_sort([5]), [5])

    def test_sorted(self):
        self.assertEqual(counting_sort([1, 2, 3, 4, 5]), [1, 2, 3, 4, 5])

    def test_reverse(self):
        self.assertEqual(counting_sort([5, 4, 3, 2, 1]), [1, 2, 3, 4, 5])

    def test_duplicates(self):
        self.assertEqual(counting_sort([4, 2, 2, 8, 3, 3, 1]),
                         [1, 2, 2, 3, 3, 4, 8])

    def test_negative(self):
        self.assertEqual(counting_sort([-5, -2, -8, 0, 3, -1]),
                         [-8, -5, -2, -1, 0, 3])

    def test_large_range_small_n(self):
        # 范围大但 n 小的情况——仍可用但效率不高
        arr = [100, 0, 999, 50, 777]
        self.assertEqual(counting_sort(arr), [0, 50, 100, 777, 999])

    def test_stability(self):
        # 测试稳定性——使用 (key, original_index) 元组
        arr = [(3, 0), (1, 1), (3, 2), (2, 3), (1, 4)]
        sorted_arr = counting_sort(arr, key=lambda x: x[0])
        # 值 1: 原始索引 1 应在 4 之前
        # 值 3: 原始索引 0 应在 2 之前
        self.assertTrue(
            sorted_arr.index((1, 1)) < sorted_arr.index((1, 4))
        )
        self.assertTrue(
            sorted_arr.index((3, 0)) < sorted_arr.index((3, 2))
        )


if __name__ == '__main__':
    unittest.main()

8.2 性能对比：计数排序 vs 快速排序

import time
import random


def benchmark():
    """对比计数排序和 Python 内置排序（Timsort）的性能"""

    # 场景1: n=100000, k=1000（密集小范围）
    n, k = 100000, 1000
    arr1 = [random.randint(0, k) for _ in range(n)]

    start = time.perf_counter()
    sorted1 = counting_sort(arr1)
    t_count = time.perf_counter() - start

    start = time.perf_counter()
    sorted2 = sorted(arr1)
    t_builtin = time.perf_counter() - start

    print(f"n={n}, k={k}")
    print(f"  计数排序: {t_count:.4f}s")
    print(f"  sorted(): {t_builtin:.4f}s")
    print(f"  加速比: {t_builtin/t_count:.2f}x")

    # 场景2: n=100000, k=100000（稀疏大范围）
    n, k = 100000, 100000
    arr2 = [random.randint(0, k) for _ in range(n)]

    start = time.perf_counter()
    sorted3 = counting_sort(arr2)
    t_count2 = time.perf_counter() - start

    start = time.perf_counter()
    sorted4 = sorted(arr2)
    t_builtin2 = time.perf_counter() - start

    print(f"n={n}, k={k}")
    print(f"  计数排序: {t_count2:.4f}s")
    print(f"  sorted(): {t_builtin2:.4f}s")
    print(f"  加速比: {t_builtin2/t_count2:.2f}x")


# 预期输出（实际速度因机器而异）:
# n=100000, k=1000
#   计数排序: 0.0123s
#   sorted(): 0.0456s
#   加速比: 3.71x
#
# n=100000, k=100000
#   计数排序: 0.0250s
#   sorted(): 0.0450s
#   加速比: 1.80x

8.3 常见使用场景举例

年龄排序： 对 10 万人的年龄排序，范围 0~150，k=151，极适合计数排序
考试成绩排名： 百分制成绩 0~100，范围固定，计数排序是经典选择
颜色排序： RGB 颜色按特定通道排序，通道值 0~255
字符频率统计： 对大规模文本中的 ASCII 字符按出现次数排序
优先级队列： 优先级值范围已知且有限的元素排序

九、拓展与进阶

9.1 处理负整数

计数排序天然支持负整数，只需通过 min_val 进行偏移映射即可。在统计频率时使用 arr[i] - min_val 作为索引，回填时使用 output[pos] = arr[i] 保持原始值。上面的 Python 和 Java 实现已经天然支持负整数。

9.2 对浮点数使用计数排序

计数排序无法直接处理浮点数，但可以通过以下方式间接应用：

映射为整数： 将浮点数乘以某个精度因子（如 100）后取整
结合桶排序： 先用桶排序分桶，桶内使用计数排序
按位处理： 利用 IEEE 754 浮点数的二进制表示按字节进行基数排序

# 对浮点数进行"伪计数排序"
def counting_sort_float(arr, precision=100):
    """
    对两位小数的浮点数进行计数排序
    将浮点数乘以 precision 映射为整数
    """
    scaled = [int(round(x * precision)) for x in arr]
    sorted_scaled = counting_sort(scaled)
    return [x / precision for x in sorted_scaled]


# 示例
scores = [85.5, 92.3, 78.0, 88.8, 92.3, 65.5]
print(counting_sort_float(scores))
# 输出: [65.5, 78.0, 85.5, 88.8, 92.3, 92.3]

9.3 计数排序的变种与优化

优化策略

稀疏计数： 对于范围大但数据稀疏的场景，使用哈希表代替数组存储计数，只对有出现的值分配空间
原地计数排序： 在某些特殊场景（如知道每个元素出现的次数），可以通过交换实现原地排序
并行计数排序： 利用多线程分别统计不同数据段的频率，最后合并计数数组
增量计数： 在对已排序数据增加少量新元素时，只需更新计数并重建输出，无需重新扫描

十、常见面试题

Q1: 计数排序的时间复杂度为什么是 O(n + k)？

计数排序没有比较操作，三次线性遍历（统计频率 O(n)、前缀和 O(k)、构建输出 O(n)）的总和为 O(n + k)。当 k = O(n) 时，退化为 O(n)，即真正的线性时间。

Q2: 为什么计数排序不适用于浮点数或字符串？

计数排序的核心是利用数组索引直接映射数值，这要求元素必须是整数（或可映射为整数）。浮点数无法直接作为数组索引；字符串虽然可以映射为整数（如 ASCII 码），但字符串的组合方式太多，会导致 k 极大，空间开销不可接受。

Q3: 计数排序是原地排序吗？

不是。标准的计数排序需要额外的输出数组来存放排序结果，空间复杂度为 O(n + k)，不是原地排序。可以通过一些技巧减少空间（如直接覆盖原数组），但通常会牺牲稳定性。

Q4: 当 k >> n 时，为什么计数排序效率低？

当数值范围 k 远大于数据规模 n 时，计数数组的大部分空间都是 0，造成巨大的空间浪费。同时 O(n + k) 退化为 O(k)，比 O(n log n) 还差。例如对 100 个 0~10^8 范围的整数排序，需要 10^8 大小的计数数组，而快速排序只需要 O(n log n) 时间和 O(1) 空间。

Q5: 如何保证计数排序的稳定性？

关键在于同时做到两条：①使用前缀和确定每个元素的"最后一个位置"；②从后向前反向遍历输入数组。反向遍历保证了后出现的相同元素被放在后面的位置，从而保持相对顺序。

十一、核心要点总结

核心思想： 计数排序通过统计每个值出现的频率，利用数组下标确定元素位置，避免了比较操作
时间复杂度： O(n + k)，当 k = O(n) 时为线性时间，突破比较排序的 O(n log n) 下界
空间复杂度： O(k) 额外空间（计数数组），稳定版本还需 O(n) 输出数组
适用条件： 整数类型、已知数据范围且范围适中、适合密集数据
稳定性： 标准实现（前缀和 + 反向遍历）是稳定排序
非比较排序： 不依赖于元素间的比较，因此不受比较排序理论下界的限制
典型应用： 基数排序的子过程、年龄排序、成绩排名、颜色排序等
局限性： 范围过大时空间开销大、仅支持整数或可映射类型、非原地排序
与快速排序对比： n 大 k 小时计数排序更快；k 大或排序自定义对象时快速排序更优
面试高频： 计数排序原理、稳定性实现、复杂度分析、与基数排序的关系是常见考点

十二、进一步思考

扩展学习方向：

桶排序（Bucket Sort）： 将数据分到有限数量的桶中，每个桶分别排序，是计数排序的泛化形式
基数排序（Radix Sort）： 按位排序的算法，计数排序是它最常用的子过程
线性时间排序家族： 计数排序、桶排序、基数排序共同构成了线性时间排序家族，适用于不同场景
分布式排序： 理解计数排序有助于理解 MapReduce 中的 Word Count 等分布式计算模式
排序算法的选择策略： 实际工程中（如 C++ std::sort 的内省排序）需要根据数据类型和规模综合选择

"计数排序的美妙之处在于它巧妙地利用了整数值本身作为索引，将排序问题转化为统计问题。当数据范围可控时，它用空间换时间，实现了线性复杂度的优雅突破。"