企业管理课程培训,中国seo公司,信丰网站制作,沧州公司网站建设基数排序 基数排序#xff0c;给关键字分成d位#xff08;组#xff09;#xff0c;#xff0c;对每一位的情况#xff0c;可能会出现的值位r#xff08;基数#xff09;个#xff0c;然后分成r个队列#xff0c;对每个对林进行分配耗时O(n)#xff0c;最后按照改位…基数排序 基数排序给关键字分成d位组对每一位的情况可能会出现的值位r基数个然后分成r个队列对每个对林进行分配耗时O(n)最后按照改位组情况进行收集耗时O(r)
所以基数排序的
时间复杂度:O(d*(rn))。
空间复杂度Or,创建r个队列。-口令饿额外空间鬼归并排序炸鸡基数排序块
稳定性稳定一直按照关键字有序排列的相同关键字入队相对位置不会变
适用情况
1.每组关键字方便拆成d位组且d比较小。
2.每组关键字取值不大r较小。
3.元素个数较大时d比较大。
2.思路 有点乱简单来说以整数为例子有一个线性表每个结点存储的数据都为三位数关键字。
三位数按照位数分为个位、十位、百位d3先进行个位的情况个位可能出现的数字为0-9十个数字因此r10.准备10个队列每一个队列存储一个数字出现的可能性。按照个位进行入队。这为分配如果要求递减序列则给个位按照递减依次给队列从大队列到小队列链接起来最后收集成一个新的线性表这叫收集随后再根据十位的情况重复类似的操作最后进行完即可如图
分配 收集
