radix_sort.cpp

// radix_sort.cpp
// -----------------------------------------------------------------
// Radix Sort（基數排序，LSD：由最低位開始）
//
// 原理：非比較排序。把整數按「位數」逐輪排序：
//       先按個位穩定排序，再按十位、百位……
//       因為每輪都穩定，前面位的次序得以保留。
//
// 時間複雜度：O(d * (n + b))，d 為位數、b 為基數（本檔 b=10 與 b=256）
// 空間複雜度：O(n + b)
// 穩定性：穩定
// 限制：適合整數 / 定長字串；每輪需要穩定子排序（計數排序）。
//
// Compile: g++ -std=c++17 -O2 -Wall -o radix_sort radix_sort.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 依「第 exp 位」做穩定計數排序（base 10）
static void countingByDigit(vector<int>& a, int exp) {
    int n = (int)a.size();
    vector<int> out(n), count(10, 0);
    for (int x : a) ++count[(x / exp) % 10];
    for (int i = 1; i < 10; ++i) count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; --i)
        out[--count[(a[i] / exp) % 10]] = a[i];
    a = move(out);
}

// 非負整數版本
void radixSortNonNegative(vector<int>& a) {
    if (a.empty()) return;
    int mx = *max_element(a.begin(), a.end());
    for (int exp = 1; mx / exp > 0; exp *= 10)
        countingByDigit(a, exp);
}

// 含負數版本：負數與非負數分開排，負數取絕對值排序後反轉
void radixSort(vector<int>& a) {
    vector<int> neg, pos;
    for (int x : a) (x < 0 ? neg : pos).push_back(x < 0 ? -x : x);
    radixSortNonNegative(neg);
    radixSortNonNegative(pos);
    a.clear();
    for (int i = (int)neg.size() - 1; i >= 0; --i) a.push_back(-neg[i]);
    for (int x : pos) a.push_back(x);
}

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 = {
        {170, 45, 75, 90, 802, 24, 2, 66},
        {5, 2, 9, 1, 5, 6},
        {-5, 3, -2, 8, 0, -9, 1},   // 含負數
        {1000000, 1, 100, 10000},
        {42},
        {},
    };
    for (auto& t : tests) {
        printVec("before: ", t);
        radixSort(t);
        printVec("after : ", t);
        cout << "sorted : " << boolalpha
             << is_sorted(t.begin(), t.end()) << "\n\n";
    }
    return 0;
}