大家好，我是 方圓。本文介紹線性排序，即時(shí)間復(fù)雜度為 O(n) 的排序算法，包括桶排序，計(jì)數(shù)排序和基數(shù)排序，它們都不是基于比較的排序算法，大家重點(diǎn)關(guān)注一下這些算法的適用場(chǎng)景。

桶排序

桶排序是分治策略的一個(gè)典型應(yīng)用。它通過(guò)設(shè)置一些具有大小順序的桶，每個(gè)桶對(duì)應(yīng)一個(gè)數(shù)據(jù)范圍，將數(shù)據(jù)平均分配到各個(gè)桶中；然后，在每個(gè)桶內(nèi)部分別執(zhí)行排序；最終按照桶的順序?qū)⑺袛?shù)據(jù)依次取出合并，組成的序列就是有序的了，如下圖所示：

桶排序的算法流程我將其分成三個(gè)步驟：

• 初始化桶：以范圍為 0 - 49 的數(shù)據(jù)為例，分為 5 個(gè)桶

• 分桶：將要排序數(shù)組中的元素加入桶中

• 出桶：該步驟需要在桶中完成排序后，依次出桶合并

    /**
     * 桶排序：指定數(shù)據(jù)范圍為0 - 49，分桶為5個(gè)，每10個(gè)數(shù)為一個(gè)桶
     */
    public void sort(int[] nums) {
        // 聲明5個(gè)桶
        List<ArrayList<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            buckets.add(new ArrayList<>());
        }

        // 數(shù)組元素分桶
        intoBucket(buckets, nums);

        // 出桶
        outOfBucket(buckets, nums);
    }

    /**
     * 分桶
     */
    private void intoBucket(List<ArrayList<Integer>> buckets, int[] nums) {
        for (int num : nums) {
            int bucketIndex = num / 10;
            buckets.get(bucketIndex).add(num);
        }
    }

    /**
     * 出桶
     */
    private void outOfBucket(List<ArrayList<Integer>> buckets, int[] nums) {
        // 出桶覆蓋原數(shù)組值
        int numsIndex = 0;
        for (ArrayList<Integer> bucket : buckets) {
            // 先排序 再出桶
            bucket.sort(Comparator.comparingInt(x -> x));

            for (Integer num : bucket) {
                nums[numsIndex++] = num;
            }
        }
    }

算法特性：

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

• 自適應(yīng)排序：與桶劃分情況和桶內(nèi)使用的排序算法有關(guān)

• 穩(wěn)定排序/非穩(wěn)定排序：與桶內(nèi)使用的排序算法有關(guān)

• 非原地排序

桶排序比較適用于 外部排序，所謂的外部排序就是數(shù)據(jù)存儲(chǔ)在外部磁盤(pán)中，數(shù)據(jù)量很大，但是內(nèi)存又有限，無(wú)法將所有數(shù)據(jù)全部加載進(jìn)來(lái)，比如有 1G 的數(shù)據(jù)需要排序，但是內(nèi)存只有幾百M(fèi)B的情況。我們可以根據(jù)數(shù)據(jù)范圍將其劃分到 N 個(gè)桶中，劃分完成后每個(gè)桶的大小不超過(guò)可用內(nèi)存大小，對(duì)每個(gè)桶內(nèi)的數(shù)據(jù)進(jìn)行排序，排序完成后生成 N 個(gè)小文件，最后我們?cè)賹⑦@ N 個(gè)小文件寫(xiě)入到一個(gè)大文件中即可。如果數(shù)據(jù)在某些范圍內(nèi)并不是均勻分布的話，有些范圍內(nèi)的數(shù)據(jù)特別多，那么這就需要我們?cè)賹?duì)其劃分成更細(xì)粒度的桶，直到滿足內(nèi)存的使用要求，但是這樣我們的桶就不是按照范圍均勻劃分的了。

計(jì)數(shù)排序

計(jì)數(shù)排序是桶排序的一種特殊情況，只是它定義的“桶”的粒度更細(xì)，每個(gè)桶中只包含一個(gè)單位范圍的數(shù)字，那么每個(gè)“桶”內(nèi)的數(shù)值都是相等的。它適合數(shù)據(jù)范圍不大，但數(shù)據(jù)量很大的排序場(chǎng)景，比如高考考生成績(jī)排名，86 萬(wàn)考生，滿分 750 分，需要?jiǎng)澐?751 個(gè)桶，將這些考生的成績(jī)劃分到各個(gè)桶中后，依次取出即可。

