桶排序算法怎么實現(xiàn)?

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

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

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

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

　　4.每個桶各自排序。

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>());
}
//將每個元素放入桶
for(int i = 0; i < arr.length; i++){
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
//對每個桶進行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}
}