👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com
喜欢《数据结构》部分笔记的小伙伴可以订阅专栏,今后还会不断更新。🧑💻
感兴趣的小伙伴可以点一下订阅、收藏、关注!🚀
谢谢大家!🙏
思想
第一趟“收集”:以“个位”作为参考进行分配
第一趟“收集”结束:得到按“个位”递减排序的序列(链表)
第二趟“收集”:以“十位”进行分配,当两个数据“十位”相同时,“个位”更大的先入队
第二趟“收集”结束:得到按“十位”递减排序的序列,“十位”相同的按“个位”递减排序
第三趟“收集”:以“百位”进行分配,当两个数据“百位”相同时,“十位”更大的先入队
第三趟“收集”结束:得到按“百位”递减排序的序列,“百位”相同的按“十位”递减排序,若“十位”还相同则按“个位”递减排序
算法效率分析
需要 r r r 个辅助队列,空间复杂度 = O ( r ) =O(r) =O(r)
一趟分配 O ( n ) O(n) O(n) ,一趟收集 O ( r ) O(r) O(r),一共 d 趟分配、收集,总的时间复杂度 = O ( d ( n + r ) ) =O(d(n+r)) =O(d(n+r))
稳定性:稳定
应用
某学校有 10000 个学生,将学生信息按年龄递减排序
生日可拆分为三组关键字:年、月、日
基数排序擅长解决的问题:
- 数据元素的关键字可以方便地拆分为d组,且d较小
- 每组关键字的取值范围不大,即 r 较小
- 数据元素个数 n 比较大