计数排序通过数组下标映射元素值、对应值存储频次实现，适用于值域小的非负整数；含负数时需偏移处理，时间复杂度O(n+k)，无需比较操作。
java 中通过数组下标直接映射实现计数排序，核心在于用下标代表待排序元素的值，用对应位置的值代表该元素出现的频次。这种方式仅适用于整数、且值域范围可控（如 0～10000）的场景，时间复杂度稳定为 o(n + k)，远优于比较类排序。
明确适用前提：值域小且非负整数
计数排序不是通用排序算法，它依赖“值 → 数组下标”的一对一映射。因此：
- 输入必须是整数（通常是非负整数，若含负数需整体偏移）
- 最大值与最小值之差（即值域大小 k）不能过大，否则空间浪费严重或触发内存异常
- 例如：对 10 万个 [0, 999] 的整数排序，申请长度为 1000 的计数数组完全可行；但若值域是 [-2^31, 2^31-1]，则不可行
基础实现：无偏移、非负整数版本
假设输入数组 arr 元素均在 [0, maxVal] 范围内：
- 第一步：遍历原数组，统计每个数字出现次数，存入 count[maxVal + 1]
- 第二步：对 count 数组做前缀和（即累加），使 count[i] 表示 ≤ i 的元素总个数
- 第三步：逆序遍历原数组（保证稳定性），根据元素值 x 查 count[x] 得到其应处的最终位置索引，填入结果数组后 count[x]--
关键点：逆序遍历 + 前缀和后自减，确保相同元素的相对顺序不变（稳定排序）。
支持负数与任意整数的偏移处理
当输入含负数（如 [-50, 150]）时，不能直接用负数作下标。解决方案是统一偏移：
Java注释规范Skills
下载
当用户要求为 Java 代码添加注释、修改注释、审查注释、整理注释格式，或要求按照代码注释规范处理 Java 文件时，使用本技能。本技能用于统一生成和维护 Java 类注释模板、按 Git 对比 release 判断版本号、补充每行代码上方中文块注释、调整注释空行规则，并保持 Java 文件 UTF-8 无 BOM 编码。典型触发场景包括：补充类注释、更新 @version、检查 @author 来源、整理行尾注释、把注释放到代码上一行、检查注释是否符合规范、构建前检查 Java 注释风格。
立即学习“Java免费学习笔记（深入）”；
- 先扫描获取最小值 min 和最大值 max
- 创建长度为 max - min + 1 的计数数组
- 将每个元素 x 映射到下标 x - min（例如 -50 → 0，0 → 50，150 → 200）
- 还原时，结果值 = 下标 + min
这样既保留了下标映射的高效性，又扩展了数值范围适应能力。
优化技巧：避免冗余空间与拷贝
实际使用中可进一步提升性能：
- 若只需统计频次（不关心排序后数组），跳过前缀和与回填步骤，仅用一次遍历完成计数
- 若原数组允许修改，可复用输入数组作为输出缓冲区，减少额外空间分配
- 对极小值域（如布尔状态、枚举类型），可用 boolean[] 或位图（long[]）压缩空间
- JDK 8+ 可结合 IntStream 快速求极值：
int min = Arrays.stream(arr).min().orElse(0);
不复杂但容易忽略：计数排序真正的高性能，来自消除了元素间两两比较，把“比较逻辑”编译为最直接的内存寻址操作。
