一、什么是基数排序
基数排序属于非比较类排序——非比较类排序包括计数排序、基数排序、桶排序。
基数排序是由计数排序改善而来的,基数排序将整数或者字符串切分不同的数字或字符,然后按照低位先排序收集,接着高位排序收集,依次类推直到最高位。
动图演示
二、基数排序的代码实现
public static void sort(int[] arr){
int length = arr.length;
int max = arr[0];
for(int i = 0;i < length;i++){
if(arr[i] > max){
max = arr[i];
}
}
int location = 1;
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
for(int i = 0; i < 10; i++){
bucketList.add(new ArrayList());
}
while(true)
{
int dd = (int)Math.pow(10,(location - 1));
if(max < dd){
break;
}
for(int i = 0; i < length; i++)
{
int number = ((arr[i] / dd) % 10);
bucketList.get(number).add(arr[i]);
}
int nn = 0;
for (int i=0;i<10;i++){
int size = bucketList.get(i).size();
for(int ii = 0;ii < size;ii ++){
arr[nn++] = bucketList.get(i).get(ii);
}
bucketList.get(i).clear();
}
location++;
}
}
三、总结
基数排序是稳定的算法,算法的时间复杂度为O(d(n+r)),d为位数,r为基数。算法这块考察的最基础的知识就是排序这一块了,实际有十大排序算法,但我认为只要掌握八大排序算法就已经够了。其实在很多时候,程序员对于排序算法应该算是非常熟悉了,有些语言例如c++STL容器也封了排序算法。但这些还不够,对自己的最低要求是要能手写这些算法的实现,清楚每种算法的特性、时间复杂度等。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)