\title{计数排序（Counting Sort）算法}
\author{马浩琨}
\date{Aug 15, 2025}
\maketitle
排序算法作为计算机科学的核心基础之一，通常分为两大类别：比较排序与非比较排序。传统比较排序如快速排序、归并排序等，其时间复杂度下限为 $O(n \log{n})$，这一理论极限由决策树模型所证明。然而当我们面对特定数据类型时，非比较排序算法能够突破这一界限，实现线性时间复杂度。计数排序正是这样一种独特的算法，其在最优情况下时间复杂度可达 $O(n + k)$，其中 $k$ 表示数据范围大小。这种特性使其在整数排序、数据范围有限且稳定性要求高的场景中大放异彩，例如年龄统计、考试分数排名等实际应用场景。\par
\chapter{计数排序核心思想}
计数排序的核心原理在于利用"桶"思想直接统计元素出现频次，通过频次信息重建有序序列，完全规避了元素间的比较操作。该算法有两个关键前提：待排序数据必须为整数，且数据范围必须已知或可提前确定。当处理 \texttt{[4, 2, 0, 1, 3, 4, 1]} 这类数据时，算法会创建索引 \texttt{0} 到 \texttt{4} 的计数桶。稳定性在此算法中尤为重要，它能确保相同元素的原始相对顺序得以保留，这对多关键字排序等场景至关重要。\par
\chapter{算法步骤拆解}
我们以数组 \texttt{[4, 2, 0, 1, 3, 4, 1]} 为例（数据范围 \texttt{0\~{}4}），详细拆解计数排序的五个关键步骤。首先确定数据范围：最大值 \texttt{max=4}，最小值 \texttt{min=0}，则范围长度 \texttt{k=5}。接着初始化计数数组 \texttt{count[0..4]}，所有元素初始值为 \texttt{0}。第三步遍历原始数组统计频次，得到 \texttt{count = [1, 2, 1, 1, 2]}，表示数字 \texttt{0} 出现 \texttt{1} 次，数字 \texttt{1} 出现 \texttt{2} 次，依此类推。\par
第四步是计算累加频次：将计数数组转换为 \texttt{count = [1, 3, 4, 5, 7]}。这一步的数学意义在于 \texttt{count[i]} 表示值小于等于 \texttt{i} 的元素总数，为后续定位提供依据。最后进行反向填充：从原数组末尾向前遍历，根据 \texttt{count} 数组确定每个元素在输出数组中的位置。以最后一个元素 \texttt{1} 为例，查询 \texttt{count[1] = 3} 表示应放在索引 \texttt{2} 的位置（\texttt{3-1=2}），放置后 \texttt{count[1]} 减 \texttt{1} 更新为 \texttt{2}。反向遍历确保相同元素的顺序稳定不变。\par
\chapter{代码实现}
\begin{lstlisting}[language=python]
def counting_sort(arr):
    if len(arr) == 0:
        return arr
    
    # 确定数据范围（支持负数处理）
    max_val, min_val = max(arr), min(arr)
    k = max_val - min_val + 1
    
    # 初始化计数数组与输出数组
    count = [0] * k
    output = [0] * len(arr)
    
    # 统计每个元素的出现频次
    for num in arr:
        count[num - min_val] += 1  # 偏移量处理负数
    
    # 计算累加频次：count[i]表示≤ i 的元素总数
    for i in range(1, k):
        count[i] += count[i-1]
    
    # 反向填充保证稳定性
    for i in range(len(arr)-1, -1, -1):
        num = arr[i]
        # 计算元素在输出数组中的正确位置
        pos = count[num - min_val] - 1  # 转换为 0-based 索引
        output[pos] = num
        count[num - min_val] -= 1  # 更新计数器
    
    return output
\end{lstlisting}
在代码实现中，三个关键设计点值得关注。首先通过 \texttt{min\_{}val} 偏移量处理负数：当元素为负值时，\texttt{num - min\_{}val} 将其映射到非负索引区间。其次累加频次计算 \texttt{count[i] += count[i-1]} 将频次统计转换为位置信息，\texttt{count[i]} 表示所有小于等于 \texttt{i} 的元素总数。最重要的是反向填充机制：从数组末尾向前遍历，结合 \texttt{count} 数组确定位置后立即更新计数器，确保相同元素维持原始顺序。该实现时间复杂度为 $O(n + k)$，其中 $n$ 为元素数量，$k$ 为数据范围大小。\par
\chapter{算法特性深度分析}
计数排序的时间复杂度在最优、最差和平均情况下均为 $O(n + k)$，当 $k = O(n)$ 时达到线性复杂度。空间复杂度为 $O(n + k)$，包含输出数组的 $O(n)$ 和计数数组的 $O(k)$。稳定性是该算法的显著优势，通过反向填充严格保证相同元素的相对位置不变。与其他排序算法对比：快速排序虽平均 $O(n \log{n})$ 但不稳定；归并排序稳定但需要 $O(n)$ 额外空间；桶排序同样线性但要求数据均匀分布。计数排序在小范围整数排序场景中具有显著性能优势。\par
\chapter{优化技巧与边界处理}
面对不同数据特征，计数排序有多种优化策略。范围压缩技术通过 \texttt{min\_{}val} 偏移减少桶数量，如处理 \texttt{[-100, 100]} 范围时，使用偏移量只需 \texttt{201} 个桶而非 \texttt{201} 个。当桶数量过大（如 $k > 10^6$）时，应改用快速排序等算法避免空间浪费。特殊场景适配包括负数处理（代码已实现）和浮点数处理（缩放取整但损失精度）。边界情况需单独处理：空数组直接返回；单元素数组无需排序；全相同元素数组仍正常执行但计数数组仅单个桶有值。\par
\chapter{实际应用场景}
计数排序在现实中有诸多高效应用案例。成绩排名系统处理 \texttt{0\~{}100} 分数据时，只需 \texttt{101} 个桶即可线性完成百万级数据排序。人口年龄统计中，\texttt{0\~{}120} 岁范围同样适用。作为基数排序的子过程，它负责单一位的稳定排序。海量数据预处理时，可结合分治策略先用计数排序处理数据块。这些场景共同特点是数据范围有限且为整数。\par
\chapter{局限性讨论}
计数排序有两个主要局限：仅适用于整数排序，浮点数需近似处理会损失精度；数据范围过大时空间效率骤降，例如处理 \texttt{[1, 10\^{}9]} 范围需要十亿级桶。不适用场景包括字符串排序（应改用桶排序或基数排序）和范围未知的大整数集合。当 $k$ 远大于 $n$ 时，空间浪费严重，时间复杂度退化为 $O(k)$。\par
\chapter{扩展：计数排序的变种}
计数排序存在多个实用变种。前缀和优化版直接使用累加计数替代二次遍历，但实现更复杂。原地计数排序通过元素交换减少空间占用，但牺牲稳定性。在数据分析领域，计数数组本身可作为频率直方图，直接展示数据分布特征，无需完整排序过程。\par
计数排序在特定场景下展现出无可比拟的效率优势，其核心价值在于利用空间换时间策略实现线性排序。选择原则需权衡数据范围 $k$ 与数据量 $n$ 的关系：当 $k = O(n)$ 时是最佳选择。作为非比较排序的经典案例，它深刻揭示了算法设计中空间与时间的辩证关系，是理解桶排序、基数排序等高级算法的重要基础。\par
