桶排序及其應用
- 2019 年 11 月 6 日
- 筆記
一、思想
一句話總結：
劃分多個範圍相同的區間，每個自區間自排序，最後合併。
桶排序是計數排序的擴展版本，計數排序可以看成每個桶只存儲相同元素，而桶排序每個桶存儲一定範圍的元素，通過映射函數，將待排序數組中的元素映射到各個對應的桶中，對每個桶中的元素進行排序，最後將非空桶中的元素逐個放入原序列中。
桶排序需要盡量保證元素分散均勻，否則當所有數據集中在同一個桶中時，桶排序失效。
二、圖解過程
三、核心代碼
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)); } // 將桶中的元素賦值到原序列 int index = 0; for(int i = 0; i < bucketArr.size(); i++){ for(int j = 0; j < bucketArr.get(i).size(); j++){ arr[index++] = bucketArr.get(i).get(j); } } }
四、複雜度分析
時間複雜度：O(N + C) 對於待排序序列大小為 N，共分為 M 個桶，主要步驟有：
N 次循環，將每個元素裝入對應的桶中
M 次循環，對每個桶中的數據進行排序（平均每個桶有 N/M 個元素）
一般使用較為快速的排序算法，時間複雜度為 O(NlogN)O(NlogN)O(NlogN)，實際的桶排序過程是以鏈表形式插入的。
整個桶排序的時間複雜度為：
O(N)+O(M∗(N/M∗log(N/M)))=O(N∗(log(N/M)+1))O(N)+O(M*(N/M*log(N/M)))=O(N*(log(N/M)+1))O(N)+O(M∗(N/M∗log(N/M)))=O(N∗(log(N/M)+1))
當 N = M 時，複雜度為 O(N)O(N)O(N)
額外空間複雜度：O(N + M)
五、穩定性分析
桶排序的穩定性取決於桶內排序使用的算法。
六、實際案例
案例一：
一年的全國高考考生人數為500 萬，分數使用標準分，最低100 ，最高900 ，沒有小數，要求對這500 萬元素的數組進行排序。
分析：對500W數據排序，如果基於比較的先進排序，平均比較次數為O(5000000*log5000000)≈1.112億。但是我們發現，這些數據都有特殊的條件： 100=<score<=900。那麼我們就可以考慮桶排序這樣一個「投機取巧」的辦法、讓其在毫秒級別就完成500萬排序。
方法：創建801(900-100)個桶。將每個考生的分數丟進f(score)=score-100的桶中。這個過程從頭到尾遍歷一遍數據只需要500W次。然後根據桶號大小依次將桶中數值輸出，即可以得到一個有序的序列。而且可以很容易的得到100分有***人，501分有***人。
實際上，桶排序對數據的條件有特殊要求，如果上面的分數不是從100-900，而是從0-2億，那麼分配2億個桶顯然是不可能的。所以桶排序有其局限性，適合元素值集合併不大的情況。
案例二：
在一個文件中有 10G 個整數，亂序排列，要求找出中位數。
內存限制為 2G。只寫出思路即可（內存限制為 2G的意思就是，可以使用2G的空間來運行程序，而不考慮這台機器上的其他軟件的佔用內存）。這問題可以使用桶排序，當然還有其他更好的方案，下次再講。
