C 語言 qsort 快速排序完全指南：比較函數編寫、多類型排序與避坑技巧

編輯：關於C語言

一、qsort 簡介

頭文件：<stdlib.h>
原型：void qsort(void* base, size_t nmemb, size_t size, int (*compar)(const void*, const void*));
特點：原地排序、不穩定、平均 O(n log n)，最壞 O(n²)（已優化版本如 glibc 內部切換插入排序緩解）。
C++ 優先選 std::sort（<algorithm>），類型安全、更快、支援仿函數/lambda。

二、比較函數編寫規範

int cmp(const void* a, const void* b) {
    // 1. 強制轉型為元素指針
    // 2. 比較邏輯
    // 3. 返回：負值(<)、0(=)、正值(>)
}

三、各類型比較函數模板

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); // 避免相減溢出
}

2. 浮點型

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. 結構體一級排序（按單一字段）

struct Student { double score; int id; };

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

4. 結構體多級排序（主鍵升序、次鍵降序）

struct Point { int x, y; };

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

5. 字符串/字符數組排序（字典序）

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);
}

// 或結構體內嵌字符數組
struct Item { char name[32]; };
int cmp_item(const void* a, const void* b) {
    return strcmp(((const struct Item*)a)->name, ((const struct Item*)b)->name);
}

四、完整調用範例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

int cmp_stu(const void* a, const void* b) {
    const struct Student* p1 = (const struct Student*)a;
    const struct Student* p2 = (const struct Student*)b;
    if (p1->score != p2->score) return p2->score - p1->score; // 分數降序
    return strcmp(p1->name, p2->name);                        // 同分按姓名升序
}

int main() {
    struct Student arr[] = {
        {"Alice", 85}, {"Bob", 92}, {"Charlie", 85}, {"David", 78}
    };
    size_t n = sizeof(arr) / sizeof(arr[0]);
    qsort(arr, n, sizeof(arr[0]), cmp_stu);

    for (size_t i = 0; i < n; ++i)
        printf("%s %d\n", arr[i].name, arr[i].score);
    return 0;
}

五、常見錯誤與避坑指南

比較函數返回 bool 或只返回 0/1：必須返回負/0/正，否則排序結果未定義。
整數相減溢出：return *a - *b 在 INT_MIN - INT_MAX 溢出，改用 (*a > *b) - (*a < *b)。
浮點數直接相減：可能產生 NaN，導致未定義行為，同用三元邏輯。
結構體含指針成員：比較時需解引用指針比較指向內容，而非指針值。
const 正確性：比較函數參數應為 const void*，轉型時保留 const。
數組名退化為指針：傳遞二維數組或指針數組時，base 傳 arr，size 為元素大小（如 sizeof(arr[0]) 或 sizeof(char*)）。

六、C++ 現代替代方案

#include <algorithm>
#include <vector>
#include <string>

std::vector<Student> vec = ...;
std::sort(vec.begin(), vec.end(),
    [](const Student& a, const Student& b) {
        if (a.score != b.score) return a.score > b.score;
        return a.name < b.name;
    });