計數排序

計數排序會先統計每個整數值出現的次數，再利用這些頻率將數值放到排序後的位置。它不需要逐對比較，但執行時間與記憶體用量取決於數值範圍的寬度。範圍不大時，計數排序很實用；若數值分布稀疏，則可能不切實際。它也會作為基數排序的子程序。主要複雜度界限為 O(n + k)，其中 n 是數值個數，k 是範圍寬度。

計數排序的運作方式

假設輸入包含 n 個整數。找出最小值 min 和最大值 max，再配置 k = max - min + 1 個計數器。以 min 作為偏移量，便能用非負的計數器索引表示負數：

對於從最小值到最大值的輸入範圍，將每個值 x 對應到計數索引 x - min。

對每個輸入值 x，將 count[x - min] 加一。這些計數就是頻率：索引 i 代表值 min + i。接著，將每個計數器加上前一個計數器的值，轉換為累積位置。完成後，每個計數器表示小於或等於其代表值的輸入值總數，也就是該值最後一次出現時在輸出中的位置（從 1 起算）。

若要穩定地排序帶有鍵值的記錄，請從右向左掃描輸入。將每筆記錄放在 count[key - min] - 1，然後將該計數器減一。反向掃描可保留鍵值相同之記錄的原始順序：

依鍵值排序記錄時，放置記錄的過程要從右向左掃描輸入，才能保留相同鍵值記錄的原始順序。

空輸入不需要計數器；在尋找最小值或最大值之前，先回傳空結果即可。基本的整數實作會保留各個值；若要排序記錄，則須在放置時將完整記錄一併放入輸出陣列。

使用計數排序的範例：排序數值

以輸入 (6, 3, 2, 7, 4, 5, 4, 2) 為例。最小值是 2，最大值是 7，範圍寬度為 k = 7 - 2 + 1 = 6。計數器索引 0 到 5 分別代表值 2 到 7。

例如，count[4 - 2] 的值是 2，表示數值 4 出現兩次。累加後，4 對應的計數器值是 5：最後一個 4 應放在從 0 起算的輸出索引 4。將位置減一，就為另一個 4 預留前一格。對其餘數值重複這個放置步驟，便會得到 (2, 2, 3, 4, 4, 5, 6, 7)。

下圖使用標記各異的記錄，展示偏移量、頻率計數、累積位置與反向放置之間的關係。範例包含負鍵值，也顯示鍵值相同的記錄會保留輸入中的原始順序。

示意圖：範圍 -1 到 4 對應六個計數索引；頻率轉為累積位置後，反向放置會讓 (4,A) 在輸出中排於 (4,C) 之前。

在 C++ 中實作計數排序

這個完整的 C++ 範例會回傳新的向量，透過偏移索引支援帶正負號的整數，並在尋找範圍之前處理空向量。範例使用標準容器，而非可變長度陣列。

執行此範例：
本節中的程式碼以及顯示的標籤或輸出仍為英文。

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

std::vector<int> countingSort(const std::vector<int>& values) {
    if (values.size() == 0) {
        return {};
    }

    const auto bounds = std::minmax_element(values.begin(), values.end());
    const long long minValue = *bounds.first;
    const long long maxValue = *bounds.second;
    const std::size_t range = static_cast<std::size_t>(maxValue - minValue + 1);
    std::vector<std::size_t> count(range, 0);

    for (int value : values) {
        const std::size_t index = static_cast<std::size_t>(value - minValue);
        ++count[index];
    }

    for (std::size_t i = 1; i < count.size(); ++i) {
        count[i] += count[i - 1];
    }

    std::vector<int> output(values.size());
    for (std::size_t i = values.size(); i-- > 0;) {
        const int value = values[i];
        const std::size_t index = static_cast<std::size_t>(value - minValue);
        output[--count[index]] = value;
    }
    return output;
}

int main() {
    const std::vector<int> input{6, 3, 2, 7, 4, 5, 4, 2};
    const std::vector<int> sorted = countingSort(input);

    std::cout << "Input: ";
    for (int value : input) {
        std::cout << value << ' ';
    }
    std::cout << "\nSorted: ";
    for (int value : sorted) {
        std::cout << value << ' ';
    }
    std::cout << '\n';
}

編譯並執行後，此範例會印出輸入值和排序結果。程式碼與輸出中顯示的 Input: 和 Sorted: 標籤仍為英文。此實作排序的是整數；若要穩定地排序記錄，請在計算出的位置將完整記錄存入 output，而非只存入其鍵值。

計數排序的複雜度與適用時機

尋找範圍、計數、累加位置與放置數值，各自需要與對應輸入或範圍成線性關係的時間。總時間為 O(n + k)。計數器與輸出向量所需的輔助空間也為 O(n + k)。此處 k = max - min + 1，因此成本取決於最大值與最小值之間的距離，而不只是實際出現了多少種數值。

當數值為整數，且範圍小到足以配置 k 個計數器並容納 n 個項目的輸出時，可使用計數排序。例如，大量分數若來自緊湊且固定的範圍，通常很適合使用此演算法。若少量輸入分散在極大的範圍內，即使大多數數值從未出現，也可能耗費過多記憶體與初始化時間；此時比較排序或基數排序可能更合適。計數器向量必須能放入可用記憶體，因此配置前應先估算範圍寬度。