桶排序又稱箱排序（Bucket sort），是一個(gè)排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶里。每個(gè)桶再個(gè)別排序（可能在使用其他的排序算法），最后依次把各個(gè)桶中的記錄列出來便得到了有序序列。桶排序是基數(shù)排序的一種歸納結(jié)果。當(dāng)要被排序的數(shù)組內(nèi)的數(shù)值平局分配的時(shí)候，桶排序使用線性時(shí)間（）。但桶排序并不是比較排序，它不受的時(shí)間復(fù)雜度影響。

基本思想

桶排序的想法近乎徹底的分治思想。桶排序假設(shè)數(shù)組均勻分布在一個(gè)范圍內(nèi)，并將這一范圍劃分為幾個(gè)子范圍（桶）。然后利用某種映射函數(shù)，將待排序的關(guān)鍵字映射到下標(biāo)為的同種，那么該關(guān)鍵字就作為中的元素。接著對每個(gè)桶的元素進(jìn)行排序，并將其依次輸出即可得到一個(gè)有序的序列。

映射函數(shù)一般采用，其中。

如果要是桶排序更加高效可以注意下面兩點(diǎn)：

1. 在額外空間足夠的情況下，增大桶的數(shù)量。
2. 使用的影射函數(shù)盡量能夠?qū)⑤斎氲?img class="math-inline" src="https://math.jianshu.com/math?formula=n" alt="n" mathimg="1">個(gè)數(shù)據(jù)均勻分配到個(gè)桶中。
3. 注意桶內(nèi)元素排序采用的算法，它對性能的影響至關(guān)重要。

具體的流程為：

1. 設(shè)置與一個(gè)定量的數(shù)組當(dāng)作空桶。
2. 尋訪序列，并把元素利用映射函數(shù)放入桶中。
3. 對每個(gè)非空的桶進(jìn)行排序。
4. 從非空的同種將元素一次取出得到排列之后的結(jié)果。

代碼實(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));
    }
}

參考文獻(xiàn)：

1. 【算法】排序算法之桶排序
2. Java 桶排序，詳細(xì)分析