C++計數(shù)排序

簡單實現(xiàn)

先來看一個簡單的例子。給定一個長度為 $n$ 的數(shù)組 nums ，其中的元素都是“非負整數(shù)”，計數(shù)排序的整體流程如圖 11-16 所示。

1. 遍歷數(shù)組，找出數(shù)組中的最大數(shù)字，記為 $m$ ，然后創(chuàng)建一個長度為 $m+1$ 的輔助數(shù)組 counter 。
2. 借助 counter 統(tǒng)計 nums 中各數(shù)字的出現(xiàn)次數(shù)，其中 counter[num] 對應(yīng)數(shù)字 num 的出現(xiàn)次數(shù)。統(tǒng)計方法很簡單，只需遍歷 nums（設(shè)當(dāng)前數(shù)字為 num），每輪將 counter[num] 增加 $1$ 即可。
3. 由于 counter 的各個索引天然有序，因此相當(dāng)于所有數(shù)字已經(jīng)被排序好了。接下來，我們遍歷 counter ，根據(jù)各數(shù)字的出現(xiàn)次數(shù)，將它們按從小到大的順序填入 nums 即可。

圖 11-16   計數(shù)排序流程

counting_sort.cpp

/* 計數(shù)排序 */
// 簡單實現(xiàn)，無法用于排序?qū)ο?void countingSortNaive(vector<int> &nums) {
    // 1. 統(tǒng)計數(shù)組最大元素 m
    int m = 0;
    for (int num : nums) {
        m = max(m, num);
    }
    // 2. 統(tǒng)計各數(shù)字的出現(xiàn)次數(shù)
    // counter[num] 代表 num 的出現(xiàn)次數(shù)
    vector<int> counter(m + 1, 0);
    for (int num : nums) {
        counter[num]++;
    }
    // 3. 遍歷 counter ，將各元素填入原數(shù)組 nums
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}

完整實現(xiàn)

細心的同學(xué)可能發(fā)現(xiàn)，如果輸入數(shù)據(jù)是對象，上述步驟 ?3.? 就失效了。假設(shè)輸入數(shù)據(jù)是商品對象，我們想要按照商品價格（類的成員變量）對商品進行排序，而上述算法只能給出價格的排序結(jié)果。

那么如何才能得到原數(shù)據(jù)的排序結(jié)果呢？我們首先計算 counter 的“前綴和”。顧名思義，索引 i 處的前綴和 prefix[i] 等于數(shù)組前 i 個元素之和：

前綴和具有明確的意義，prefix[num] - 1 代表元素 num 在結(jié)果數(shù)組 res 中最后一次出現(xiàn)的索引。這個信息非常關(guān)鍵，因為它告訴我們各個元素應(yīng)該出現(xiàn)在結(jié)果數(shù)組的哪個位置。接下來，我們倒序遍歷原數(shù)組 nums 的每個元素 num ，在每輪迭代中執(zhí)行以下兩步。

1. 將 num 填入數(shù)組 res 的索引 prefix[num] - 1 處。
2. 令前綴和 prefix[num] 減小 $1$ ，從而得到下次放置 num 的索引。

遍歷完成后，數(shù)組 res 中就是排序好的結(jié)果，最后使用 res 覆蓋原數(shù)組 nums 即可。圖 11-17 展示了完整的計數(shù)排序流程。

圖 11-17   計數(shù)排序步驟

計數(shù)排序的實現(xiàn)代碼如下所示。

counting_sort.cpp

/* 計數(shù)排序 */
// 完整實現(xiàn)，可排序?qū)ο?，并且是穩(wěn)定排序
void countingSort(vector<int> &nums) {
    // 1. 統(tǒng)計數(shù)組最大元素 m
    int m = 0;
    for (int num : nums) {
        m = max(m, num);
    }
    // 2. 統(tǒng)計各數(shù)字的出現(xiàn)次數(shù)
    // counter[num] 代表 num 的出現(xiàn)次數(shù)
    vector<int> counter(m + 1, 0);
    for (int num : nums) {
        counter[num]++;
    }
    // 3. 求 counter 的前綴和，將“出現(xiàn)次數(shù)”轉(zhuǎn)換為“尾索引”
    // 即 counter[num]-1 是 num 在 res 中最后一次出現(xiàn)的索引
    for (int i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
    }
    // 4. 倒序遍歷 nums ，將各元素填入結(jié)果數(shù)組 res
    // 初始化數(shù)組 res 用于記錄結(jié)果
    int n = nums.size();
    vector<int> res(n);
    for (int i = n - 1; i >= 0; i--) {
        int num = nums[i];
        res[counter[num] - 1] = num; // 將 num 放置到對應(yīng)索引處
        counter[num]--;              // 令前綴和自減 1 ，得到下次放置 num 的索引
    }
    // 使用結(jié)果數(shù)組 res 覆蓋原數(shù)組 nums
    nums = res;
}

算法特性

• 時間復(fù)雜度 $O(n+m)$ ：涉及遍歷 nums 和遍歷 counter ，都使用線性時間。一般情況下 $n?m$ ，時間復(fù)雜度趨于 $O(n)$ 。
• 空間復(fù)雜度 $O(n+m)$、非原地排序：借助了長度分別為 $n$ 和 $m$ 的數(shù)組 res 和 counter 。
• 穩(wěn)定排序：由于向 res 中填充元素的順序是“從右向左”的，因此倒序遍歷 nums 可以避免改變相等元素之間的相對位置，從而實現(xiàn)穩(wěn)定排序。實際上，正序遍歷 nums 也可以得到正確的排序結(jié)果，但結(jié)果是非穩(wěn)定的。

局限性

看到這里，你也許會覺得計數(shù)排序非常巧妙，僅通過統(tǒng)計數(shù)量就可以實現(xiàn)高效的排序工作。然而，使用計數(shù)排序的前置條件相對較為嚴格。

計數(shù)排序只適用于非負整數(shù)。若想要將其用于其他類型的數(shù)據(jù)，需要確保這些數(shù)據(jù)可以被轉(zhuǎn)換為非負整數(shù)，并且在轉(zhuǎn)換過程中不能改變各個元素之間的相對大小關(guān)系。例如，對于包含負數(shù)的整數(shù)數(shù)組，可以先給所有數(shù)字加上一個常數(shù)，將全部數(shù)字轉(zhuǎn)化為正數(shù)，排序完成后再轉(zhuǎn)換回去即可。

計數(shù)排序適用于數(shù)據(jù)量大但數(shù)據(jù)范圍較小的情況。比如，在上述示例中 $m$ 不能太大，否則會占用過多空間。而當(dāng) $n?m$ 時，計數(shù)排序使用 $O(m)$ 時間，可能比 $O(n\log ?n)$ 的排序算法還要慢。