看到這里你可能會(huì)覺(jué)得這不就是桶排序嗎？計(jì)數(shù)排序的計(jì)數(shù)體現(xiàn)在哪里呢？別急，我們看下下面這個(gè)排序的例子，簡(jiǎn)單起見(jiàn)，假設(shè)有 8 個(gè)考生，他們的分?jǐn)?shù)為 [2, 5, 3, 0, 2, 3, 0, 3]，分?jǐn)?shù)范圍為 0 ~ 5，那么我們需要?jiǎng)?chuàng)建 6 個(gè)桶，規(guī)定桶中保存的不是對(duì)應(yīng)的元素，而是對(duì)應(yīng)分?jǐn)?shù)元素出現(xiàn)的數(shù)量，并根據(jù)分?jǐn)?shù)將桶中的計(jì)數(shù)值累加，如下圖所示：

我們先看分?jǐn)?shù) 0 的桶，它是該數(shù)據(jù)范圍內(nèi)最小的分?jǐn)?shù)，它的計(jì)數(shù)為 2，根據(jù)計(jì)數(shù)值我們可以確定分?jǐn)?shù)為 0 的兩個(gè)元素占用該數(shù)據(jù)范圍的前兩個(gè)索引位置，所以計(jì)數(shù)表示的是對(duì)應(yīng)數(shù)值的索引位置。我們?cè)倏纯雌渌耐皝?lái)驗(yàn)證一下：可以發(fā)現(xiàn)分?jǐn)?shù) 2 的桶計(jì)數(shù)也為 2，但是前兩個(gè)索引位置已經(jīng)被分?jǐn)?shù) 0 占用了呀，分?jǐn)?shù) 2 的計(jì)數(shù)應(yīng)該是 4 才對(duì)，所以，我們還需要一步操作：疊加前面分?jǐn)?shù)出現(xiàn)的次數(shù)，這樣分?jǐn)?shù) 2 的計(jì)數(shù)值便為 4，可以發(fā)現(xiàn)計(jì)數(shù)值其實(shí)表示的是某數(shù)字占用的第 N 個(gè)索引，如果我們想知道其中分?jǐn)?shù) 2 的索引位置，將計(jì)數(shù)值 4 進(jìn)行減 1 即可，即它的索引值為 3，而且每取完某數(shù)字一次，需要將該計(jì)數(shù)值減 1。排序流程如下：

這樣一步步操作完成之后，最終數(shù)組是有序的。計(jì)數(shù)排序的代碼如下：

    /**
     * 計(jì)數(shù)排序的計(jì)數(shù)體現(xiàn)在小于等于某個(gè)數(shù)出現(xiàn)的次數(shù) - 1 即為該數(shù)在原數(shù)組排序后的位置
     */
    public void sort(int[] nums) {
        if (nums.length <= 1) {
            return;
        }

        // 尋找數(shù)組中的最大值來(lái)以此定義max + 1個(gè)桶
        int max = Arrays.stream(nums).max().getAsInt();

        // 定義桶，索引范圍即數(shù)組值的最大范圍，每個(gè)桶中保存的是該數(shù)字出現(xiàn)的次數(shù)，計(jì)數(shù)排序的計(jì)數(shù)概念出現(xiàn)
        int[] bucket = new int[max + 1];

        // 計(jì)算每個(gè)數(shù)的個(gè)數(shù)在桶中累加
        Arrays.stream(bucket).forEach(x -> bucket[x]++);
        // 依次累加桶中的數(shù)，該數(shù)表示小于等于該索引值的數(shù)量
        for (int i = 1; i < bucket.length; i++) {
            bucket[i] += bucket[i - 1];
        }

        // 創(chuàng)建臨時(shí)數(shù)組來(lái)保存排序結(jié)果值
        int[] res = new int[nums.length];
        // 倒序遍歷原數(shù)組，不改變相同元素的相對(duì)順序
        for (int i = nums.length - 1; i >= 0; i--) {
            // 根據(jù)桶中的 計(jì)數(shù) 找出該數(shù)的索引
            int index = bucket[nums[i]] - 1;
            // 根據(jù)索引在結(jié)果數(shù)組中賦值
            res[index] = nums[i];
            // 該數(shù)分配完成后，需要將桶中的計(jì)數(shù)-1
            bucket[nums[i]]--;
        }

        // 結(jié)果數(shù)組覆蓋原數(shù)組
        System.arraycopy(res, 0, nums, 0, res.length);
    }

