Bucket sort

• bucket-sort ref.1

//	桶排序的基本思想是：把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。
//	计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。
//
//	1.找出待排序数组中的最大值max、最小值min
//	2.我们使用 动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1
//	3.遍历数组 arr，计算每个元素 arr[i] 放的桶
//	4.每个桶各自排序
//	5.遍历桶数组，把排序好的元素放进输出数组
import java.util.*;

class Solution {

	public static void bucketSort(double[] arr){
		//桶数
		int bucketNum = arr.length;
		ArrayList<ArrayList<Double>> bucketArr = new ArrayList<>(bucketNum);		
		for(int i = 0; i < bucketNum; i++){
			bucketArr.add(new ArrayList<Double>());
		}

		//将每个元素放入桶
		for(int i = 0; i < arr.length; i++){
			int num =(int) (arr[i] * (arr.length));
			bucketArr.get(num).add(arr[i]);
		}
		
		//对每个桶进行排序
		for(int i = 0; i < bucketArr.size(); i++){
			Collections.sort(bucketArr.get(i));
		}
		
		for(ArrayList<Double> ls:bucketArr){
			for (int i=0;i<ls.size();i++) {
				System.out.print(ls.get(i)+" ");
			}
		}
	}
	
    //*********************************************
	public static void main(String[] args) {
		double[] arr = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434}; 
		bucketSort(arr);
	}
}