计数排序用于对一组线性存储的数据进行排序，是一种非比较排序算法，特别适合数据范围较小的场景。
计数排序是基于数值域的排序算法。通过查找比第 i 个元素大或小的数的个数，获取第 i 个元素的排序位置，从而实现排序。计数排序会使用额外的存储空间来统计元素出现的频率，是一种以空间换时间的算法。
在学习完整的计数排序之前，我们先来看一个简化版本。这个版本不需要前缀和，代码更短，更容易理解。
核心思路： 统计每个数值出现的次数，然后按顺序把每个数值输出对应的次数即可。
1#include <bits/stdc++.h>
2using namespace std;
3
4int cnt[105] = {};
5
6int main() {
7 int n, x;
8 cin >> n;
9 for (int i = 0; i < n; ++i) {
10 cin >> x;
11 ++cnt[x];
12 }
13 for (int i = 1; i <= 100; ++i) {
14 for (int j = 0; j < cnt[i]; ++j) {
15 cout << i << " ";
16 }
17 }
18 return 0;
19}简化版的局限性：
因此，当题目只要求输出排序后的数值时，简化版已经够用；当需要稳定排序或处理更复杂的数据时，就需要使用下面的完整版计数排序。
从小到大排序的工作原理如下：
下面是从小到大排序的完整实现代码：
1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[100005] = {};
5int cnt[105] = {};
6int ans[100005] = {};
7
8int main() {
9 int n;
10 cin >> n;
11 for (int i = 0; i < n; ++i) {
12 cin >> arr[i];
13 ++cnt[arr[i]];
14 }
15 for (int i = 2; i <= 100; ++i) {
16 cnt[i] += cnt[i - 1];
17 }
18 for (int i = n - 1; i >= 0; --i) {
19 ans[--cnt[arr[i]]] = arr[i];
20 }
21 for (int i = 0; i < n; ++i) {
22 cout << ans[i] << (i + 1 == n ? "\n" : " ");
23 }
24
25 return 0;
26}从大到小排序的工作原理如下：
下面是从大到小排序的完整实现代码：
1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[100005] = {};
5int cnt[105] = {};
6int ans[100005] = {};
7
8int main() {
9 int n;
10 cin >> n;
11 for (int i = 0; i < n; ++i) {
12 cin >> arr[i];
13 ++cnt[arr[i]];
14 }
15 for (int i = 99; i >= 1; --i) {
16 cnt[i] += cnt[i + 1];
17 }
18 for (int i = n - 1; i >= 0; --i) {
19 ans[--cnt[arr[i]]] = arr[i];
20 }
21 for (int i = 0; i < n; ++i) {
22 cout << ans[i] << (i + 1 == n ? "\n" : " ");
23 }
24 return 0;
25}下面通过一个具体例子，展示计数排序（从小到大）的完整执行过程。
输入数据： n = 8，数组 arr = [3, 1, 4, 1, 5, 9, 2, 6]，数据值域范围为 1~9。
第一步：统计每个数值出现的次数
遍历数组，对每个元素 arr[i]，执行 ++cnt[arr[i]]：
1cnt[1] = 2 （数值1出现2次）
2cnt[2] = 1 （数值2出现1次）
3cnt[3] = 1 （数值3出现1次）
4cnt[4] = 1 （数值4出现1次）
5cnt[5] = 1 （数值5出现1次）
6cnt[6] = 1 （数值6出现1次）
7cnt[9] = 1 （数值9出现1次）第二步：计算前缀和（确定每个数值的排名上界）
从左到右累加 cnt[i] += cnt[i-1]：
1cnt[1] = 2 （数值<=1的共2个）
2cnt[2] = 3 （数值<=2的共3个）
3cnt[3] = 4 （数值<=3的共4个）
4cnt[4] = 5 （数值<=4的共5个）
5cnt[5] = 6 （数值<=5的共6个）
6cnt[6] = 7 （数值<=6的共7个）
7cnt[7] = 7
8cnt[8] = 7
9cnt[9] = 8 （数值<=9的共8个）第三步：从后往前遍历原数组，放置元素到正确位置
从 i = 7 到 i = 0 依次处理：
1i=7: arr[7]=6, cnt[6]=7, --cnt[6]=6, ans[6]=6 → ans=[_,_,_,_,_,_,6,_]
2i=6: arr[6]=2, cnt[2]=3, --cnt[2]=2, ans[2]=2 → ans=[_,_,2,_,_,_,6,_]
3i=5: arr[5]=9, cnt[9]=8, --cnt[9]=7, ans[7]=9 → ans=[_,_,2,_,_,_,6,9]
4i=4: arr[4]=5, cnt[5]=6, --cnt[5]=5, ans[5]=5 → ans=[_,_,2,_,_,5,6,9]
5i=3: arr[3]=1, cnt[1]=2, --cnt[1]=1, ans[1]=1 → ans=[_,1,2,_,_,5,6,9]
6i=2: arr[2]=4, cnt[4]=5, --cnt[4]=4, ans[4]=4 → ans=[_,1,2,_,4,5,6,9]
7i=1: arr[1]=1, cnt[1]=1, --cnt[1]=0, ans[0]=1 → ans=[1,1,2,_,4,5,6,9]
8i=0: arr[0]=3, cnt[3]=4, --cnt[3]=3, ans[3]=3 → ans=[1,1,2,3,4,5,6,9]最终输出： 1 1 2 3 4 5 6 9
为什么要从后往前遍历？ 从后往前遍历可以保证排序的稳定性——当两个元素值相同时，原数组中靠后的元素在排序后仍然靠后，保持了相对顺序不变。
遇到需要使用计数排序的题目时，可以按以下步骤思考：
cnt 数组的大小，要能覆盖所有可能的数值cnt 数组的大小必须覆盖数据的值域范围，例如数据范围是 0~100，那么 cnt 数组至少要开到 cnt[101]cnt 和 ans 数组必须初始化为 0，否则统计结果会出错计数排序默认只能处理非负整数，因为数组下标不能为负。当数据范围包含负数时，需要对数据做偏移处理：将所有数值加上一个偏移量，使最小值变为 0。
例如数据范围是 -50 ~ 50，偏移量为 50，那么 -50 映射到 cnt[0]，50 映射到 cnt[100]。
1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[100005] = {};
5int cnt[205] = {}; // 值域 -100~100，偏移后 0~200
6int ans[100005] = {};
7const int OFFSET = 100; // 偏移量，使最小值 -100 映射到下标 0
8
9int main() {
10 int n;
11 cin >> n;
12 for (int i = 0; i < n; ++i) {
13 cin >> arr[i];
14 ++cnt[arr[i] + OFFSET]; // 加偏移量后统计
15 }
16 for (int i = 1; i <= 200; ++i) {
17 cnt[i] += cnt[i - 1];
18 }
19 for (int i = n - 1; i >= 0; --i) {
20 ans[--cnt[arr[i] + OFFSET]] = arr[i]; // 注意：ans中存原始值
21 }
22 for (int i = 0; i < n; ++i) {
23 cout << ans[i] << (i + 1 == n ? "\n" : " ");
24 }
25 return 0;
26}关键点： 偏移量只用在cnt数组的下标计算上，ans数组中存放的仍然是原始数值，输出时无需还原。
学到这里，我们已经掌握了多种排序算法。下面对比它们的特点，帮助你在不同场景下选择合适的算法：
| 排序算法 | 时间复杂度（平均） | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|
| 选择排序 | O(n²) | O(1) | 不稳定 | 数据量小，代码简单 |
| 冒泡排序 | O(n²) | O(1) | 稳定 | 数据量小，需要稳定排序 |
| 插入排序 | O(n²) | O(1) | 稳定 | 数据基本有序时效率高 |
| 计数排序 | O(n + w) | O(n + w) | 稳定 | 值域 w 较小，数据量大 |
什么时候用计数排序？
什么时候不用计数排序？
cnt 数组开不下计数排序的复杂度和特点如下（其中 n 为数据量，w 为数据值域范围）：
计数排序更适合对 n 比较大、w 比较小的数据进行排序，例如成绩排序、价格排序等场景。当数据值域较小而数据量较大时，计数排序的效率远高于基于比较的排序算法。