藍橋杯 C 語言基礎訓練：數列排序 (n ≤ 200) 完整解法與優化

編輯：關於C語言

題目描述

給定長度 n (1 ≤ n ≤ 200) 的整數數列，將其按從小到大順序排序輸出。每個整數絕對值 < 10000。

輸入輸出範例

解法分析

資料範圍極小 (n ≤ 200)，時間複雜度 O(n²) 的簡單排序 (冒泡、選擇、插入) 完全足夠，無需快排/歸併。標準庫 `qsort` 最省事。

方案一：標準庫 qsort (推薦)

#include 
#include 

int cmp(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    int a[200];
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    
    qsort(a, n, sizeof(int), cmp);
    
    for (int i = 0; i < n; i++) {
        printf("%d%c", a[i], i == n-1 ? '\n' : ' ');
    }
    return 0;
}

方案二：冒泡排序 (教學用)

void bubble_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j+1]) {
                int t = a[j]; a[j] = a[j+1]; a[j+1] = t;
                swapped = true;
            }
        }
        if (!swapped) break; // 已有序提前結束
    }
}

方案三：計數排序 (數值範圍小時最快 O(n+k))

題目說明絕對值 < 10000，範圍 [-9999, 9999]，共 19999 個可能值，適合計數排序。

void counting_sort(int a[], int n) {
    const int OFFSET = 10000; // 將負數映射到非負索引
    const int RANGE = 20001;
    static int count[RANGE] = {0}; // static 避免棧溢出
    
    for (int i = 0; i < n; i++) count[a[i] + OFFSET]++;
    
    int idx = 0;
    for (int v = 0; v < RANGE; v++) {
        while (count[v]-- > 0) a[idx++] = v - OFFSET;
    }
}

複雜度對比

演算法	時間	空間	穩定性	備註
qsort	O(n log n) 平均	O(log n) 棧	不穩定	標準庫、生產首選
冒泡/插入	O(n²)	O(1)	穩定	n≤200 完全可接受
計數排序	O(n + k)	O(k)	穩定	k=20001 此題最快

常見錯誤與避坑

比較函數溢位：`return *(int*)a - *(int*)b` 在極大整數差值會溢位，安全寫法：
`return (*(int*)a > *(int*)b) - (*(int*)a < *(int*)b);`
輸入讀取失敗：未檢查 `scanf` 回傳值，導致未初始化陣列被排序
輸出格式：末尾多餘空格通常可接受，但建議控制格式
陣列大小：宣告 `a[200]` 或 `a[205]` 留餘量

完整可提交代碼 (qsort 版)

#include 
#include 

int cmp(const void *a, const void *b) {
    int x = *(const int*)a;
    int y = *(const int*)b;
    return (x > y) - (x < y); // 避免溢位
}

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0 || n > 200) return 0;
    int a[200];
    for (int i = 0; i < n; i++) {
        if (scanf("%d", &a[i]) != 1) return 0;
    }
    qsort(a, n, sizeof(int), cmp);
    for (int i = 0; i < n; i++) {
        printf("%d%c", a[i], i == n-1 ? '\n' : ' ');
    }
    return 0;
}