基数排序

基数排序是一种非比较型排序，基于关键字各位的大小进行排序，通常借助「分配」和「收集」两种操作实现。

基本思想

• 按关键字的最低有效位（LSD）优先或最高有效位（MSD）优先
• 每一趟按某一位上的值将元素分配到对应「桶」中，再按顺序收集
• 经过 $d$ 趟（$d$ 为关键字的位数）后完成排序

复杂度

• 时间复杂度：$O(d(n + r))$，其中 $d$ 是关键字的位数，$r$ 是基数（桶的个数）
• 稳定性：稳定
• 空间复杂度：$O(r)$

特点

• 适用于关键字位数较少、可以分割且取值范围有限的场景
• 不基于元素间的比较