基数排序(桶排序)
程序员文章站
2022-03-24 15:29:12
...
1。什么是基数排序(radix sort)?
基数排序 属于分配式排序(distribution sort),又称“桶排序”(bucket sort),它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用。
2.它和归并一样,属于稳定型算法。
public void radixSort(int []arr) {
//1.得到数组中最大的数的位数
int max=arr[0];
for(int i=1;i<arr.length;i++){
if(arr[i]>max){
max=arr[i];
}
}
//判断最大数是几位数
int maxLength=(max+"").length();
//定义一个二维数组,表示10个桶,每个桶就是一个一位数组
/*
说明:
1.二维数组包含10个一维数组;
2.为了防止一位数组在存放数时溢出,大小定位arr.length
3.明确:基数排序是以时间换空间的经典算法
*/
int [][]bucket=new int[10][arr.length];
//使用一个一维数组,来确定桶里世纪放了多少个数
int []bucketCount=new int[10];
for(int i=0,n=1;i<maxLength;i++,n*=10){
//针对每个元素对应的位进行排序处理
for(int j=0;j<arr.length;j++){
//取出每个元素对应的位数
int digitOfElem=arr[j]/n%10;
//放入到对应的桶中
bucket[digitOfElem][bucketCount[digitOfElem]]=arr[j];
bucketCount[digitOfElem]++;
}
//按照桶的顺序,(一维数组的下标一次取出,放入到原数组中)
int index=0;
for(int k=0;k<bucket.length;k++){
//如果桶中没有数据,不放
if(bucketCount[k]!=0){
//取出元素放入到桶
for(int l=0;l<bucketCount[k];l++){
//最大长度是确定的,所以点length不出来
arr[index++]=bucket[k][l];
}
}
//第i+1轮处理完后,将每个bucketCount[k]=0!!
bucketCount[k]=0;
}
}
// System.out.println(Arrays.toString(arr));
}
上一篇: 桶排序(基数排序)
下一篇: 算法设计经典算法总结