基數排序（LSD）原理與支援負數的 C 實現

算法核心

基數排序（Radix Sort）是非比較型整數排序，按「個位→十位→百位…」依次穩定排序。關鍵在於穩定性：同一位數相同元素，相對順序保持上一輪結果。

流程示例

輸入：12, 104, 13, 7, 9

1. 個位排序：12, 13, 104, 7, 9 (2,3,4,7,9)
2. 十位排序：104, 7, 9, 12, 13 (0,0,0,1,1) — 7,9 保持上輪順序
3. 百位排序：7, 9, 12, 13, 104 (0,0,0,0,1)

關鍵挑戰：負數處理

標準 LSD 僅處理非負整數。本實現將餘數範圍擴展至 [-9, 9]，負數個位為負，從而自然支援負數排序。

模組化代碼結構

1. 提取當前位數值 pre_process_data

// 將 array 中每個元素替換為其第 weight 位數值 (1=個位, 2=十位...)
// 返回 1 表示仍有非零位，0 表示所有高位皆為 0（排序結束）
int pre_process_data(int array[], int length, int weight) {
    int divisor = 1;
    for (int i = 0; i < weight; ++i) divisor *= 10;

    int has_nonzero = 0;
    for (int i = 0; i < length; ++i) {
        // 負數取模在 C99 中結果為負，符合需求
        array[i] = (array[i] % divisor) / (divisor / 10);
        if (array[i] != 0) has_nonzero = 1;
    }
    return has_nonzero;
}

2. 計數排序當前位 sort_for_basic_number

// 對 -9..9 範圍的位值進行穩定計數排序
void sort_for_basic_number(int digit_arr[], int length, int buffer[]) {
    int count[19] = {0};      // 索引 0 對應 -9, 索引 9 對應 0, 索引 18 對應 9
    int offset = 9;

    // 統計頻次
    for (int i = 0; i < length; ++i)
        ++count[digit_arr[i] + offset];

    // 累積計數 → 目標位置
    for (int i = 1; i < 19; ++i)
        count[i] += count[i - 1];

    // 從後向前填入 buffer 以保證穩定性
    for (int i = length - 1; i >= 0; --i) {
        int d = digit_arr[i];
        buffer[--count[d + offset]] = d;
    }

    // 複製回 digit_arr
    for (int i = 0; i < length; ++i)
        digit_arr[i] = buffer[i];
}

3. 根據位值排序原始數據 sort_data_by_basic_number

// 依據已排序的 digit_arr，調整原始 data 陣列順序
void sort_data_by_basic_number(int data[], const int digit_arr[],
                               int buffer[], int length, int weight) {
    int divisor = 1;
    for (int i = 0; i < weight; ++i) divisor *= 10;

    // 建立 (原始值, 位值) 配對索引
    // 這裡簡化：遍歷 data，找到匹配的 digit_arr 元素（標記已用 -10）
    // 實際工程中建議用結構體或索引陣列，此處為教學演示
    for (int i = 0; i < length; ++i) {
        for (int j = 0; j < length; ++j) {
            if (digit_arr[j] != -10 &&
                data[i] == (digit_arr[j] % divisor) / (divisor / 10)) {
                buffer[i] = data[j];
                digit_arr[j] = -10; // 標記已用
                break;
            }
        }
    }
    for (int i = 0; i < length; ++i)
        data[i] = buffer[i];
}

4. 主排序函數 radix_sort

void radix_sort(int array[], int length) {
    if (NULL == array || length <= 1) return;

    int* digits = malloc(length * sizeof(int));
    int* buffer = malloc(length * sizeof(int));
    int* data_copy = malloc(length * sizeof(int));
    memcpy(data_copy, array, length * sizeof(int));

    int weight = 1;
    while (pre_process_data(digits, length, weight)) {
        sort_for_basic_number(digits, length, buffer);
        sort_data_by_basic_number(array, digits, buffer, length, weight);
        memcpy(digits, array, length * sizeof(int)); // 更新 digits 為最新數據供下輪提取
        ++weight;
    }

    free(digits);
    free(buffer);
    free(data_copy);
}

測試重點

• 含負數陣列：-12, 5, -3, 0, 104
• 大數值範圍驗證位數提取正確性
• 已排序/逆序/重複元素陣列

優化方向

1. 改用計數排序替代雙重循環匹配，將 sort_data_by_basic_number 降至 O(n)。
2. 預分配緩衝區避免重複 malloc/free。
3. 位運算優化（基數 2^k）替代基數 10，提升速度。

總結

基數排序以空間換時間，在整數鍵值排序中極具優勢。本文實現支援負數、模組化清晰，適合教學與工程參考。掌握其「位提取→穩定排序→映射回原數據」三步曲，即可靈活擴展至字串、浮點數等場景。