前面介紹了一些經(jīng)典排序算法，它們的時(shí)間復(fù)雜度最好是 O(nlogn)，那 如何把百萬(wàn)級(jí)別的訂單根據(jù)金額排序 是不是覺(jué)得可以按照之前學(xué)的歸并排序、快速排序?qū)崿F(xiàn)？功能是可以完成，但是效率太低了。今天「碼哥」帶大家一起玩轉(zhuǎn)特殊場(chǎng)景下的排序算法，在 O(n) 時(shí)間復(fù)雜度的情況下實(shí)現(xiàn)排序。

「碼哥」帶大家學(xué)習(xí)的算法類(lèi)比「超跑型賽車(chē)」，用于特殊場(chǎng)景能實(shí)現(xiàn)飛快速度?？炫?、歸并是經(jīng)濟(jì)實(shí)用型小轎車(chē)。而桶排序、計(jì)數(shù)排序、基數(shù)排序則是賽道上的跑車(chē)競(jìng)速，也叫做線性排序。

來(lái)不及解釋了，快上車(chē)！今天先來(lái)桶排序壓壓驚。

桶排序（Bucket Sort）

顧名思義，會(huì)使用「桶」，核心思想就是 把要排序的的數(shù)據(jù)分到幾個(gè)有序的桶里，每個(gè)桶里面的數(shù)據(jù)在單獨(dú)進(jìn)行排序，所有的桶內(nèi)數(shù)據(jù)排序完成后，再按照桶的順序依次取出，組成的序列就是有序的。

為了桶排序的高效，我們需要做到以下兩點(diǎn)：

1. 在額外空間充足的情況下，盡量增加桶的數(shù)量。
2. 使用的映射函數(shù)能夠把輸入的 n 個(gè)數(shù)據(jù)均勻的分配到 k 個(gè)桶中。

同時(shí)，對(duì)于桶內(nèi)元素的排序，選擇哪一種排序算法對(duì)于性能的影響也至關(guān)重要。

桶排序的基本思想是：把數(shù)組 arr 劃分為n個(gè)大小相同子區(qū)間（桶），每個(gè)子區(qū)間各自排序，最后合并。

為何說(shuō)時(shí)間復(fù)雜度是 O(n) 呢? 我們一探究竟。

如果待排序的數(shù)據(jù)有 n 個(gè)，我們需要將其使用函數(shù)映射均勻的分配到 k 個(gè)桶里面，每個(gè)桶的元素個(gè)數(shù) y = n / k。

接著每個(gè)桶的內(nèi)部使用快排，時(shí)間復(fù)雜度就是 O(y _ logy)， k 個(gè)桶排序的時(shí)間復(fù)雜度就是 O(k _ y _ logy)， 因?yàn)?y = n / k。所以整個(gè)桶排序的時(shí)間復(fù)雜度就是 O(n _ log(n / k))。當(dāng)桶的個(gè)數(shù) k 接近 數(shù)據(jù)個(gè)數(shù) n ，log(n / k) 就是一個(gè)很小的常量，桶排序時(shí)間復(fù)雜度接近 O(n)。

看起來(lái)如此優(yōu)秀，它能代替碼哥之間介紹的 O(nlogn) 復(fù)雜度的排序算法么？

很遺憾，答案是否定的。跑車(chē)能跑的賽道是特殊的，并不能代替家用小轎車(chē)。實(shí)際上它的運(yùn)用場(chǎng)景很苛刻。

1. 要排序的數(shù)據(jù)很容易均勻的劃分成 k 個(gè)桶，并且桶與桶之間有著天然的大小順序。這樣才在實(shí)現(xiàn)在每個(gè)桶內(nèi)的數(shù)據(jù)都排序好了以后不需要再進(jìn)行排序。
2. 數(shù)據(jù)在每個(gè)桶之間都是均勻的分布，假如出現(xiàn)有的桶很多數(shù)有的很少。那桶內(nèi)排序的時(shí)間復(fù)雜度就不是常量級(jí)了，在極端情況下數(shù)據(jù)都劃分到一個(gè)桶里，也就退化成 O(nlogn) 的時(shí)間復(fù)雜度了。

適用場(chǎng)景

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

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

解決思路

一下，對(duì)應(yīng)根據(jù)訂單金額把 10G 訂單數(shù)據(jù)排序也是如此，訂單金額最小是 1 元，最大是 10 萬(wàn)元。我們將所有訂單根據(jù)金額劃分到 100 個(gè)桶里，第一個(gè)桶我們存儲(chǔ)金額在 1 元到 1000 元之內(nèi)的訂單，第二桶存儲(chǔ)金額在 1001 元到 2000 元之內(nèi)的訂單，以此類(lè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ù)了。

