C 語言 qsort 函數詳解：從基本類型到結構體排序的比較函數寫法

qsort 原型

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

• base：數組首地址
• nmemb：元素個數
• size：單元素大小 sizeof(T)
• compar：比較函數，返回 < 0 / = 0 / > 0 表示 < / = / >

基本類型排序

int 數組

int cmp_int(const void *a, const void *b) {
    int ia = *(const int*)a;
    int ib = *(const int*)b;
    return (ia > ib) - (ia < ib); // 避免溢出，不直接用 ia - ib
}

int arr[] = {5, 2, 9, 1, 7};
qsort(arr, 5, sizeof(int), cmp_int);

char 數組（同 int）

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

結構體排序

按單一字段排序

typedef struct { int data; } Node;

int cmp_node_data(const void *a, const void *b) {
    const Node *pa = (const Node*)a;
    const Node *pb = (const Node*)b;
    return (pa->data > pb->data) - (pa->data < pb->data);
}

Node nodes[] = {{5}, {2}, {9}, {1}, {7}};
qsort(nodes, 5, sizeof(Node), cmp_node_data);

按多字段排序（先 x 後 y）

typedef struct { int x, y; } Point;

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);
    return (pa->y > pb->y) - (pa->y < pb->y);
}

按字符串字段排序

typedef struct { char name[32]; } Person;

int cmp_person_name(const void *a, const void *b) {
    const Person *pa = (const Person*)a;
    const Person *pb = (const Person*)b;
    return strcmp(pa->name, pb->name);
}

指針數組排序（排序指針而非對象）

int *ptrs[5];
for (int i = 0; i < 5; i++) ptrs[i] = &arr[i];

int cmp_ptr(const void *a, const void *b) {
    int *pa = *(int**)a;
    int *pb = *(int**)b;
    return (*pa > *pb) - (*pa < *pb);
}

qsort(ptrs, 5, sizeof(int*), cmp_ptr);

常見錯誤與避坑

1. 比較函數返回值溢出：return ia - ib 可能溢出，改用 (ia > ib) - (ia < ib) 或 ia < ib ? -1 : ia > ib。
2. const 正確性：參數應為 const void*，轉換時保留 const。
3. 結構體包含指針：淺拷貝排序會導致指針指向同一內存，需自定義交換邏輯或排序指針數組。
4. 浮點數比較：NaN 不等於自身，需特殊處理；+0.0 == -0.0 為真。

性能提示

• 小數組（< 50 元素）插入排序可能更快，glibc 內部已優化。
• 比較函數開銷大時，考慮預計算鍵值（Schwartzian transform）或使用鍵值索引排序。
• 大量重複鍵值時，三路快排（荷蘭國旗算法）優於標準快排。

總結

qsort 是 C 標準庫提供的通用排序，核心在於正確編寫比較函數。掌握基本類型、結構體單/多字段、字符串、指針數組等常見場景的比較函數寫法，即可應對 95% 的排序需求。