一、定義

桶排序是一種線性時(shí)間的排序算法。

桶排序需要?jiǎng)?chuàng)建若干個(gè)桶來(lái)協(xié)助排序。

每一個(gè)桶（bucket）代表一個(gè)區(qū)間范圍，里面可以承載一個(gè)或多個(gè)元素。

桶排序的第1步，就是創(chuàng)建這些桶，并確定每一個(gè)桶的區(qū)間范圍具體需要建立多少個(gè)桶，

如何確定桶的 區(qū)間范圍，有很多種不同的方式。

我們這里創(chuàng)建的桶數(shù)量等于原始數(shù)列的元素?cái)?shù)量，除最后一個(gè)桶只包含數(shù)列最大值外， 前面各個(gè)桶的區(qū)間按照比例來(lái)確定。

區(qū)間跨度 = （最大值-最小值）/ （桶的數(shù)量 - 1）

二、思路

假設(shè)有一個(gè)非整數(shù)數(shù)列如下： 4.5，0.84，3.25，2.18，0.5

第2步，遍歷原始數(shù)列，把元素對(duì)號(hào)入座放入各個(gè)桶中。

第3步，對(duì)每個(gè)桶內(nèi)部的元素分別進(jìn)行排序（顯然，只有第1個(gè)桶需要排序）

第4步，遍歷所有的桶，輸出所有元素： 0.5，0.84，2.18，3.25，4.5

三、代碼實(shí)現(xiàn)

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>());
        }
        //將每個(gè)元素放入桶中
        for (int i = 0; i < array.length; i++) {

            int num = (int) ((array[i] - min) * (bucketNum - 1) / d);
            bucketList.get(num).add(array[i]);
        }
        //對(duì)每個(gè)桶內(nèi)部進(jìn)行排序
        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));
    }
}

四、復(fù)雜度

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(n)

穩(wěn)定性：穩(wěn)定

五、適用場(chǎng)景

桶排序?qū)σ判驍?shù)據(jù)的要求是非常苛刻的。

首先，要排序的數(shù)據(jù)需要很容易就能劃分成m個(gè)桶，并且，桶與桶之間有著天然的大小順序。這樣每個(gè)桶內(nèi)的數(shù)據(jù)都排序完之后，桶與桶之間的數(shù)據(jù)不需要再進(jìn)行排序。

其次，數(shù)據(jù)在各個(gè)桶之間的分布是比較均勻的。如果數(shù)據(jù)經(jīng)過(guò)桶的劃分之后，有些桶里的數(shù)據(jù)非常多，有些非常少，很不平均，那桶內(nèi)數(shù)據(jù)排序的時(shí)間復(fù)雜度就不是常量級(jí)了。在極端情況下，如果數(shù)據(jù)都被劃分到一個(gè)桶里，那就退化為O(nlogn)的排序算法了。

桶排序比較適合用在外部排序中。所謂的外部排序就是數(shù)據(jù)存儲(chǔ)在外部磁盤中，數(shù)據(jù)量比較大，內(nèi)存有限，無(wú)法將數(shù)據(jù)全部加載到內(nèi)存中。

六、案例

1、需求

我們有10GB的訂單數(shù)據(jù)，我們希望按訂單金額（假設(shè)金額都是正整數(shù)）進(jìn)行排序，但是我們的內(nèi)存有限，只有幾百M(fèi)B，沒(méi)辦法一次性把10GB的數(shù)據(jù)都加載到內(nèi)存中。這個(gè)時(shí)候該怎么辦呢？

2、桶排序解決方案

我們可以先掃描一遍文件，看訂單金額所處的數(shù)據(jù)范圍。假設(shè)經(jīng)過(guò)掃描之后我們得到，訂單金額最小是1元，最大是10萬(wàn)元。我們將所有訂單根據(jù)金額劃分到100個(gè)桶里，第一個(gè)桶我們存儲(chǔ)金額在1元到1000元之內(nèi)的訂單，第二桶存儲(chǔ)金額在1001元到2000元之內(nèi)的訂單，以此類推。每一個(gè)桶對(duì)應(yīng)一個(gè)文件，并且按照金額范圍的大小順序編號(hào)命名（00，01，02...99）。

理想的情況下，如果訂單金額在1到10萬(wàn)之間均勻分布，那訂單會(huì)被均勻劃分到100個(gè)文件中，每個(gè)小文件中存儲(chǔ)大約100MB的訂單數(shù)據(jù)，我們就可以將這100個(gè)小文件依次放到內(nèi)存中，用快排來(lái)排序。等所有文件都排好序之后，我們只需要按照文件編號(hào)，從小到大依次讀取每個(gè)小文件中的訂單數(shù)據(jù)，并將其寫(xiě)入到一個(gè)文件中，那這個(gè)文件中存儲(chǔ)的就是按照金額從小到大排序的訂單數(shù)據(jù)了。

不過(guò)，你可能也發(fā)現(xiàn)了，訂單按照金額在1元到10萬(wàn)元之間并不一定是均勻分布的 ，所以10GB訂單數(shù)據(jù)是無(wú)法均勻地被劃分到100個(gè)文件中的。有可能某個(gè)金額區(qū)間的數(shù)據(jù)特別多，劃分之后對(duì)應(yīng)的文件就會(huì)很大，沒(méi)法一次性讀入內(nèi)存。這又該怎么辦呢？

針對(duì)這些劃分之后還是比較大的文件，我們可以繼續(xù)劃分，比如，訂單金額在1元到1000元之間的比較多，我們就將這個(gè)區(qū)間繼續(xù)劃分為10個(gè)小區(qū)間，1元到100元，101元到200元，201元到300元....901元到1000元。如果劃分之后，101元到200元之間的訂單還是太多，無(wú)法一次性讀入內(nèi)存，那就繼續(xù)再劃分，直到所有的文件都能讀入內(nèi)存為止。?