您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

qsort 比較函數寫法大全：七大資料類型排序範例 (含結構體多鍵值、字串、凸包)

編輯：關於C++

qsort 原型回顧


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

compar 回傳：< 0 (a0 (a>b)
參數為 void*，函數內需轉型為實際型別指標

一、基本型別陣列排序

int / long


int cmp_int(const void* a, const void* b) {
    int ia = *static_cast(a);
    int ib = *static_cast(b);
    return (ia > ib) - (ia < ib); // 避免減法溢位
}
qsort(arr, n, sizeof(int), cmp_int);

char / unsigned char


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

double / float (不可直接相減)


int cmp_double(const void* a, const void* b) {
    double da = *static_cast(a);
    double db = *static_cast(b);
    return (da > db) - (da < db); // 或使用 fcmp 模式
}

二、結構體一級鍵值排序


struct Record {
    double score;
    int id;
};

int cmp_score(const void* a, const void* b) {
    const Record* pa = static_cast(a);
    const Record* pb = static_cast(b);
    return (pa->score > pb->score) - (pa->score < pb->score);
}
qsort(records, n, sizeof(Record), cmp_score);

三、結構體多級鍵值排序 (二級排序)


struct Point { int x, y; };

int cmp_xy(const void* a, const void* b) {
    const Point* pa = static_cast(a);
    const Point* pb = static_cast(b);
    if (pa->x != pb->x) return pa->x - pb->x;      // 主鍵：x 升序
    return pb->y - pa->y;                          // 次鍵：y 降序
}

四、字串排序 (結構體內嵌 char[] 或 char*)


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

int cmp_name(const void* a, const void* b) {
    const Student* pa = static_cast(a);
    const Student* pb = static_cast(b);
    return strcmp(pa->name, pb->name); // 字典序
}

五、指標陣列排序 (排序指向結構體的指標)


Student* students[100];
// ... 填入指標 ...
int cmp_ptr(const void* a, const void* b) {
    const Student* pa = *static_cast(a);
    const Student* pb = *static_cast(b);
    return strcmp(pa->name, pb->name);
}
qsort(students, n, sizeof(Student*), cmp_ptr);

六、計算幾何：凸包極角排序 (Graham Scan 核心)


struct Point { double x, y; };
Point pivot; // 基準點 (最低最左)

double cross(const Point& a, const Point& b, const Point& c) {
    return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
double dist2(const Point& a, const Point& b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return dx*dx + dy*dy;
}

int cmp_polar(const void* a, const void* b) {
    const Point* pa = static_cast(a);
    const Point* pb = static_cast(b);
    double cr = cross(pivot, *pa, *pb);
    if (cr < 0) return 1;   // pb 在 pa 左側 (順時針)
    if (cr > 0) return -1;  // pa 在 pb 左側
    // 共線：遠點優先 (便於掃描移除內點)
    return (dist2(pivot, *pb) < dist2(pivot, *pa)) ? 1 : -1;
}

七、通用比較函數模板 (C++ 泛型寫法)


template 
int cmp_asc(const void* a, const void* b) {
    const T& va = *static_cast(a);
    const T& vb = *static_cast(b);
    return (va > vb) - (va < vb);
}

// 使用
qsort(arr, n, sizeof(int), cmp_asc);
qsort(vec, n, sizeof(double), cmp_asc);

常見錯誤與避坑指南

錯誤	後果	正確做法
`return (int)a - (int)b;`	整數溢位導致錯誤排序 (INT_MIN - INT_MAX 為正)	用三元運算或 `(a>b)-(a`
double 直接相減轉 int	精度遺失、錯誤比較	用 `(da>db)-(da`
忘記 `const` 正確性	C++ 編譯警告/錯誤	參數加 `const`，轉型用 `static_cast`
結構體含指標未深度比較	比較指標值而非內容	解參考指標比較實際資料
比較函數不具備嚴格弱序	qsort 行為未定義 (可能死循環、崩潰)	確保可傳遞性、反對稱性、非自反性

標準庫替代方案 (C++ 推薦)


#include 
#include 

std::vector v = {...};
std::sort(v.begin(), v.end()); // 類型安全、內聯優化、支援 Lambda

std::sort(students, students+n, [](const Student& a, const Student& b){
    return a.score > b.score; // 降序
});

std::sort 平均效能優於 qsort (避免函數呼叫開銷、型別安全、支援移動語意)，現代 C++ 專案應優先使用。