计数排序适合非负整数且数值范围不大的数组，时间复杂度O(n+k)，通过统计频次、映射下标实现稳定排序，支持负数偏移处理，但不适用于浮点数或大范围数据。
计数排序适合对整数数组排序，尤其当数值范围不大（比如 0 到 100）时效率很高，时间复杂度是 O(n + k)，其中 k 是数值范围大小。它不是基于比较的排序，而是利用数组下标作为数值映射来统计频次，再按顺序还原。
理解计数排序的核心思路
计数排序不比较元素大小，而是先统计每个数值出现的次数，再根据统计结果依次填入输出数组。前提是：数组元素必须是非负整数，且最大值不能过大（否则辅助数组太占内存）。
如果原始数组含负数或范围跨度大（如 -1000 到 10000），需要做偏移处理——找出最小值，把所有数减去它，使最小值变为 0，排序后再加回去。
实现步骤与关键代码
以非负整数、已知范围为例（如数组元素都在 [0, 9] 内）：
立即学习“Java免费学习笔记（深入）”；
- 找出数组最大值 max，创建长度为 max + 1 的计数数组 count，初始化为 0
- 遍历原数组，对每个元素 num 执行 count[num]++
- 遍历 count 数组，对每个下标 i，将 i 重复 count[i] 次写入结果数组
Java 示例代码：
public static int[] countingSort(int[] arr) {
if (arr.length == 0) return arr;
<pre class='brush:java;toolbar:false;'>int max = Arrays.stream(arr).max().orElse(0);
int[] count = new int[max + 1];
// 统计频次
for (int num : arr) {
count[num]++;
}
// 构造排序后数组
int[] sorted = new int[arr.length];
int idx = 0;
for (int i = 0; i < count.length; i++) {
while (count[i]-- > 0) {
sorted[idx++] = i;
}
}
return sorted;}
处理含负数或任意范围的情况
若数组含负数（如 [-5, 3, -2, 1]），不能直接用下标索引。需先求出 min 和 max：
- min = -5，max = 3 → 范围跨度为 max - min + 1 = 9
- 创建长度为 9 的 count 数组，把每个 num 映射到索引 num - min（即 -5→0，-2→3，1→6）
- 还原时，真实值 = 下标 + min
这样既保持逻辑清晰，又避免负数下标异常。
注意事项和适用边界
计数排序不是万能的：
- 不适合浮点数、字符串等不可直接映射为小整数的类型
- 当 k（数值范围）远大于 n（元素个数）时，空间浪费严重，不如快排或归并
- 它是稳定排序——相同元素的相对位置不会改变，前提是构造结果数组时从左到右遍历 count
- 原地排序？不行。它需要额外 O(k) 空间存计数数组，O(n) 空间存结果，无法真正原地完成
实际项目中，若数据来自传感器读数、等级评分、年龄等有限离散值，计数排序简洁高效；但通用排序场景仍推荐 Arrays.sort()（底层是双轴快排+Timsort混合策略）。
