桶排序又稱箱排序（Bucket sort），是一個排序算法轧膘，工作的原理是將數(shù)組分到有限數(shù)量的桶里鸠信。每個桶再個別排序（可能在使用其他的排序算法），最后依次把各個桶中的記錄列出來便得到了有序序列掩浙。桶排序是基數(shù)排序的一種歸納結果。當要被排序的數(shù)組內的數(shù)值平局分配的時候秸歧，桶排序使用線性時間（）厨姚。但桶排序并不是比較排序，它不受
的時間復雜度影響键菱。
基本思想
桶排序的想法近乎徹底的分治思想谬墙。桶排序假設數(shù)組均勻分布在一個范圍內，并將這一范圍劃分為幾個子范圍（桶）经备。然后利用某種映射函數(shù)拭抬，將待排序的關鍵字
映射到下標為
的同種，那么該關鍵字
就作為
中的元素侵蒙。接著對每個桶的元素進行排序造虎，并將其依次輸出即可得到一個有序的序列。
映射函數(shù)一般采用
纷闺，其中
算凿。
如果要是桶排序更加高效可以注意下面兩點：
- 在額外空間足夠的情況下，增大桶的數(shù)量犁功。
- 使用的影射函數(shù)盡量能夠將輸入的
個數(shù)據(jù)均勻分配到
個桶中氓轰。
- 注意桶內元素排序采用的算法，它對性能的影響至關重要浸卦。
具體的流程為：
- 設置與一個定量的數(shù)組當作空桶署鸡。
- 尋訪序列，并把元素利用映射函數(shù)放入桶中限嫌。
- 對每個非空的桶進行排序靴庆。
- 從非空的同種將元素一次取出得到排列之后的結果。
代碼實現(xiàn)
public class Template {
public void bucketSort(double[] arr) {
int len = arr.length;
ArrayList<LinkedList<Double>> buckets = new ArrayList<>();
for (int i = 0; i < 10; i++) buckets.add(new LinkedList<>());
for (double val : arr) insert(buckets.get(mapping(val)), val);
int ind = 0;
for (LinkedList<Double> bucket : buckets) {
for (Double val : bucket) {
arr[ind++] = val;
}
}
}
/**
* 映射函數(shù)
*
* @param val
* @return
*/
public int mapping(double val) {
return (int) val;
}
public void insert(List<Double> bucket, double val) {
ListIterator<Double> it = bucket.listIterator();
boolean flag = true;
while (it.hasNext()) {
if (val <= it.next()) {
it.previous();
it.add(val);
flag = false;
break;
}
}
if (flag) it.add(val);
}
public static void main(String[] args) {
Template temp = new Template();
double[] arr = {0.12, 2.2, 8.8, 7.6, 7.2, 6.3, 9.0, 1.6, 5.6, 2.4};
temp.bucketSort(arr);
System.out.println(Arrays.toString(arr));
}
}
參考文獻：
