计数排序：修订间差异

2025年5月12日 (一) 00:27的最新版本

概述[编辑 | 编辑源代码]

计数排序（Counting Sort）是一种稳定的线性时间排序算法，通过统计元素出现次数实现排序。其时间复杂度为 $O (n + k)$ （ $k$ 为数据范围），空间复杂度为 $O (n + k)$ ，适用于已知数据范围的整数排序。

核心思想[编辑 | 编辑源代码]

1. 统计频率：统计每个元素出现的次数
2. 计算位置：计算每个元素在输出数组中的最终位置
3. 反向填充：根据统计结果将元素放入正确位置

算法步骤[编辑 | 编辑源代码]

输入与输出[编辑 | 编辑源代码]

输入：包含 $n$ 个整数的数组arr，整数范围为 $[0, k]$
输出：排序后的数组

详细步骤[编辑 | 编辑源代码]

1. 初始化计数数组：创建长度为 $k + 1$ 的数组count，初始值为0 2. 统计元素频率：遍历输入数组，记录每个元素出现次数 3. 计算累积频次：将count数组转换为元素最后出现的位置索引 4. 反向填充结果数组：从后向前遍历输入数组，根据count数组确定元素位置

代码实现[编辑 | 编辑源代码]

Python示例[编辑 | 编辑源代码]

def counting_sort(arr):
    if not arr:
        return []
    
    max_val = max(arr)
    count = [0] * (max_val + 1)
    output = [0] * len(arr)
    
    # 统计元素出现次数
    for num in arr:
        count[num] += 1
    
    # 计算累积频次
    for i in range(1, len(count)):
        count[i] += count[i-1]
    
    # 反向填充结果数组（保证稳定性）
    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1
    
    return output

# 示例
arr = [4, 2, 2, 8, 3, 3, 1]
print("排序前:", arr)
sorted_arr = counting_sort(arr)
print("排序后:", sorted_arr)

模板:Output

关键点说明[编辑 | 编辑源代码]

稳定性：反向填充保证相同元素的原始顺序不变
边界处理：空数组直接返回
空间优化：可改为原地排序（但会失去稳定性）

复杂度分析[编辑 | 编辑源代码]

时间复杂度对比
情况	时间复杂度
最优情况	$O (n + k)$
最差情况	$O (n + k)$
平均情况	$O (n + k)$

空间复杂度： $O (n + k)$ （结果数组+计数数组）
稳定性：稳定（实现正确时）

应用场景[编辑 | 编辑源代码]

适用情况[编辑 | 编辑源代码]

1. 数据范围为已知有限整数 2. 需要稳定排序的场景 3. 数据量大但范围小的场景（如年龄排序）

实际案例[编辑 | 编辑源代码]

学生成绩排序：假设有10万名学生，成绩范围为0-100分：

# 生成随机成绩（示例）
import random
grades = [random.randint(0, 100) for _ in range(100000)]
sorted_grades = counting_sort(grades)  # 比快速排序快3倍

变体与优化[编辑 | 编辑源代码]

负数支持[编辑 | 编辑源代码]

通过偏移量处理负数：

def counting_sort_with_negative(arr):
    min_val = min(arr)
    max_val = max(arr)
    offset = -min_val
    count = [0] * (max_val - min_val + 1)
    
    for num in arr:
        count[num + offset] += 1
    
    # 其余步骤相同...

空间优化版[编辑 | 编辑源代码]

减少计数数组大小（需多次遍历）：

def counting_sort_optimized(arr):
    if not arr:
        return []
    
    min_val = min(arr)
    max_val = max(arr)
    count = [0] * (max_val - min_val + 1)
    
    for num in arr:
        count[num - min_val] += 1
    
    # 直接展开计数数组
    result = []
    for i in range(len(count)):
        result.extend([i + min_val] * count[i])
    
    return result

与其他算法对比[编辑 | 编辑源代码]

排序算法对比（k为数据范围）
算法	平均时间复杂度	稳定性	适用场景
计数排序	$O (n + k)$	稳定	小范围整数
快速排序	$O (n \log n)$	不稳定	通用排序
归并排序	$O (n \log n)$	稳定	大数据量

常见问题[编辑 | 编辑源代码]

Q1: 为什么计数排序不是比较排序？[编辑 | 编辑源代码]

计数排序通过统计元素出现次数而非比较元素大小来排序，因此不受 $O (n \log n)$ 比较排序下限限制。

Q2: 如何处理浮点数排序？[编辑 | 编辑源代码]

可将浮点数乘以精度系数转为整数（如两位小数×100），但会显著增加 $k$ 值，通常不推荐。

总结[编辑 | 编辑源代码]

计数排序在特定场景（小范围整数）下效率极高，但需注意：

仅适用于离散整数
数据范围过大会导致内存消耗剧增
稳定性取决于实现方式

页面模块:Message box/ambox.css没有内容。

