8.5.2 基数排序

LSD基数排序从低位到高位，每趟必须稳定分配收集；适合位数固定、基数有限的键。

手工推演与代码

170,45,75,90先按个位稳定分桶，再十位、百位，最终45,75,90,170。

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

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。每趟用不稳定排序；高位先排却套LSD规则；负数未定义。

迁移训练

为什么个位相同元素次序必须保留？答案高位处理依赖低位已有次序。