## **桶排序** 桶排序又叫箱排序，是計數排序的升級版，它的工作原理是將數組分到有限數量的桶子里，然后對每個桶子再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序），最后將各個桶中的數據有序的合并起來。 > 計數排序是桶排序的一種特殊情況，可以把計數排序當成每個桶里只有一個元素的情況。網絡中很多博文寫的桶排序實際上都是計數排序，并非標準的桶排序，要注意辨別。 ## **算法描述** 1. 找出待排序數組中的最大值max、最小值min 2. 我們使用 動態數組ArrayList 作為桶，桶里放的元素也用 ArrayList 存儲。桶的數量為(max-min)/arr.length+1 3. 遍歷數組 arr，計算每個元素 arr\[i\] 放的桶 4. 每個桶各自排序 5. 遍歷桶數組，把排序好的元素放進輸出數組 ## **穩定性** 可以看出，在分桶和從桶依次輸出的過程是穩定的。但是，由于我們在對每個桶進行排序時使用了其他算法，所以，桶排序的穩定性依賴于這一步。如果我們使用了快排，顯然，算法是不穩定的。 ## **適用場景** 桶排序可用于最大最小值相差較大的數據情況，但桶排序要求數據的分布必須均勻，否則可能導致數據都集中到一個桶中。比如\[104,150,123,132,20000\], 這種數據會導致前4個數都集中到同一個桶中。導致桶排序失效。 ## **JAVA代碼實現** ``` 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]); } //桶數 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)); } System.out.println(bucketArr.toString()); } ```