计数排序通过统计每个数值出现频次并回填实现排序，无需比较操作；核心是一维统计数组，下标为偏移后的数值，值为频次，适用于整数范围小且重复多的场景。
计数排序不是靠比较大小来排的，而是靠“数清楚每个数出现几次”，再按顺序填回去。它特别适合整数范围不太大的场景，比如学生成绩（0–100）、年龄（0–120）、小范围编号等。
为什么用一维数组做计数排序？
核心是建一个“统计数组”，下标代表数值，值代表该数值出现的次数。比如成绩数组 {85, 92, 85, 76}，最大值92、最小值76，只需开一个长度为 92 − 76 + 1 = 17 的数组，count[0] 对应76分出现几次，count[9] 对应85分出现几次……这样既省空间，又天然有序。
关键三步：找范围 → 统计频次 → 回填结果
实际操作分三步，每步都依赖一维数组：
- 找 min 和 max：遍历原数组一次，确定数值范围，避免申请过大数组
- 建 countingArray：长度 = max − min + 1，初始化全为 0；再遍历原数组，对每个数 x，执行 countingArray[x − min]++
- 回填原数组：按 countingArray 下标从小到大遍历，若 countingArray[i] = n，就把 i + min 这个数连续写入 n 次
注意边界和常见坑
直接套公式 max + 1 开数组容易爆内存，比如数据是 {3, 1000, 5}，max=1000，但真正需要的只有 1000−3+1=998 个位置。
负数也能处理——只要把 min 找准，偏移量就从 −min 开始。例如数组含 {−5, 0, 3}，min=−5，那么 −5 映射到下标 0，0 映射到下标 5，3 映射到下标 8。
如果数据重复多、跨度小（如 1000 个 1–20 之间的随机数），计数排序比冒泡、选择快得多，时间复杂度稳定 O(n + k)，k 是数值范围。
它和普通比较排序的本质区别
冒泡、选择、插入这些算法，本质是在原数组上不断交换元素位置，依赖两两比较；而计数排序跳过了比较环节，只做“计数”和“展开”，所以不适用于浮点数、字符串或范围极大且稀疏的整数（如 {1, 1000000}）。
