基数排序
2020-07-14 本文已影响0人
YAOPRINCESS
结果
30 11 1 25 5 6
1 5 6 11 25 30
完整代码
package com.nan;
/**
* @author klr
* @create 2020-07-14-10:47
*/
public class BucketSort {
public static void main(String[] args) {
int[] arr=new int[]{11,25,6,30,1,5};
BucketSort.sort(arr);
}
public static void sort(int[] arr){
//查找最大的数,计算总共要遍历几次,也就是最大数的位数
int max=arr[0];
for(int i=1;i<arr.length;i++){
if(arr[i]>max)
max=arr[i];
}
//求位数
int maxLength=(""+max).length();
//创建桶
int[][] container=new int[10][arr.length];
//创建每个桶的计数器
int[] counter=new int[10];
for (int i = 0,n=1; i < maxLength; i++,n*=10) {
//排序,填入桶
// /n%10用于求每个位上的数字
for(int j=0 ;j<arr.length;j++){
int digit=arr[j] /n %10;
container[digit][counter[digit]++]=arr[j];
}
//复制回原数组
int index=0;
for(int k=0;k<counter.length;k++){
//如果桶不为空
if(counter[k]!=0){
for (int m = 0; m < counter[k]; m++) {
arr[index++]=container[k][m];
}
counter[k]=0;
}
}
for (int num : arr) {
System.out.print(num+" ");
}
System.out.println();
}
}
}