@@ 第1行： / 第1行： @@
-{{DISPLAYTITLE:计数排序}}
+{{Note|本文介绍的是非比较型整数排序算法——计数排序（Counting Sort），适用于数据范围较小的整数排序场景。}}
-'''计数排序'''（Counting Sort）是一种非基于比较的[[排序算法]]，适用于整数数据的线性时间排序。其核心思想是通过统计每个元素的出现次数，然后根据统计结果直接确定排序后的位置。计数排序的时间复杂度为<math>O(n + k)</math>，其中<math>n</math>是元素数量，<math>k</math>是数据范围大小。
-== 算法原理 ==
+== 概述 ==
-计数排序的步骤如下：
+'''计数排序'''（Counting Sort）是一种稳定的线性时间排序算法，通过统计元素出现次数实现排序。其时间复杂度为<math>O(n + k)</math>（<math>k</math>为数据范围），空间复杂度为<math>O(n + k)</math>，适用于已知数据范围的整数排序。
-. '''统计频率'''：遍历输入数组，统计每个元素出现的次数，存入一个辅助数组（计数数组）。
-. '''计算前缀和'''：将计数数组转换为前缀和形式，表示每个元素在排序后数组中的最后位置。
-. '''反向填充'''：根据前缀和数组，将元素按顺序放入输出数组，同时更新前缀和以避免重复。
-=== 数学表示 ===
+=== 核心思想 ===
-对于输入数组<math>A</math>，输出数组<math>B</math>，计数数组<math>C</math>：
+. '''统计频率'''：统计每个元素出现的次数<br>
-* 统计频率：<math>C[A[i]] = C[A[i]] + 1</math>
+. '''计算位置'''：计算每个元素在输出数组中的最终位置<br>
-* 前缀和：<math>C[i] = C[i] + C[i-1]</math>
+. '''反向填充'''：根据统计结果将元素放入正确位置
-* 填充输出：<math>B[C[A[j]] - 1] = A[j]</math>
-== 示例代码 ==
+== 算法步骤 ==
-以下是用[[Python]]实现的计数排序代码：
+=== 输入与输出 ===
-<syntaxhighlight lang="python">
+* 输入：包含<math>n</math>个整数的数组<code>arr</code>，整数范围为<math>[0, k]</math>
-def counting_sort(arr):
+* 输出：排序后的数组
-    max_val = max(arr)
-    count = [0] * (max_val + 1)
-    output = [0] * len(arr)
-    # 统计频率
+=== 详细步骤 ===
-    for num in arr:
+. '''初始化计数数组'''：创建长度为<math>k+1</math>的数组<code>count</code>，初始值为0
-        count[num] += 1
+. '''统计元素频率'''：遍历输入数组，记录每个元素出现次数
+. '''计算累积频次'''：将<code>count</code>数组转换为元素最后出现的位置索引
+. '''反向填充结果数组'''：从后向前遍历输入数组，根据<code>count</code>数组确定元素位置
-     # 计算前缀和
+<mermaid>
-     for i in range(1, len(count)):
+flowchart TD
-        count[i] += count[i-1]
+     A[输入数组 arr] --> B[创建计数数组 count]
+     B --> C[统计元素频率]
+    C --> D[计算累积频次]
+    D --> E[反向填充结果数组]
+    E --> F[输出排序数组]
+</mermaid>
-     # 反向填充
+== 代码实现 ==
-     for num in reversed(arr):
+=== Python示例 ===
-         output[count[num] - 1] = num
+<syntaxhighlight lang="python">
-         count[num] -= 1
+def counting_sort(arr):
+    if not arr:
+        return []
+    max_val = max(arr)
+    count = [0] * (max_val + 1)
+    output = [0] * len(arr)
+     # 统计元素出现次数
+    for num in arr:
+        count[num] += 1
+    # 计算累积频次
+    for i in range(1, len(count)):
+        count[i] += count[i-1]
+    # 反向填充结果数组（保证稳定性）
+     for num in reversed(arr):
+         output[count[num] - 1] = num
+         count[num] -= 1
+    return output
-    return output
+# 示例
+arr = [4, 2, 2, 8, 3, 3, 1]
+print("排序前:", arr)
+sorted_arr = counting_sort(arr)
+print("排序后:", sorted_arr)
+</syntaxhighlight>
-# 示例输入
+{{Output|
-arr = [4, 2, 2, 8, 3, 3, 1]
+<pre>
-sorted_arr = counting_sort(arr)
+排序前: [4, 2, 2, 8, 3, 3, 1]
-print("排序前:", arr)
+排序后: [1, 2, 2, 3, 3, 4, 8]
-print("排序后:", sorted_arr)
+</pre>
-</syntaxhighlight>
+}}
-'''输出结果'''：
+=== 关键点说明 ===
-<pre>
+* '''稳定性'''：反向填充保证相同元素的原始顺序不变
-排序前: [4, 2, 2, 8, 3, 3, 1]
+* '''边界处理'''：空数组直接返回
-排序后: [1, 2, 2, 3, 3, 4, 8]
+* '''空间优化'''：可改为原地排序（但会失去稳定性）
-</pre>
 == 复杂度分析 ==
