基数排序
标签: 数据结构
学习人数: 4100

前言

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

 

算法思想

基本思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

算法步骤:

基数排序的方式可以采用 LSD(Least significant digital)或 MSD(Most significant digital),LSD 的排序方式由键值的最右边开始,而 MSD 则相反,由键值的最左边开始。

不妨通过一个具体的实例来展示一下基数排序是如何进行的。 设有一个初始序列为: R {50, 123,...

登录查看完整内容


课后作业

课后习题

 

【2013年真题】对给定的关键字序列 110,119,007,911,114,120,122 进行基数排序,则第 2 趟分配收集后得到的关键字序列是 
A.007,110,119,114,911,120,122         
B.007,110,119,114,911,122,120 
C.007,110,911,114,119,120,122         
D. 110,120,911,122,114,007,119 

参考答案:C
答案解析:基数排序的第 1 趟排序是按照个位数字来排序的,第 2 趟排序是按然十位数字的大小进行排序的,答案是 C 选项。 


登录后发布评论

暂无评论,来抢沙发