使用C++實現基數排序算法

基數排序算法的C++實現¶

什麼是基數排序？¶

基數排序（Radix Sort）是一種非比較型整數排序算法，它通過按位排序的方式實現。與冒泡排序、快速排序等基於比較的排序不同，基數排序不需要比較元素的大小，而是根據數字的每一位（如個位、十位、百位等）進行排序，最終達到整體有序的效果。

基數排序的基本思想¶

基數排序通常採用最低有效位優先（LSD） 的方式，即從數字的最低位（個位）開始，依次向最高位（如百位、千位）進行排序。每一位排序時，使用穩定的排序算法（如計數排序）來處理當前位上的數字分佈，確保低位排序的結果在高位排序時不被破壞。

實現步驟¶

找出最大數：確定數組中最大數的位數，例如數組中的最大數是802（3位數），則需要處理個位、十位、百位共3位。
按位排序：對每一位（從低位到高位）進行計數排序：
- 統計當前位上每個數字（0-9）出現的次數。
- 根據次數計算每個數字在臨時數組中的位置。
- 從後往前遍歷原數組，將元素按當前位數字放入臨時數組的正確位置，保證穩定性。
- 將臨時數組複製回原數組，完成當前位的排序。

C++代碼實現¶

#include <iostream>
using namespace std;

// 輔助函數：計數排序（按當前位排序）
void countingSort(int arr[], int n, int exp) {
    int output[n];  // 臨時數組存儲排序結果
    int count[10] = {0};  // 計數數組，統計0-9出現的次數

    // 1. 統計當前位上每個數字出現的次數
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % 10;  // 當前位數字
        count[digit]++;
    }

    // 2. 計算前綴和，確定每個數字的位置
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 3. 從後往前遍歷原數組，穩定地放入臨時數組
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];  // 放置到正確位置
        count[digit]--;  // 保證後續元素位置不衝突
    }

    // 4. 將臨時數組結果複製回原數組
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 基數排序主函數
void radixSort(int arr[], int n) {
    // 1. 找到數組中的最大數
    int max_num = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_num) {
            max_num = arr[i];
        }
    }

    // 2. 對每一位（從低位到高位）進行計數排序
    for (int exp = 1; max_num / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

// 測試函數
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前數組：";
    printArray(arr, n);

    radixSort(arr, n);

    cout << "排序後數組：";
    printArray(arr, n);

    return 0;
}

代碼解釋¶

countingSort函數：
- 統計當前位（由exp決定，如exp=1對應個位）上每個數字（0-9）的出現次數。
- 通過前綴和計算每個數字在臨時數組中的位置，確保排序穩定性。
- 從後往前遍歷原數組，將元素按當前位數字放入臨時數組，避免覆蓋已排序元素。
- 將臨時數組結果複製回原數組，完成當前位排序。
radixSort函數：
- 找到數組中的最大數，確定需要處理的最高位。
- 按位（從低位到高位）調用countingSort，處理每一位的排序。

測試結果¶

運行上述代碼，輸出如下：

排序前數組：170 45 75 90 802 24 2 66 
排序後數組：2 24 45 66 75 90 170 802

總結¶

基數排序通過按位分解和計數排序實現，時間複雜度爲 O(d×(n+k))（d爲最大位數，n爲數組長度，k爲基數，通常k=10），適用於整數範圍較大的場景。其核心是利用計數排序的穩定性，確保低位排序結果在高位排序中保持有序。初學者可通過逐步理解每一位的處理過程，掌握基數排序的設計思想。