「演算法」什麼是桶排序
點擊上方"java全棧技術"關注，每天學習一個java知識點
原創： 小灰
————— 第二天 —————
————————————
讓我們先來回顧一下計數排序：
計數排序需要根據原始數列的取值範圍，創建一個統計數組，用來統計原始數列中每一個可能的整數值所出現的次數。
原始數列中的整數值，和統計數組的下標是一一對應的，以數列的最小值作為偏移量。比如原始數列的最小值是90， 那麼整數95對應的統計數組下標就是 95-90 = 5。
那麼，桶排序當中所謂的「桶」，又是什麼概念呢？
每一個桶（bucket）代表一個區間範圍，裡面可以承載一個或多個元素。桶排序的第一步，就是創建這些桶，確定每一個桶的區間範圍：
具體建立多少個桶，如何確定桶的區間範圍，有很多不同的方式。我們這裡創建的桶數量等於原始數列的元素數量，除了最後一個桶只包含數列最大值，前面各個桶的區間按照比例確定。
區間跨度 = （最大值-最小值）/ （桶的數量 - 1）
第二步，遍歷原始數列，把元素對號入座放入各個桶中：
第三步，每個桶內部的元素分別排序（顯然，只有第一個桶需要排序）：
第四步，遍歷所有的桶，輸出所有元素：
0.5，0.84，2.18，3.25，4.5
到此為止，排序結束。
代碼中，所有的桶保存在ArrayList集合當中，每一個桶被定義成一個鏈表（LinkedList<Double>），這樣便於在尾部插入元素。
定位元素屬於第幾個桶，是按照比例來定位：
(array[i] - min) * (bucketNum-1) / d
同時，代碼使用了JDK的集合工具類Collections.sort來為桶內部的元素進行排序。Collections.sort底層採用的是歸併排序或Timsort，小夥伴們可以簡單地把它們當做是一種時間複雜度 O（nlogn）的排序。
假設原始數列有n個元素，分成m個桶（我們採用的分桶方式 m=n），平均每個桶的元素個數為n/m。
下面我們來逐步分析演算法複雜度：
第一步求數列最大最小值，運算量為n。
第二步創建空桶，運算量為m。
第三步遍歷原始數列，運算量為n。
第四步在每個桶內部做排序，由於使用了O（nlogn）的排序演算法，所以運算量為 n/m * log(n/m ) * m。
第五步輸出排序數列，運算量為n。
加起來，總的運算量為 3n+m+ n/m * log(n/m ) * m = 3n+m+n(logn-logm) 。
去掉係數，時間複雜度為：
O(n+m+n(logn-logm)）
至於空間複雜度就很明顯了：
空桶佔用的空間 + 數列在桶中佔用的空間 = O（m+n）。
