C 語言選擇排序優化：從 O(n²) 到 qsort 避免超時

題目需求

對 n 個整數（n ≤ 100,000）進行降序排序，採用簡單選擇排序演算法。使用者原始碼採用雙重迴圈交換法，時間複雜度 O(n²)，在大資料量下導致超時（Time Limit Exceeded）。

原始碼問題分析

void sort(int array[], int n) {
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (array[i] < array[j]) { /* swap */ }
}

• 此為氣泡排序變體，非標準選擇排序，且雙重迴圈在 n=100,000 時約 10¹⁰ 次比較，遠超 40 秒限制。
• 選擇排序應每趟只找出最大值並交換一次，減少交換次數，但比較次數仍為 O(n²)。

優化方案：使用標準庫 qsort

C 標準庫 stdlib.h 提供 qsort，平均時間複雜度 O(n log n)，適合大規模資料。

實作範例

#include <stdlib.h>

int cmp_desc(const void *a, const void *b) {
    return (*(int*)b - *(int*)a); // 降序
}

int main() {
    int n;
    scanf("%d", &n);
    int *arr = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);

    qsort(arr, n, sizeof(int), cmp_desc);

    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    free(arr);
    return 0;
}

進階補充

• 若必須自行實作，可改用堆積排序或歸併排序，保證 O(n log n) 最壞情況。
• 注意 qsort 比較函數回傳值邏輯：負值表示 a < b，正值表示 a > b，零表相等。
• 輸入輸出量大時，建議使用 fread/fwrite 或關閉同步 ios::sync_with_stdio(false)（C++）。

善用標準庫高效演算法，是解決大規模排序超時的關鍵捷徑。