您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

演算法實作筆記：基數排序（Radix Sort）原理與 C 語言實作

編輯：關於C

什麼是基數排序？

基數排序是一種非比較型、穩定的整數排序演算法。它不直接比較元素大小，而是將整數拆解為各位數字（個位、十位、百位……），從最低有效位（LSD）開始，依序對每一位進行穩定排序（通常用計數排序），最終得到有序序列。適用於範圍已知、位數固定的整數（含負數）。

核心思想：逐位穩定排序

以十進制為例，對陣列 {12, 104, 13, 7, 9} 排序：

個位排序：12, 13, 104, 7, 9（按 2,3,4,7,9）
十位排序：104, 7, 9, 12, 13（按 0,0,0,1,1；同十位者保持上輪相對順序）
百位排序：7, 9, 12, 13, 104（按 0,0,0,0,1）

關鍵在於穩定性：同一位數字相同時，必須保持上一輪的相對順序，這才能保證多輪排序後整體有序。

程式碼架構設計

本實作採用「三步走」模組化設計：

extract_digit()：將原始陣列就地轉換為當前權重位的數字（0~9 或 -9~9 支援負數），並回傳是否還有非零位（決定是否繼續下一輪）。
counting_sort_digit()：對提取出的位數字陣列執行計數排序，結果寫入暫存陣列。
reorder_by_digit()：根據排序後的位數字陣列，將原始資料重新排序（同樣需穩定）。

關鍵函數實作

1. 位數提取與終止判斷


// 就地將 array 轉為第 weight 位（1=個位, 2=十位...）的數字
// 回傳 1 表示還有非零位，需繼續；0 表示全為 0，排序結束
int extract_digit(int array[], int len, int weight) {
    int divisor = 1;
    for (int i = 0; i < weight; ++i) divisor *= 10;

    int has_non_zero = 0;
    for (int i = 0; i < len; ++i) {
        // 支援負數：C99 餘數符號跟隨被除數，這裡統一映射到 -9..9
        int digit = (array[i] % divisor) / (divisor / 10);
        array[i] = digit;
        if (digit != 0) has_non_zero = 1;
    }
    return has_non_zero;
}

2. 位數字計數排序（穩定）


// 對 digits[0..len-1] 做計數排序，結果存入 output
// digits 範圍假設為 -9..9（共 19 個桶）
void counting_sort_digit(int digits[], int len, int output[]) {
    const int BUCKETS = 19;
    int count[BUCKETS] = {0};
    const int OFFSET = 9;  // 將 -9..9 映射到 0..18

    // 統計頻次
    for (int i = 0; i < len; ++i) count[digits[i] + OFFSET]++;

    // 累積和（穩定排序關鍵：從後向前填入）
    for (int i = 1; i < BUCKETS; ++i) count[i] += count[i-1];

    for (int i = len - 1; i >= 0; --i) {
        int idx = digits[i] + OFFSET;
        output[--count[idx]] = digits[i];
    }
}

3. 依位數字重排原始資料


// 根據排序後的 digits 陣列，將原始 data 重新排序
// 同樣採用從後向前掃描以保持穩定
void reorder_by_digit(int data[], const int digits[], int sorted_digits[],
                      int len, int weight) {
    int divisor = 1;
    for (int i = 0; i < weight; ++i) divisor *= 10;

    // 建立 digits 值 -> 原始索引的多重映射（簡化版：線性搜尋+標記）
    // 實際工程建議用隊列陣列或索引陣列優化至 O(n)
    int used[len];
    memset(used, 0, sizeof(used));

    for (int i = 0; i < len; ++i) {
        int target = sorted_digits[i];
        for (int j = 0; j < len; ++j) {
            if (!used[j] && (data[j] % divisor) / (divisor/10) == target) {
                sorted_digits[i] = data[j];  // 暫存到 sorted_digits
                used[j] = 1;
                break;
            }
        }
    }
    memcpy(data, sorted_digits, len * sizeof(int));
}

4. 主排序流程


void radix_sort(int array[], int len) {
    if (!array || len == 0) return;

    int *digits = malloc(len * sizeof(int));
    int *sorted_digits = malloc(len * sizeof(int));
    int *temp_data = malloc(len * sizeof(int));
    memcpy(temp_data, array, len * sizeof(int));

    int weight = 1;
    while (1) {
        memcpy(digits, temp_data, len * sizeof(int));
        if (!extract_digit(digits, len, weight)) break;

        counting_sort_digit(digits, len, sorted_digits);
        reorder_by_digit(temp_data, digits, sorted_digits, len, weight);

        weight++;
    }
    memcpy(array, temp_data, len * sizeof(int));
    free(digits);
    free(sorted_digits);
    free(temp_data);
}

複雜度與適用場景

指標	數值
時間複雜度	O(d·(n+b))，d=位數，b=基數（10 或 19）
空間複雜度	O(n+b)
穩定性	穩定
適用資料	整數（含負數）、定長字串、定點數