C 標準庫 qsort 函數完整使用指南：從基本類型到複雜結構體排序

qsort 是 C 標準庫提供的快速排序實作（<stdlib.h>），以函式指標實現泛型排序。本文系統整理各類資料型別的比較函式寫法與實戰技巧。

函數原型

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

• base：陣列起始位址
• nmemb：元素個數
• size：單一元素大小（sizeof(type)）
• compar：比較函式，回傳 < 0 / = 0 / > 0 代表小於/等於/大於

比較函式核心原則

int cmp(const void *a, const void *b) {
    // 1. 轉型為正確型別指標
    // 2. 解參考取值
    // 3. 回傳差值或三元比較，避免整數溢位
}

避免溢位：整數比較勿直接相減（return *(int*)a - *(int*)b 可能溢位），改用三元運算子：

return (*(int*)a > *(int*)b) - (*(int*)a < *(int*)b);  // C++20 可用 std::cmp_three_way

各類型完整範例

1. 基本整數型別

int cmp_int(const void *a, const void *b) {
    int ia = *(const int*)a;
    int ib = *(const int*)b;
    return (ia > ib) - (ia < ib);
}
qsort(arr, n, sizeof(int), cmp_int);

2. 浮點數（double/float）

int cmp_double(const void *a, const void *b) {
    double da = *(const double*)a;
    double db = *(const double*)b;
    return (da > db) - (da < db);  // 處理 NaN 需額外判斷
}

3. 字串（char*）

int cmp_str(const void *a, const void *b) {
    const char *sa = *(const char**)a;
    const char *sb = *(const char**)b;
    return strcmp(sa, sb);
}
// 陣列型別：char *names[]
qsort(names, count, sizeof(char*), cmp_str);

4. 結構體：單一欄位排序

struct Student { char name[32]; int score; };

int cmp_score(const void *a, const void *b) {
    const Student *sa = (const Student*)a;
    const Student *sb = (const Student*)b;
    return (sa->score > sb->score) - (sa->score < sb->score);
}

5. 結構體：多鍵值排序（主要鍵升序、次要鍵降序）

struct Point { int x, y; };

int cmp_point(const void *a, const void *b) {
    const Point *pa = (const Point*)a;
    const Point *pb = (const Point*)b;
    if (pa->x != pb->x)
        return (pa->x > pb->x) - (pa->x < pb->x);  // x 升序
    return (pb->y > pa->y) - (pb->y < pa->y);  // y 降序
}

6. 幾何演算法：凸包極角排序

struct Point { double x, y; };
Point pivot;  // 基準點（最左下點）

int cmp_polar(const void *a, const void *b) {
    const Point *pa = (const Point*)a;
    const Point *pb = (const Point*)b;
    double cross = (pa->x - pivot.x) * (pb->y - pivot.y)
                 - (pa->y - pivot.y) * (pb->x - pivot.x);
    if (cross != 0) return (cross > 0) ? -1 : 1;  // 逆時針序
    // 共線：遠點優先
    double da = (pa->x - pivot.x)*(pa->x - pivot.x) + (pa->y - pivot.y)*(pa->y - pivot.y);
    double db = (pb->x - pivot.x)*(pb->x - pivot.x) + (pb->y - pivot.y)*(pb->y - pivot.y);
    return (da > db) ? -1 : 1;
}

常見錯誤與避坑指南

現代 C++ 替代方案

// C++ 標準演算法：型別安全、支援 Lambda、通常更快
std::sort(vec.begin(), vec.end(), [](const Auto& a, const Auto& b) {
    return a.key < b.key;
});

// 穩定排序
std::stable_sort(vec.begin(), vec.end(), cmp);

std::sort 平均比 qsort 快（內聯優化、避免函式呼叫開銷），新專案優先使用。