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较大