-* '''时间复杂度'''：<math>O(n + k)</math>，其中<math>k</math>是数据范围。若<math>k = O(n)</math>，则复杂度为线性。
+{| class="wikitable"
-* '''空间复杂度'''：<math>O(n + k)</math>，需要额外的计数数组和输出数组。
+|+ 时间复杂度对比
-* '''稳定性'''：计数排序是稳定的，因为反向填充保证了相同元素的相对顺序。
+! 情况 !! 时间复杂度
+|-
+| 最优情况 || <math>O(n + k)</math>
+|-
+| 最差情况 || <math>O(n + k)</math>
+|-
+| 平均情况 || <math>O(n + k)</math>
+|}
-== 适用场景与限制 ==
+* '''空间复杂度'''：<math>O(n + k)</math>（结果数组+计数数组）
-=== 适用场景 ===
+* '''稳定性'''：稳定（实现正确时）
-. 数据范围较小（如年龄、成绩等离散值）。
-. 需要稳定排序且数据为整数。
-. 作为基数排序的子过程。
-=== 限制 ===
+== 应用场景 ==
-. 仅适用于整数或可映射为整数的数据。
+=== 适用情况 ===
-. 数据范围过大时空间效率低。
+. 数据范围为已知有限整数
+. 需要稳定排序的场景
+. 数据量大但范围小的场景（如年龄排序）
-== 实际案例 ==
+=== 实际案例 ===
-'''场景'''：某学校需要按学生成绩（0~100分）快速排序。
+'''学生成绩排序'''：假设有10万名学生，成绩范围为0-100分：
-'''解决'''：使用计数排序，统计每个分数的学生人数后直接输出结果。
+<syntaxhighlight lang="python">
+# 生成随机成绩（示例）
+import random
+grades = [random.randint(0, 100) for _ in range(100000)]
+sorted_grades = counting_sort(grades)  # 比快速排序快3倍
+</syntaxhighlight>
-== 可视化示例 ==
+== 变体与优化 ==
-<mermaid>
+=== 负数支持 ===
-graph TD
+通过偏移量处理负数：
-     A[输入数组: 4, 2, 2, 8, 3, 3, 1]
+<syntaxhighlight lang="python">
-     B[计数数组: 0,1,2,2,1,0,0,0,1]
+def counting_sort_with_negative(arr):
-     C[前缀和: 0,1,3,5,6,6,6,6,7]
+     min_val = min(arr)
-    D[输出数组: 1,2,2,3,3,4,8]
+    max_val = max(arr)
-     A -->|统计频率| B
+    offset = -min_val
-     B -->|计算前缀和| C
+     count = [0] * (max_val - min_val + 1)
-    C -->|反向填充| D
-</mermaid>
+     for num in arr:
+        count[num + offset] += 1
+     # 其余步骤相同...
+</syntaxhighlight>
-== 与其他排序算法对比 ==
+=== 空间优化版 ===
-* '''对比快速排序'''：计数排序无需比较，但仅适用于有限范围整数。
+减少计数数组大小（需多次遍历）：
-* '''对比桶排序'''：计数排序是桶大小为1的特例。
+<syntaxhighlight lang="python">
+def counting_sort_optimized(arr):
+    if not arr:
+        return []
+    min_val = min(arr)
+    max_val = max(arr)
+    count = [0] * (max_val - min_val + 1)
+    for num in arr:
+        count[num - min_val] += 1
+    # 直接展开计数数组
+    result = []
+    for i in range(len(count)):
+        result.extend([i + min_val] * count[i])
+    return result
+</syntaxhighlight>
-== 扩展阅读 ==
+== 与其他算法对比 ==
-* [[基数排序]]：利用计数排序作为稳定子过程处理多关键字排序。
+{| class="wikitable"
-* [[桶排序]]：将数据分到有限数量的桶中再分别排序。
+|+ 排序算法对比（k为数据范围）
+! 算法 !! 平均时间复杂度 !! 稳定性 !! 适用场景
+|-
+| 计数排序 || <math>O(n + k)</math> || 稳定 || 小范围整数
+|-
+| 快速排序 || <math>O(n \log n)</math> || 不稳定 || 通用排序
+|-
+| 归并排序 || <math>O(n \log n)</math> || 稳定 || 大数据量
+|}
-{{算法导航}}
+== 常见问题 ==
+=== Q1: 为什么计数排序不是比较排序？ ===
+计数排序通过统计元素出现次数而非比较元素大小来排序，因此不受<math>O(n \log n)</math>比较排序下限限制。
+=== Q2: 如何处理浮点数排序？ ===
+可将浮点数乘以精度系数转为整数（如两位小数×100），但会显著增加<math>k</math>值，通常不推荐。
+== 总结 ==
+计数排序在特定场景（小范围整数）下效率极高，但需注意：
+* 仅适用于离散整数
+* 数据范围过大会导致内存消耗剧增
+* 稳定性取决于实现方式
+{{Warning|当<math>k \gg n</math>时（如排序[1, 1000000]），应优先选择比较排序算法}}
 [[Category:计算机科学]]
-[[Category:数据结构与算法]]
+[[Category:面试技巧]]
 [[Category:排序算法]]