基數排序法 Radix Sort

C++ 基數排序法參考程式

這裡示範 LSD（Least Significant Digit）版本，從個位數開始一路排到最高位數。

• 每一輪根據 exp（1、10、100...）抽出當前位數。
• 使用穩定的 counting sort 進行當前位數排序。
• 當所有位數都處理完，整個陣列就完成排序。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void countingSortByDigit(vector<int>& arr, int exp) {
    int n = static_cast<int>(arr.size());
    vector<int> output(n);
    int count[10] = {0};

    for (int x : arr) {
        int digit = (x / exp) % 10;
        count[digit]++;
    }

    for (int i = 1; i < 10; ++i) {
        count[i] += count[i - 1];
    }

    for (int i = n - 1; i >= 0; --i) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    for (int i = 0; i < n; ++i) {
        arr[i] = output[i];
    }
}

void radixSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());

    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
}

int main() {
    vector<int> data = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(data);

    cout << "排序結果: ";
    for (int x : data) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}