8.5.3 计数排序

计数排序统计值域每个键次数，前缀和确定输出位置。时间O(n+k)、空间O(k)，当值域远大于n时不合算；反向扫描输入可稳定。

手工推演与代码

[2,0,2,1]计数[1,1,2]，输出[0,1,2,2]。

代码实现必须保持当前有序区、堆区或归并段的不变量，并对空数组、单元素、重复键和逆序输入测试。

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。允许负数却不做偏移；原地直接按计数覆盖却声称稳定；忽略值域空间。

迁移训练

键范围[-2,2]如何索引？答案整体加2映射到0..4。