C++桶排序

前述的幾種排序算法都屬于“基于比較的排序算法”，它們通過(guò)比較元素間的大小來(lái)實(shí)現(xiàn)排序。此類排序算法的時(shí)間復(fù)雜度無(wú)法超越 O(nlog?n) 。接下來(lái)，我們將探討幾種“非比較排序算法”，它們的時(shí)間復(fù)雜度可以達(dá)到線性階。

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

11.8.1   算法流程?

考慮一個(gè)長(zhǎng)度為 n 的數(shù)組，元素是范圍 [0,1) 的浮點(diǎn)數(shù)。桶排序的流程如圖 11-13 所示。

1. 初始化 k 個(gè)桶，將 n 個(gè)元素分配到 k 個(gè)桶中。
2. 對(duì)每個(gè)桶分別執(zhí)行排序（本文采用編程語(yǔ)言的內(nèi)置排序函數(shù)）。
3. 按照桶的從小到大的順序，合并結(jié)果。

圖 11-13   桶排序算法流程

bucket_sort.cpp

/* 桶排序 */
void bucketSort(vector<float> &nums) {
    // 初始化 k = n/2 個(gè)桶，預(yù)期向每個(gè)桶分配 2 個(gè)元素
    int k = nums.size() / 2;
    vector<vector<float>> buckets(k);
    // 1. 將數(shù)組元素分配到各個(gè)桶中
    for (float num : nums) {
        // 輸入數(shù)據(jù)范圍 [0, 1)，使用 num * k 映射到索引范圍 [0, k-1]
        int i = num * k;
        // 將 num 添加進(jìn)桶 bucket_idx
        buckets[i].push_back(num);
    }
    // 2. 對(duì)各個(gè)桶執(zhí)行排序
    for (vector<float> &bucket : buckets) {
        // 使用內(nèi)置排序函數(shù)，也可以替換成其他排序算法
        sort(bucket.begin(), bucket.end());
    }
    // 3. 遍歷桶合并結(jié)果
    int i = 0;
    for (vector<float> &bucket : buckets) {
        for (float num : bucket) {
            nums[i++] = num;
        }
    }
}

11.8.2   算法特性

• 時(shí)間復(fù)雜度 $O(n+k)$ ：假設(shè)元素在各個(gè)桶內(nèi)平均分布，那么每個(gè)桶內(nèi)的元素?cái)?shù)量為 $\frac{n}{k}$ 。假設(shè)排序單個(gè)桶使用 $O(\frac{n}{k}\log ?\frac{n}{k})$ 時(shí)間，則排序所有桶使用 $O(n\log ?\frac{n}{k})$ 時(shí)間。當(dāng)桶數(shù)量 $k$ 比較大時(shí)，時(shí)間復(fù)雜度則趨向于 $O(n)$ 。合并結(jié)果時(shí)需要遍歷所有桶和元素，花費(fèi) $O(n+k)$ 時(shí)間。
• 自適應(yīng)排序：在最壞情況下，所有數(shù)據(jù)被分配到一個(gè)桶中，且排序該桶使用 $O(n^2)$ 時(shí)間。
• 空間復(fù)雜度 $O(n+k)$、非原地排序：需要借助 $k$ 個(gè)桶和總共 $n$ 個(gè)元素的額外空間。
• 桶排序是否穩(wěn)定取決于排序桶內(nèi)元素的算法是否穩(wěn)定。

11.8.3   如何實(shí)現(xiàn)平均分配

桶排序的時(shí)間復(fù)雜度理論上可以達(dá)到 O(n) ，關(guān)鍵在于將元素均勻分配到各個(gè)桶中，因?yàn)閷?shí)際數(shù)據(jù)往往不是均勻分布的。例如，我們想要將淘寶上的所有商品按價(jià)格范圍平均分配到 10 個(gè)桶中，但商品價(jià)格分布不均，低于 100 元的非常多，高于 1000 元的非常少。若將價(jià)格區(qū)間平均劃分為 10 份，各個(gè)桶中的商品數(shù)量差距會(huì)非常大。

為實(shí)現(xiàn)平均分配，我們可以先設(shè)定一個(gè)大致的分界線，將數(shù)據(jù)粗略地分到 3 個(gè)桶中。分配完畢后，再將商品較多的桶繼續(xù)劃分為 3 個(gè)桶，直至所有桶中的元素?cái)?shù)量大致相等。

如圖 11-14 所示，這種方法本質(zhì)上是創(chuàng)建一個(gè)遞歸樹(shù)，目標(biāo)是讓葉節(jié)點(diǎn)的值盡可能平均。當(dāng)然，不一定要每輪將數(shù)據(jù)劃分為 3 個(gè)桶，具體劃分方式可根據(jù)數(shù)據(jù)特點(diǎn)靈活選擇。

圖 11-14   遞歸劃分桶

如果我們提前知道商品價(jià)格的概率分布，則可以根據(jù)數(shù)據(jù)概率分布設(shè)置每個(gè)桶的價(jià)格分界線。值得注意的是，數(shù)據(jù)分布并不一定需要特意統(tǒng)計(jì)，也可以根據(jù)數(shù)據(jù)特點(diǎn)采用某種概率模型進(jìn)行近似。

如圖 11-15 所示，我們假設(shè)商品價(jià)格服從正態(tài)分布，這樣就可以合理地設(shè)定價(jià)格區(qū)間，從而將商品平均分配到各個(gè)桶中。

圖 11-15   根據(jù)概率分布劃分桶