C 語言 qsort 效能實測：百萬筆資料驗證 O(n log n) 時間複雜度

編輯：關於C語言

從理論到實測：用 qsort 直觀感受 O(n log n) 的計算代價

演算法複雜度 O(n log n) 是教科書標準，但實際執行時間受常數因子、快取效應、分支預測、記憶體頻寬影響極大。本文以 qsort 排序 100 萬筆 float 重複 10 次為例，示範如何在筆電上量測真實效能並解讀結果。

測試程式碼

#include 
#include 
#include 

#define N 1000000

int compare(const void *p1, const void *p2) {
    float f1 = *(const float*)p1;
    float f2 = *(const float*)p2;
    if (f1 < f2) return -1;
    if (f1 > f2) return 1;
    return 0;
}

int main() {
    float *x = malloc(N * sizeof(float));
    if (!x) return 1;

    srand((unsigned)time(NULL));
    clock_t t1 = clock();

    for (int j = 0; j < 10; j++) {
        for (long i = 0; i < N; i++)
            x[i] = (float)rand() / RAND_MAX; // [0, 1) 均勻分布
        qsort(x, N, sizeof(float), compare);
    }

    for (int i = 0; i < 10; i++) printf("%f ", x[i]);
    printf("\n");

    clock_t t2 = clock();
    printf("浮點數排序算法用時: %f 秒\n", (double)(t2 - t1) / CLOCKS_PER_SEC);
    free(x);
    return 0;
}

實測環境與結果

CPU：Intel Core i7-8565U (1.8 GHz, 4C8T)
編譯：gcc -O2 -std=c11 qsort_test.c -o qsort_test
OS：Ubuntu 22.04 LTS

~/tmp$ ./qsort_test
0.000001 0.000002 0.000003 0.000004 0.000005 0.000006 0.000007 0.000008 0.000009 0.000010
浮點數排序算法用時: 2.236941 秒

結果解讀

指標	數值	說明
總元素數	10 × 1,000,000 = 10⁷
理論比較次數	~ n log₂ n ≈ 10⁷ × 23.25 ≈ 2.3×10⁸	平均情況
實測耗時	2.24 秒	含資料生成 + 排序 + 輸出
單次排序估算	~0.22 秒	扣除資料生成開銷
每比較耗時	~1 ns	極佳：受惠於 L1 快取、分支預測、SIMD 自動向量化

影響 qsort 效能的關鍵因素

比較函數開銷：函數呼叫、間接存取、分支。內聯比較或使用巨集可提升 20-30%。
資料局部性：float 陣列連續記憶體，預取友善。結構體陣列若欄位多則快取命中率下降。
輸入分布：已近乎排序/逆序/大量重複值會觸發不同分區策略 (glibc 內省排序 Introsort：QuickSort + HeapSort + InsertionSort)。
記憶體配置：malloc 記憶體對齊、posix_memalign 64-byte 對齊利於 SIMD。
編譯優化：-O2/-O3、-march=native、-flto (鏈接時優化) 影響顯著。

進階優化方向

Radix Sort (基數排序)：浮點數可轉換為整數位模式，O(n) 線性排序，百萬筆可達 0.05 秒級
平行排序：__gnu_parallel::sort (GNU extension) 或 Intel TBB parallel_sort，多核心近線性加速
自定義快速排序：三向切分、中位數三取樣、小陣列插入排序切換，針對特定資料型別特化
避免 qsort 通用介面開銷：模板/巨集產生型別專用排序，消除 void* 轉換與間接呼叫