1.算法思想
- 将整个关键字拆分为d位(或“组”)
- 按照各个关键字位,权重递增的次序(如:个、十、百),做d趟“分配”和“收集”,若当前处理的关键字位可能取的r个值,则需要建立r个队列
- 分配:顺序扫面各个元素,根据当前处理的关键字位,将元素插入到相应队列。一趟分配耗时O(n)
- 收集:把各个队列中的结点依次出队并链接。一趟收集耗时O(r)
2.分类
最高位优先算法MSD
- 权重依次递减,逐层分成若干个子序列,最后将所有子序列依次连成一个有序序列
最低位优先算法
- 权重依次递增排序,最后形成一个有序序列
- 整个序列参与排序
3.性能
空间复杂度
- O(r)
- 一趟排序需要r个辅助队列存储空间
时间复杂度
- O(d(n+r))
- 需要进行d趟手机,一趟分配需要O(n),一趟收集需要O(r)
稳定性
- 稳定
4.擅长处理
- 数据元素的关键字可以方便地拆分为d组,且d较小
- 每组关键字的取值范围不大,即r较小
- 数据元素个数n较大



