桶排序的基本思想是： 把數(shù)組 arr 劃分為 n 個(gè)大小相同子區(qū)間(桶)，每個(gè)子區(qū)間各自排序，最后合并 。計(jì)數(shù)排序是桶排序的一種特殊情況，可以把計(jì)數(shù)排序當(dāng)成每個(gè)桶里只有一個(gè)元素的情況。

　　1.找出待排序數(shù)組中的最大值 max、最小值 min

　　2.我們使用 動(dòng)態(tài)數(shù)組 ArrayList 作為桶，桶里放的元素也用 ArrayList 存儲(chǔ)。桶的數(shù)量為(maxmin)/arr.length+1

　　3.遍歷數(shù)組 arr，計(jì)算每個(gè)元素 arr[i] 放的桶

　　4.每個(gè)桶各自排序。

public static void bucketSort(int[] arr){

int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
//創(chuàng)建桶
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum); for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
//將每個(gè)元素放入桶
for(int i = 0; i < arr.length; i++){
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
//對(duì)每個(gè)桶進(jìn)行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}
}