counting_sort.cpp

// counting_sort.cpp
// -----------------------------------------------------------------
// Counting Sort（計數排序）
//
// 原理：非比較排序。統計每個值出現的次數，
//       再用「前綴和」算出每個值在輸出中的最終位置。
//
// 時間複雜度：O(n + k)，k 為值域大小（max - min + 1）
// 空間複雜度：O(n + k)
// 穩定性：穩定（從後往前放回）
// 限制：只適合「整數且值域不大」的資料；k 太大會爆記憶體。
// 特點：是 Radix Sort 每一輪的子程序。
//
// Compile: g++ -std=c++17 -O2 -Wall -o counting_sort counting_sort.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void countingSort(vector<int>& a) {
    if (a.empty()) return;
    int mn = *min_element(a.begin(), a.end());
    int mx = *max_element(a.begin(), a.end());
    int k = mx - mn + 1;                    // 值域大小

    vector<int> count(k, 0);
    for (int x : a) ++count[x - mn];        // 1. 統計次數

    for (int i = 1; i < k; ++i)             // 2. 前綴和 -> 結束位置
        count[i] += count[i - 1];

    vector<int> out(a.size());
    for (int i = (int)a.size() - 1; i >= 0; --i)   // 3. 從後往前 -> 穩定
        out[--count[a[i] - mn]] = a[i];

    a = move(out);
}

static void printVec(const string& tag, const vector<int>& a) {
    cout << tag;
    for (int x : a) cout << x << " ";
    cout << "\n";
}

int main() {
    vector<vector<int>> tests = {
        {4, 2, 2, 8, 3, 3, 1},
        {5, 2, 9, 1, 5, 6},
        {-3, 5, 0, -1, 2, -3},     // 含負數（用 min 偏移）
        {7, 7, 7},
        {42},
        {},
    };
    for (auto& t : tests) {
        printVec("before: ", t);
        countingSort(t);
        printVec("after : ", t);
        cout << "sorted : " << boolalpha
             << is_sorted(t.begin(), t.end()) << "\n\n";
    }
    return 0;
}