代碼實(shí)戰(zhàn)

/**
 * 桶排序：把數(shù)組 arr 劃分為n個(gè)大小相同子區(qū)間（桶），每個(gè)子區(qū)間各自排序，最后合并
 */
public class BucketSort implements LineSort {

    private static final QuickSort quickSort = new QuickSort();

    @Override
    public int[] sort(int[] sourceArray, int bucketSize) {
        // 找出最大、最小值
        int minValue = sourceArray[0];
        int maxValue = sourceArray[1];
        for (int value : sourceArray) {
            minValue = Math.min(minValue, value);
            maxValue = Math.max(maxValue, value);
        }
        // 桶數(shù)量
        int bucketCount = (maxValue - minValue) / bucketSize + 1;
        int[][] buckets = new int[bucketCount][bucketSize];
        // 保存每個(gè)桶的數(shù)組的元素下標(biāo)，默認(rèn)值 0
        int[] indexArr = new int[bucketCount];

        // 將數(shù)組中值分配到各個(gè)桶里
        for (int value : sourceArray) {
            int bucketIndex = (value - minValue) / bucketSize;
            // 當(dāng)前桶的數(shù)組達(dá)到最大值,需要拓容
            if (indexArr[bucketIndex] == buckets[bucketIndex].length) {
                ensureCapacity(buckets, bucketIndex);
            }
            // 將數(shù)據(jù)放到桶中，并且桶對(duì)應(yīng)的數(shù)組下標(biāo) + 1
            buckets[bucketIndex][indexArr[bucketIndex]++] = value;
        }

        // 對(duì)每個(gè)桶進(jìn)行排序，這里使用了快速排序
        int k = 0;
        for (int i = 0; i < buckets.length; i++) {
            if (indexArr[i] == 0) {
                continue;
            }
            // 默認(rèn)容量是 bucketSize, 要根據(jù)實(shí)際桶的容量排序，否則不足 bucketSize 的默認(rèn)值是 0
            quickSort.quickSortInternal(buckets[i], 0, indexArr[i] - 1);
            for (int j = 0; j < indexArr[i]; j++) {
                sourceArray[k++] = buckets[i][j];
            }
        }
        return sourceArray;
    }

    /**
     * 數(shù)組擴(kuò)容,并保存數(shù)據(jù)
     *
     * @param buckets
     * @param bucketIndex
     */
    private void ensureCapacity(int[][] buckets, int bucketIndex) {
        int[] tempArr = buckets[bucketIndex];
        int[] newArr = new int[tempArr.length * 2];
        for (int j = 0; j < tempArr.length; j++) {
            newArr[j] = tempArr[j];
        }
        buckets[bucketIndex] = newArr;
    }

}

單元測(cè)試

生成一百萬(wàn)的數(shù)據(jù)，數(shù)據(jù)范圍 [1, 100000]

@DisplayName("線性排序算法測(cè)試")
public class LineSortTest {

    private static int length = 100;

    private int[] array = new int[length];

    @BeforeEach
    public void beforeEach() {
        Random rand = new Random();

        for (int i = 0; i < length; i++) {
            // 隨機(jī)生成 [1, 1000000] 的數(shù)據(jù)
            array[i] = rand.nextInt(length) + 1;
        }

    }

    @DisplayName("桶排序")
    @Test
    public void testBucketSort() {
        BucketSort bucketSort = new BucketSort();
        // 100 數(shù)據(jù)，10 個(gè)桶
        int[] sort = bucketSort.sort(array, 10);
        System.out.println(Arrays.toString(sort));
    }
}

總結(jié)

如何根據(jù)年齡給 100 萬(wàn)用戶(hù)排序？現(xiàn)在思考題是不是變得非常簡(jiǎn)單了呢？我來(lái)說(shuō)一下我的解決思路。

實(shí)際上，根據(jù)年齡給 100 萬(wàn)用戶(hù)排序，就類(lèi)似按照成績(jī)給 50 萬(wàn)考生排序。我們假設(shè)年齡的范圍最小 1 歲，最大不超過(guò) 120 歲。我們可以遍歷這 100 萬(wàn)用戶(hù)，根據(jù)年齡將其劃分到這 120 個(gè)桶里，然后依次順序遍歷這 120 個(gè)桶中的元素。這樣就得到了按照年齡排序的 100 萬(wàn)用戶(hù)數(shù)據(jù)。

特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒(méi)關(guān)注的小伙伴，可以長(zhǎng)按關(guān)注一下：

長(zhǎng)按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