如何確定桶的 區間范圍，有很多種不同的方式。我們這里創建的桶數量等于原始數列的元素數量，除最后一個桶只包含數列最大值外， 前面各個桶的區間按照比例來確定。
一、定義
桶排序是一種線性時間的排序算法。
桶排序需要創建若干個桶來協助排序。
每一個桶（bucket）代表一個區間范圍，里面可以承載一個或多個元素。
桶排序的第1步，就是創建這些桶，并確定每一個桶的區間范圍具體需要建立多少個桶，
如何確定桶的 區間范圍，有很多種不同的方式。
我們這里創建的桶數量等于原始數列的元素數量，除最后一個桶只包含數列最大值外， 前面各個桶的區間按照比例來確定。
區間跨度 = （最大值-最小值）/ （桶的數量 - 1）
二、思路
假設有一個非整數數列如下： 4.5，0.84，3.25，2.18，0.5
第2步，遍歷原始數列，把元素對號入座放入各個桶中。
第3步，對每個桶內部的元素分別進行排序（顯然，只有第1個桶需要排序）
第4步，遍歷所有的桶，輸出所有元素： 0.5，0.84，2.18，3.25，4.5
三、代碼實現
import JAVA.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
public class BucketSort {
public static double[] bucketSort(double[] array) {
double max = 0;
double min = 0;
//獲得最大值和最小值之間的差
for (int i = 0; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
if (array[i] < min) {
min = array[i];
}
}
double d = max - min;
//桶初始化
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>());
}
//將每個元素放入桶中
for (int i = 0; i < array.length; i++) {
int num = (int) ((array[i] - min) * (bucketNum - 1) / d);
bucketList.get(num).add(array[i]);
}
//對每個桶內部進行排序
for (int i = 0; i < bucketList.size(); i++) {
Collections.sort(bucketList.get(i));
}
//輸出全部元素
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 = {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));
}
}
四、復雜度
時間復雜度：O(n)
空間復雜度：O(n)
穩定性：穩定
五、適用場景
桶排序對要排序數據的要求是非常苛刻的。
首先，要排序的數據需要很容易就能劃分成m個桶，并且，桶與桶之間有著天然的大小順序。這樣每個桶內的數據都排序完之后，桶與桶之間的數據不需要再進行排序。
其次，數據在各個桶之間的分布是比較均勻的。如果數據經過桶的劃分之后，有些桶里的數據非常多，有些非常少，很不平均，那桶內數據排序的時間復雜度就不是常量級了。在極端情況下，如果數據都被劃分到一個桶里，那就退化為O(nlogn)的排序算法了。
桶排序比較適合用在外部排序中。所謂的外部排序就是數據存儲在外部磁盤中，數據量比較大，內存有限，無法將數據全部加載到內存中。
六、案例
1、需求
我們有10GB的訂單數據，我們希望按訂單金額（假設金額都是正整數）進行排序，但是我們的內存有限，只有幾百MB，沒辦法一次性把10GB的數據都加載到內存中。這個時候該怎么辦呢？
2、桶排序解決方案
我們可以先掃描一遍文件，看訂單金額所處的數據范圍。假設經過掃描之后我們得到，訂單金額最小是1元，最大是10萬元。我們將所有訂單根據金額劃分到100個桶里，第一個桶我們存儲金額在1元到1000元之內的訂單，第二桶存儲金額在1001元到2000元之內的訂單，以此類推。每一個桶對應一個文件，并且按照金額范圍的大小順序編號命名（00，01，02...99）。
理想的情況下，如果訂單金額在1到10萬之間均勻分布，那訂單會被均勻劃分到100個文件中，每個小文件中存儲大約100MB的訂單數據，我們就可以將這100個小文件依次放到內存中，用快排來排序。等所有文件都排好序之后，我們只需要按照文件編號，從小到大依次讀取每個小文件中的訂單數據，并將其寫入到一個文件中，那這個文件中存儲的就是按照金額從小到大排序的訂單數據了。
不過，你可能也發現了，訂單按照金額在1元到10萬元之間并不一定是均勻分布的 ，所以10GB訂單數據是無法均勻地被劃分到100個文件中的。有可能某個金額區間的數據特別多，劃分之后對應的文件就會很大，沒法一次性讀入內存。這又該怎么辦呢？
針對這些劃分之后還是比較大的文件，我們可以繼續劃分，比如，訂單金額在1元到1000元之間的比較多，我們就將這個區間繼續劃分為10個小區間，1元到100元，101元到200元，201元到300元....901元到1000元。如果劃分之后，101元到200元之間的訂單還是太多，無法一次性讀入內存，那就繼續再劃分，直到所有的文件都能讀入內存為止。?
