qsort的cmp函數理解

• 2020 年 11 月 30 日
• 筆記

qsort使用

近期頻繁使用qsort函數，但是對於cmp函數卻一直不太熟悉，現用現查。故寫一篇小筆記記錄一下。

函數原型：

void qsort(void *base,size_t NumEle,size_t SizeEle,int (cmp*)(const void *a,const void *b))

值得注意的是cmp這個函數指針，返回值類型必須是int，參數是兩個const void *,在寫cmp函數時，可以選擇在函數體內，再將a，b強轉為所需要的類型，而因為void *的特殊性，也可以在寫函數簽名是用const T*代替。

cmp函數

以一個int數組為例，現在要將這個數組按照元素大小，升序排列。cmp函數與參數a,b對於qsort的影響是

if a>b return positive
if a=b return 0
if a<b return negative

按照這個要求設計的return就會使得按照升序排序，注意是按照這個要求去設計所需要的返回值！只要能保住a,b在你設計的規則下，產生這樣的返回值即可。

而這三個條件剛好與a-b等價：

a>b return positive ~ a-b
a=b return 0        ~ a-b
a<b return negative ~ a-b

因而cmp函數可以寫為：

int cmp(const void *a,const void *b){
    return *(int*)a-*(int*)b;/*按照升序排序*/
}

那麼按照這個思想，同樣可以寫出字元串按字典序，因為strcmp函數的返回值，正與我們所要求的升序設計一致。因而cmp函數可以寫為：

int cmp(const void *a,const void *b){
    return (char*)a-(char*)b;/*按照升序排序*/
}

對於結構體的排序也是如此，只是要注意類型的轉化。多級排序就設計一個if/else即可，例如：

struct pair{
    int x;
    int y;
}P[100];
/*
當x不相等時，按照x升序排序，否則就按y降序排列
*/
int cmp(const void *a,const void *b){
    struct pair* p_a=(struct pair*)a;
    struct pair* p_b=(struct pair*)b;
    if(p_a->x==p_b->x){
        return p_a->x - p_b->x;
    }else{
        reyurn p_b->y - p_a->y;
    }
}
qsort(P,100,sizeof(P[0]),cmp);

總結

因此，要弄清楚cmp的意義，關鍵在於如何排序是有規定的，我們要根據這個規定去設計cmp函數的返回值。

按照升序排序的要求：對於任意的元素a，b(假定比較運算符有意義)

if a>b return positive 
if a=b return 0       
if a<b return negative