算法（7）——桶排序算法
桶排序的基本思想是：把数组 arr 划分为 n 个大小相同子区间（桶），每个子区间各自排序，最后合并 。计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。
1.找出待排序数组中的最大值 max、最小值 min
2.我们使用 动态数组 ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1
3.遍历数组 arr，计算每个元素 arr[i] 放的桶
4.每个桶各自排序
public class BucketSort extends Sort<Integer>{@Overrideprotected void sort() {// TODO Auto-generated method stub//最大最小值int max = array[0];int min = array[0];int length = array.length/4;for(int i=1; i<array.length; i++) {if(array[i] > max) {max = array[i];} else if(array[i] < min) {min = array[i];}}//最大值和最小值的差int diff = max - min;//桶列表ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();for(int i = 0; i < length; i++){bucketList.add(new ArrayList<>());}//每个桶的存数区间float section = (float) diff / (float) (length - 1) ;//数据入桶for(int i = 0; i < array.length; i++){//当前数除以区间得出存放桶的位置 减1后得出桶的下标int num = (int) (array[i] / section) - 1;if(num < 0){num = 0;}bucketList.get(num).add(array[i]);}//桶内排序for(int i = 0; i < bucketList.size(); i++){//jdk的排序速度当然信得过Collections.sort(bucketList.get(i));}//写入原数组int index = 0;for(ArrayList<Integer> arrayList : bucketList){for(int value : arrayList){array[index] = value;index++;}}}