BucketSort-桶排序-计数排序

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);

	}
		

}