一、排序思想

之前將的計(jì)數(shù)排序，有些局限性，比如數(shù)列最大值和最小值差距不能太大，而且只能排整數(shù)。桶排序就對這些局限性做了彌補(bǔ)。桶排序的思想就是每個桶代表一個區(qū)間范圍，里面可以裝若干個元素。然后對這些桶內(nèi)部進(jìn)行排序，最后遍歷這些桶，那么數(shù)列就是有序的了。

「1. 案例：」

假如現(xiàn)在有如下數(shù)列：

4.5,   0.84,   3.25,   2.18,   0.5

• 首先創(chuàng)建與元素個數(shù)相同的桶，這里就創(chuàng)建5個桶；
• 最后一個桶讓它只包含最大元素，即只包含4.5；
• 最大數(shù)是4.5，最小是0.5，間距是4，除去最后一個桶還有4個桶，所以每個桶間距是1，如下圖：

• 然后開始遍歷原始數(shù)列，把元素放入對應(yīng)的桶中，如下：

• 對每個桶內(nèi)部的元素進(jìn)行排序，如下：

• 最后遍歷所有的桶，輸出的元素就是有序的了。

桶排序的缺點(diǎn)：如果數(shù)據(jù)分布不均衡，比如最大值1000，最小值0.5，剩余元素都是零點(diǎn)幾的，也就是說最后一個桶放最大元素，其他元素都在第一個桶，這樣性能就會下降，并且創(chuàng)建了很多空桶，浪費(fèi)空間。

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

public static void sort(double[] arr){
        if (arr == null || arr.length == 1){
            return;
        }
        int arrNum = arr.length; // 元素個數(shù)
        // 拿到最大數(shù)和最小數(shù)，用來確定間距
        double max = arr[0];
        double min = arr[1];
        for (int i = 0; i < arrNum; i++) {
            max = arr[i] > max ? arr[i] : max;
            min = arr[i] < min ? arr[i] : min;
        }
        double distance = max - min;
        // 創(chuàng)建 arrNum 個桶，桶用linkedList表示，因?yàn)閘inkedList是可重復(fù)的，待排數(shù)列可能有相同的元素
        List<LinkedList<Double>> buckets = new ArrayList<>();
        for (int i = 0; i < arrNum; i++) {
            buckets.add(new LinkedList<>());
        }
        // 遍歷原始數(shù)組，將每個元素放到桶中
        for (int i = 0; i < arrNum; i++) {
            // 判斷該元素應(yīng)該放入哪個桶中：當(dāng)前元素減去最小值，乘以桶數(shù)量減一，再除以最大值減最小，得到的值就是桶編號
            int num = (int)((arr[i] - min) * (arrNum - 1) / (max - min));
            buckets.get(num).add(arr[i]);
        }
        // 對每個桶內(nèi)部進(jìn)行排序
        for (int i = 0; i < buckets.size(); i++) {
            Collections.sort(buckets.get(i));
        }
        // 最后遍歷桶，輸出所有元素
        int i = 0;
        for (LinkedList<Double> bucket : buckets){
            for (double num : bucket){
                arr[i++] = num;
            }
        }
}