深入解析 qsort 通用排序與 void 指針多態機制

K&R 教材第 5.11 節：行排序程序核心

本文詳細剖析《The C Programming Language》中通用快速排序 qsort 的實現，重點闡述 void * 指針如何實現類似多態的泛型編程。

qsort 函數原型與遞歸邏輯

void qsort(void *v[], int left, int right,
           int (*comp)(void *, void *)) {
    int i, last;
    if (left >= right) return;
    swap(v, left, (left + right) / 2);
    last = left;
    for (i = left + 1; i <= right; i++)
        if (comp(v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last - 1, comp);
    qsort(v, last + 1, right, comp);
}

函數接收指針陣列 v[]、左右邊界及比較函數指針 comp。透過遞歸分治完成排序，僅操作指針值，不直接搬移數據實體。

void 指針的類型轉換原理

1. 任意類型指針均可隱式轉為 void *，反之需顯式強制轉換。
2. 傳遞 char *lineptr[] 時，實際傳遞的是 (void **)lineptr，即指向指針陣列的指針。
3. 比較函數 comp 負責具體類型解讀：在 comp 內部將 void * 還原為 char * 進行字符串比較。

為何這樣設計？

• 通用性：同一排序邏輯可處理整數、浮點數、結構體、字符串等任意類型，只需提供對應比較函數。
• 地址運算安全：void * 僅保存地址，編譯器不知其指向類型大小，因此 qsort 內部僅進行指針交換（地址運算），不涉及解引用或算術運算，避免未定義行為。
• 平台無關：32/64 位系統指針大小固定，指針陣列佈局一致，保證移植性。

關鍵限制

嚴禁在 qsort 內部對 void 指針進行解引用或四則運算。所有類型感知操作必須委託給比較函數 comp，這正是「關注點分離」在 C 語言層面的體現。

標準庫 qsort 對比

ANSI C 標準庫 stdlib.h 提供的 qsort 原型為：

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

它直接操作內存塊，需指定元素大小 size，並透過指針算術計算偏移，比教材版本更底層、更通用。