计数排序通过数组下标映射元素值、对应值存储频次实现，适用于值域小的非负整数；含负数时需偏移处理，时间复杂度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 注释风格。

下载

• 先扫描获取最小值 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);

不复杂但容易忽略：计数排序真正的高性能，来自消除了元素间两两比较，把“比较逻辑”编译为最直接的内存寻址操作。

Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南