import java.util.Arrays;
public class BucketSort {
//桶排序-计数排序
public static void bucketSort(int[] arr){
if(arr==null||arr.length<2) {
return ;
}
int max=Integer.MIN_VALUE;
for(int i=0;i<arr.length;i++) {
max=Math.max(max, arr[i]);
}
int bucket[]=new int[max+1];
for(int i=0;i<arr.length;i++) {
bucket[arr[i]]++;
}
int i=0;
for(int j=0;j<bucket.length;j++){
//先判断bucket[j]是否大于0,然后再自减
while(bucket[j]-->0) {
arr[i++]=j;
}
}
}
//调用系统类库函数
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
//获取随机数组
public static int[] getRandomArray(int maxSize,int maxValue) {
int[] arr=new int[(int)((maxSize+1)*Math.random())];
for(int i=0;i<arr.length;i++) {
//获取 0 ~ maxValue 的值
//此处随机变量值为非负数
arr[i]=(int)((maxValue+1)*Math.random());
}
return arr;
}
//复制数组
public static int[] copyArray(int[] arr) {
if(arr==null) {
return null;
}
int[] book=new int[arr.length];
for(int i= 0;i<arr.length;i++) {
book[i]=arr[i];
}
return book;
}
//比较
public static boolean isEqual(int[] arr1,int[] arr2) {
if((arr1==null&&arr2!=null)||(arr1!=null&&arr2==null)){
return false;
}
if(arr1==null&&arr2==null) {
return true;
}
if(arr1.length!=arr2.length) {
return false;
}
for(int i=0;i<arr1.length;i++) {
if(arr1[i]!=arr2[i]) {
return false;
}
}
return true;
}
//打印数组
public static void printArray(int arr[]) {
if(arr==null) {
return;
}
for(int i=0;i<arr.length;i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
//测试次数
int test=50000;
//数组长度
int maxSize=100;
//最大数值
int maxValue=100;
boolean flag=true;
for(int i=0;i<test;i++) {
int arr1[]=getRandomArray(maxSize,maxValue);
//拷贝比较
int arr2[]=copyArray(arr1);
bucketSort(arr1);
comparator(arr2);
if(!isEqual(arr1,arr2)) {
flag=true;
break;
}
}
System.out.println(flag?"测试正常":"发生错误");
//随机测试一组数据
int arr[]=getRandomArray(maxSize,maxValue);
printArray(arr);
bucketSort(arr);
printArray(arr);
}
}