您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 程式設計綜合問答

C 語言基數排序演算法完整實現與原理解析

編輯：程式設計綜合問答

基數排序核心思想

基數排序是非比較型整數排序演算法，透過「個位→十位→百位...」逐位分配與收集，利用桶排序思想實現穩定排序。時間複雜度 O(d*(n+k))，空間複雜度 O(n+k)。

完整可執行代碼 (VC++ 相容)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_DIGITS 10  // 0-9 十進位
#define MAX_SIZE 100   // 最大陣列大小

// 獲取最大值位數
int getMaxDigits(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }
    int digits = 0;
    while (max > 0) {
        max /= 10;
        digits++;
    }
    return digits;
}

// 基數排序主函數
void radixSort(int arr[], int n) {
    int maxDigits = getMaxDigits(arr, n);
    int *bucket = (int*)malloc(n * sizeof(int));
    int count[MAX_DIGITS];
    int divisor = 1;

    for (int d = 0; d < maxDigits; d++) {
        // 1. 計數歸零
        memset(count, 0, sizeof(count));

        // 2. 統計各桶元素個數
        for (int i = 0; i < n; i++) {
            int digit = (arr[i] / divisor) % 10;
            count[digit]++;
        }

        // 3. 計算桶起始位置 (前綴和)
        for (int i = 1; i < MAX_DIGITS; i++) {
            count[i] += count[i-1];
        }

        // 4. 從後向前放入桶 (保證穩定性)
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / divisor) % 10;
            bucket[--count[digit]] = arr[i];
        }

        // 5. 從桶收集回原陣列
        memcpy(arr, bucket, n * sizeof(int));

        // 6. 移至下一位
        divisor *= 10;
    }

    free(bucket);
}

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

    printf("排序前: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");

    radixSort(arr, n);

    printf("排序後: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

關鍵步驟圖解

初始陣列: [170, 45, 75, 90, 802, 24, 2, 66]

第 1 輪 (個位排序):
桶 0: [170, 90]      桶 2: [802, 2]     桶 4: [24]
桶 5: [45, 75]       桶 6: [66]
收集: [170, 90, 802, 2, 24, 45, 75, 66]

第 2 輪 (十位排序):
桶 0: [802, 2]       桶 2: [24]         桶 4: [45]
桶 6: [66]           桶 7: [170, 75]    桶 9: [90]
收集: [802, 2, 24, 45, 66, 170, 75, 90]

第 3 輪 (百位排序):
桶 0: [2, 24, 45, 66, 75, 90]   桶 1: [170]   桶 8: [802]
收集: [2, 24, 45, 66, 75, 90, 170, 802] ✓

進階優化版本 (支援負數)

void radixSortWithNegative(int arr[], int n) {
    // 分離正負數
    int *pos = (int*)malloc(n * sizeof(int));
    int *neg = (int*)malloc(n * sizeof(int));
    int posCount = 0, negCount = 0;

    for (int i = 0; i < n; i++) {
        if (arr[i] >= 0) pos[posCount++] = arr[i];
        else neg[negCount++] = -arr[i]; // 存絕對值
    }

    // 分別排序
    if (posCount > 0) radixSort(pos, posCount);
    if (negCount > 0) {
        radixSort(neg, negCount);
        // 負數部分反轉並取負
        for (int i = 0; i < negCount/2; i++) {
            int t = neg[i]; neg[i] = neg[negCount-1-i]; neg[negCount-1-i] = t;
        }
        for (int i = 0; i < negCount; i++) neg[i] = -neg[i];
    }

    // 合併：負數在前，正數在後
    int idx = 0;
    for (int i = 0; i < negCount; i++) arr[idx++] = neg[i];
    for (int i = 0; i < posCount; i++) arr[idx++] = pos[i];

    free(pos); free(neg);
}