保研复习数据结构记（9）--基数排序

作者：小蓝xlanll | 2024-03-16 15:28:44

踩

保研复习数据结构记（9）--基数排序

基数排序的过程？首先设置r个（r：每个关键字位可以对应多少取值）空队列， $Q_0,Q_1,...,Q_{r-1}$ ，按照各个关键字位权重递增的次序（个、十、百），将d个元素（关键字可以被拆分成d个部分）分别做“分配”和“收集”。分配：顺序扫描各个元素，若当前处理的关键字位=x，则将元素插入Qx队尾。收集：把 $Q_0,Q_1,...,Q_{r-1}$ 结点一次出队并链接。如果需要递增序列，那么在入队的时候就按照不同权重将序列由高到低入队。基数排序不是基于比较，而其他排序都是基于比较来完成。
基数排序的空间复杂度是多少？O(r)，因为设置了r个辅助队列。
基数排序的时间复杂度是多少？O(d*(n+r)
基数排序是稳定的？是稳定的
基数排序的应用？可以应用于排序年月日
基数排序擅长解决哪些问题？（1）数据元素的关键字可以方便的拆分为d组，且d较小（2）每组关键字的取值范围不大，即r较小（3）数据元素的个数n较大

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/250348