内部排序算法:基数排序

基本思想 基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。 基数排序可以采用两种方式: LSD(Least Significant Digital):从待排序元素的最右边开始计算(如果是数字类型,即从最低位个位开始)。 MSD(Most Significant Digital):从待排序元素的最左边开始计算(如果是数字类型,即从最高位开始)。 我们以LSD方式为例,从数组R[1..n]中每个元素的最低位开始处理,假设基数为radix,如果是十进制,则radix=10。基本过程如下所示: 计算R中最大的元素,求得位数最大的元素,最大位数记为distance; 对每一位round<=distance,计算R[i] % radix即可得到; 将上面计算得到的余数作为bucket编号,每个bucket中可能存放多个数组R的元素; 按照bucket编号的顺序,收集bucket中元素,就地替换数组R中元素; 重复2~4,最终数组R中的元素为有序。 算法实现 基数排序算法,Java实现,代码如下所示: p