计数排序
一句话总结
计数排序通过统计每种元素出现的次数来推算排序后位置，时间空间复杂度均为 O(n + max - min)，是一种非比较排序算法。
核心要点
1. 基本原理
计数排序的核心思想是：统计每种元素出现的次数，进而推算出每个元素在排序后数组中的索引位置，最终完成排序。
- 需要将元素的值作为
count数组的索引才能计数 - 仅关心元素出现次数，不关心相同元素的相对位置 → 不稳定排序
- 适合元素值范围不大的场景
2. 时间空间复杂度
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n + max - min) | n 是数组长度，max - min 是元素值范围 |
| 空间复杂度 | O(n + max - min) | count 数组大小取决于元素值范围 |
3. 适用场景与限制
适用场景：
- 元素都是非负整数（或可通过偏移量处理负数）
- 元素值范围不大（max - min 不太大）
- 不要求稳定排序
限制/问题：
- 只能处理整数类型（或可以映射到整数的类型）
- 元素值范围过大时，count 数组会太大，空间效率低
- 原生实现是不稳定排序
基本原理
简单示例
输入一个 nums 数组，统计出：
- 2 个元素
1 - 1 个元素
3 - 3 个元素
6
那么只要依次填入 2 个 1，1 个 3，3 个 6，就能得到排序结果 [1, 1, 3, 6, 6, 6]。
通用计数排序的关键问题
- 负数处理：是不是只能处理非负整数？包含负数时如何排序？
- 稳定性：计数排序是否一定是不稳定排序？
- 大值范围问题：如果数组最大元素值很大，会不会导致 count 数组太大？
时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 计数排序 | O(n + k) | k = max - min + 1，元素值范围 |
| 最佳情况 | O(n + k) | 与数据分布无关 |
| 最坏情况 | O(n + k) | 与数据分布无关 |
代码实现
简单版本（LeetCode 75 颜色分类）
class Solution {
public void sortColors(int[] nums) {
// 统计 0, 1, 2 出现的次数
int[] count = new int[3];
for (int element : nums) {
count[element]++;
}
// 按照 count 数组的统计结果，依次填充原数组
int index = 0;
for (int element = 0; element < 3; element++) {
for (int i = 0; i < count[element]; i++) {
nums[index] = element;
index++;
}
}
}
}
说明：这个例子只有 0, 1, 2 三种元素，是最简单的计数排序场景。
⚠️ 原文在通用计数排序代码实现处截断，完整的通用计数排序代码（处理负数、保证稳定性等）缺失。
对比分析
| 维度 | 计数排序 | 比较排序（快排/归并等） |
|---|---|---|
| 排序类型 | 非比较排序 | 比较排序 |
| 时间复杂度 | O(n + k) | O(n log n) |
| 稳定性 | 原生不稳定 | 取决于实现 |
| 适用数据类型 | 整数（范围不大） | 任意可比较类型 |
| 额外空间 | O(k) | O(1) ~ O(n) |
应用场景
- 元素值范围有限的整数排序（如年龄、分数、状态码等）
- 作为基数排序的子过程
- LeetCode 75 颜色分类等特定场景
相关题目
| 平台 | 题目 | 难度 |
|---|---|---|
| LeetCode | 75. Sort Colors | 简单 |
| 力扣 | 75. 颜色分类 | 简单 |
| LeetCode | 912. Sort an Array | 中等 |
| 力扣 | 912. 排序数组 | 中等 |
相关概念
- 排序算法：计数排序是排序算法的一种
- 时间复杂度：O(n + max - min)
- 空间复杂度：O(n + max - min)
- 选择排序：同为 O(n²) 级别的简单排序算法
- 快速排序：比较排序的代表，O(n log n)
- 计数排序：
相关实体
- labuladong：本文来源
- leetcode：题目平台
总结
计数排序是一种非比较排序算法，通过统计元素出现次数实现排序，时间复杂度 O(n + k)，适合元素值范围不大的整数排序场景。原生实现是不稳定排序。
待补充
以下内容缺失：
- 通用计数排序的完整实现（处理负数、保证稳定性等）
- 计数排序的三个关键问题详细解答
- 稳定计数排序的实现方法
- 计数排序与基数排序的关系
- 完整的代码实现和可视化说明