桶排序的基本思想：它就是把陣列arr[]劃分為N個大小相同的子區間（桶），每個子區間各自排序，最后合并，計數排序是桶排序的一種特殊情況，可以把計數排序當成每個桶里只有一個元素的情況，
步驟：
1.找出待排序陣列中的最大值max、最小值min；
2.我們使用動態陣列arraylist作為桶，桶里放的元素也用arraylist存盤，桶的數量為（max-min）/arr.length+1；
3.遍歷陣列arr，計算每個元素arr[i]放的桶；
4.每個桶各自排序
演算法實作：
1 public static void bucketSort(int[] arr){
2 int max = Integer.MIN_VALUE;
3 int min = Integer.MAX_VALUE;
4 for(int i = 0; i < arr.length; i++){
5 max = Math.max(max, arr[i]);
6 min = Math.min(min, arr[i]);
7 }
8 //創建桶
9 int bucketNum = (max - min) / arr.length + 1;
10 ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
11 for(int i = 0; i < bucketNum; i++){
12 bucketArr.add(new ArrayList<Integer>());
13 }
14 //將每個元素放入桶
15 for(int i = 0; i < arr.length; i++){
16 int num = (arr[i] - min) / (arr.length);
17 bucketArr.get(num).add(arr[i]);
18 }
19 //對每個桶進行排序
20 for(int i = 0; i < bucketArr.size(); i++){
21 Collections.sort(bucketArr.get(i));
22 }
23 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137177.html
標籤：其他