基數(shù)排序

基數(shù)排序?qū)Υ判驍?shù)據(jù)是有特殊要求的，需要數(shù)據(jù)可以分割出獨(dú)立的“位”，并且位與位之間要有遞進(jìn)關(guān)系，根據(jù)遞進(jìn)關(guān)系對(duì)每一位進(jìn)行排序，獲得最終排序結(jié)果。

我們先來(lái)看一下使用基數(shù)排序處理 [3, 4, 100, 11, 33] 數(shù)組的過(guò)程：

因?yàn)檎麛?shù)每位取數(shù)范圍為 0 ~ 9，所以創(chuàng)建了 10 個(gè)桶，這 10 個(gè)桶已經(jīng)有了從大到小的順序。排序時(shí)從整數(shù)的個(gè)位開(kāi)始，到最高位終止，排序的輪次為最大整數(shù)的位數(shù)，在每輪排序中，根據(jù)當(dāng)前位數(shù)值大小入桶，完成后再按順序出桶，最終結(jié)果即為排序結(jié)果。代碼如下：

    private void sort(int[] nums) {
        if (nums.length <= 1) {
            return;
        }

        // 1. 整數(shù)的每位取值范圍為 0-9，因此需要?jiǎng)?chuàng)建10個(gè)桶
        Queue<Integer>[] buckets = createBuckets();

        // 2. 獲取基數(shù)排序的執(zhí)行輪次
        int radixRounds = getRadixRounds(nums);

        // 3. 根據(jù)執(zhí)行輪次處理各個(gè)"位"，eg: 第一輪處理個(gè)位...
        for (int round = 1; round <= radixRounds; round++) {
            for (int num : nums) {
                // 獲取所在桶的索引
                int bucketIndex = getBucketIndex(num, round);
                // 進(jìn)桶
                buckets[bucketIndex].offer(num);
            }

            // 出桶賦值，當(dāng)前結(jié)果為根據(jù)當(dāng)前位排序的結(jié)果
            int numsIndex = 0;
            for (Queue<Integer> bucket : buckets) {
                while (!bucket.isEmpty()) {
                    nums[numsIndex++] = bucket.poll();
                }
            }
        }
    }

    /**
     * 創(chuàng)建大小為10的數(shù)組作為桶，每個(gè)桶都是一個(gè)隊(duì)列
     */
    @SuppressWarnings("unchecked")
    private Queue<Integer>[] createBuckets() {
        Queue<Integer>[] buckets = new Queue[10];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new LinkedList<>();
        }

        return buckets;
    }

    /**
     * 獲取基數(shù)排序的執(zhí)行輪次
     */
    private int getRadixRounds(int[] nums) {
        return String.valueOf(Arrays.stream(nums).max().getAsInt()).length();
    }

    /**
     * 獲取該數(shù)所在桶的索引
     */
    private int getBucketIndex(int num, int round) {
        int bucketIndex = 0;

        while (round != 0) {
            bucketIndex = num % 10;
            num /= 10;

            round--;
        }

        return bucketIndex;
    }

基數(shù)排序比較適用于數(shù)據(jù)范圍比較大且位數(shù)相對(duì)均勻的數(shù)據(jù)排序，比如排序手機(jī)號(hào)或者學(xué)號(hào)，它的時(shí)間復(fù)雜度接近于 O(n)。

巨人的肩膀

• 《數(shù)據(jù)結(jié)構(gòu)與算法之美》：第 3.6 章 線性排序：如何根據(jù)年齡給 100 萬(wàn)個(gè)用戶排序

• 《Hello 算法》：第 11.8、11.9 和 11.10 章

• 《算法導(dǎo)論》：第 8 章 線性時(shí)間排序文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-832559.html

到了這里，關(guān)于時(shí)間復(fù)雜度為 O(n) 的排序算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！