08-8.5.2 基数排序

👋 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$ 个辅助队列，空间复杂度$=O(r)$
一趟分配 $O(n)$ ，一趟收集 $O(r)$，一共 d 趟分配、收集，总的时间复杂度 $=O(d(n+r))$

稳定性：稳定

应用

某学校有 10000 个学生，将学生信息按年龄递减排序
生日可拆分为三组关键字：年、月、日

基数排序擅长解决的问题：

1. 数据元素的关键字可以方便地拆分为d组，且d较小
2. 每组关键字的取值范围不大，即 r 较小
3. 数据元素个数 n 比较大