排序算法 COUNTING SORT
计数排序.
统计各数值出现次数，再按累计位置写入输出数组。
时间O(n + k)额外空间O(n + k)稳定性稳定
原理与执行逻辑
利用整数值域直接统计频次，再把频次累加成位置边界。每个元素根据累计计数放入输出数组，避免逐对比较。
执行步骤
- 建立计数数组，统计每个数值出现次数。
- 累加计数，使 count[v] 表示不大于 v 的元素数量。
- 逆序扫描输入，将 v 放到 --count[v] 对应的位置。
- 把输出数组复制回原数组。
关键理解
逆序扫描与从右端分配位置配合，使相等元素保持原顺序。空间开销受最大值影响，值域很大时计数数组也会很大。
简短示例
[2, 1, 2] 中不大于 1 的元素有 1 个，不大于 2 的有 3 个；两个 2 从后向前放到下标 2、1，1 放到下标 0。
代码与执行动画
STEP 0 / 20function countingSort(arr) { const count = Array(Math.max(...arr) + 1).fill(0); for (const value of arr) count[value]++; for (let v = 1; v < count.length; v++) count[v] += count[v - 1]; const output = Array(arr.length); for (let i = arr.length - 1; i >= 0; i--) { output[--count[arr[i]]] = arr[i]; } for (let i = 0; i < arr.length; i++) arr[i] = output[i]; return arr;}高亮对应当前步骤；源码对传入数组进行原地排序。
数组状态
升序 · 8 个元素比较 0实际交换 0数组写入 0当前区间 —
待排序当前操作已就位
下标显示在底部；柱体随元素移动，等值元素也保留独立身份。
0
准备排序
点击下一步或自动播放，观察数组从左到右升序排列的过程。
调整待排序数组
使用相同数据切换算法，观察比较与交换过程。
计数排序的执行规则
k 是最大值加一。适合值域较小的非负整数；本实现逆序填充输出，保持稳定性。
交换次数仅统计两个不同位置的交换；可输入重复值。对应题目与扩展练习
观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。
利用有限值域统计频次，按指定顺序与升序输出。
- 扩展练习75. 颜色分类打开题目
练习三种值的计数与回填；进阶要求常数空间的一趟扫描。