點擊上方「程序人生」，選擇「置頂公眾號」
第一時間關注程序猿（媛）身邊的故事
作者
小灰
已獲原作者授權，如需轉載，請聯繫原作者。
————— 第二天 —————
————————————
讓我們先來回顧一下計數排序：
計數排序需要根據原始數列的取值範圍，創建一個統計數組，用來統計原始數列中每一個可能的整數值所出現的次數。
原始數列中的整數值，和統計數組的下標是一一對應的，以數列的最小值作為偏移量。比如原始數列的最小值是90， 那麼整數95對應的統計數組下標就是 95-90 = 5。
那麼，桶排序當中所謂的「桶」，又是什麼概念呢？
每一個桶（bucket）代表一個區間範圍，裡面可以承載一個或多個元素。桶排序的第一步，就是創建這些桶，確定每一個桶的區間範圍：
具體建立多少個桶，如何確定桶的區間範圍，有很多不同的方式。我們這裡創建的桶數量等於原始數列的元素數量，除了最後一個桶只包含數列最大值，前面各個桶的區間按照比例確定。
區間跨度 = （最大值-最小值）/ （桶的數量 - 1）
第二步，遍歷原始數列，把元素對號入座放入各個桶中：
第三步，每個桶內部的元素分別排序（顯然，只有第一個桶需要排序）：
第四步，遍歷所有的桶，輸出所有元素：
0.5，0.84，2.18，3.25，4.5
到此為止，排序結束。
public static double[] bucketSort(double[] array){
//1.得到數列的最大值和最小值，並算出差值d
double max = array[0];
double min = array[0];
for(int i=1; i<array.length; i++) {
if(array[i] > max) {
max = array[i];
}
if(array[i] < min) {
min = array[i];
}
}
double d = max - min;
//2.初始化桶
int bucketNum = array.length;
ArrayList<LinkedList<Double>> bucketList = new ArrayList<LinkedList<Double>>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketList.add(new LinkedList<Double>());
}
//3.遍歷原始數組，將每個元素放入桶中
for(int i = 0; i < array.length; i++){
int num = (int)((array[i] - min) * (bucketNum-1) / d);
bucketList.get(num).add(array[i]);
}
//4.對每個通內部進行排序
for(int i = 0; i < bucketList.size(); i++){
//JDK底層採用了歸併排序或歸併的優化版本
Collections.sort(bucketList.get(i));
}
//5.輸出全部元素
double[] sortedArray = new double[array.length];
int index = 0;
for(LinkedList<Double> list : bucketList){
for(double element : list){
sortedArray[index] = element;
index++;
}
}
return sortedArray;
}
public static void main(String[] args) {
double[] array = new double[] {4.12,6.421,0.0023,3.0,2.123,8.122,4.12, 10.09};
double[] sortedArray = bucketSort(array);
System.out.println(Arrays.toString(sortedArray));
}
代碼中，所有的桶保存在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）。
有關計數排序的知識，可以看看這一篇漫畫：
漫畫：什麼是計數排序？
點擊文末閱讀全文，看『程序人生』其他精彩文章推薦
「若你有原創文章想與大家分享，歡迎投稿。」
加編輯微信ID，備註#投稿#：
程序 丨 druidlost
小七 丨 duoshangshuang
推薦閱讀：
print_r('點個讚吧')；
var_dump('點個讚吧')；
NSLog(@"點個讚吧！")
System.out.println("點個讚吧!");
console.log("點個讚吧!");
print("點個讚吧!");
printf("點個讚吧!\n");
cout << "點個讚吧!" << endl;
Console.WriteLine("點個讚吧!");
fmt.Println("點個讚吧!")
Response.Write("點個讚吧")；
alert（』點個讚吧』）