qsort()函數的使用

qsort()函數是 C 庫中實現的快速排序演算法，包含在 stdlib.h 頭文件中，其時間複雜度為 O(nlogn)。函數原型如下：

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

此函數需要四個參數。

第一個參數是需要排序的數組的基地址，因為是 void * 類型，所以此函數可以給任何類型的數組進行排序；

第二個參數是待排序的數量(size_t 是一種特別的數據類型，可以近似理解為 int 型)；

第三個是單個數組元素的大小，即位元組數，例如 int 型就是 4 或者 sizeof(int) (sizeof 的返回值類型就是 sizeof)，char 型就是 1 或者

sizeof(char)。因為為了適用於各種數據結構，第一個參數將指向數組的指針強轉成了 void * 類型，也即此時函數並不知道將要進行排序的數組記憶體儲的是什麼元素，因此我們需要顯式地告訴它單個元素所占的長度；

第四個參數是一個指向函數的指針，其作用是規定排序的規則，即按照什麼樣的方式進行排序。

下麵我們對一個整型數組排序為例：

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

//比較函數原型 
int mycmp(const void* p1, const void* p2);
 
int main() {
    
    int num[10] = {32, -4, 89, 232, 2, 12, -32, 0, -4, 89};
    
    qsort(num, 10, sizeof(int), mycmp);
    
    for(int i=0; i<10; i++)
        printf("%d ", num[i]);
    
    printf("\n");
    return 0;
}

//比較函數 
int mycmp(const void* p1, const void* p2){
    const int * a = (const int *) p1;
    const int * b = (const int *) p2;
    
    int value = 0;
    
    if(*a < *b)
        value = -1;
    else if(*a == *b)
        value = 0;
    else value = 1;
    
    return value;
}

運行結果如下所示：

使用 qsort 最重要的是比較函數的編寫。

首先，qsort 函數的原型中已經對此元素的原型有了明確的規定：int (*compar)(const void *, const void *) ，需要傳入指向兩個元素的指針。

與上文增加第三個參數的原因相同，比較函數的參數指針是 void * 類型，這個參數同樣不知道元素實際的大小，因此我們需要進行類型的強轉，轉換成元素實際類型對應的指針，例如上文中為了給一個 int 型數組排序：

const int * a = (const int *) p1;
const int * b = (const int *) p2;

然後，兩個元素之間的比較結果無非 > 、= 、< ，我們要給希望成立的結果返回 1，例如：如果希望從小到大排列，則 *a < *b 成立時返回 1；如果希望從大到小排列，則 *a > *b 返回 1，相應的 *a == *b 返回 0，*a < *b 返回 -1.

因此如果將上述程式的 1 和 -1 顛倒位置，結果就會變成降序排列：

因為可以任意編寫比較函數，當比較具有優先順序時我們也可以從容解決。

例如：

定義了這樣一個表示時間的結構體：

struct Time {
    int hour;
    int min;
    int sec;
}; 

如果對此類型的數組元素進行升序排列，那麼比較函數應該為：

int mycomp(const void * p1, const void * p2){
    const Time * a = (const Time *) p1;
    const Time * b = (const Time *) p2;
    
    int value = 0;
    
    if(a->hour > b->hour)
        value = 1;
    else if(a->hour < b->hour)
        value = -1;
    
    else{
        if(a->min > b->min)
            value = 1;
        else if(a->min < b->min)
            value = -1;
        else{
            if(a->sec > b->sec)
                value = 1;
            else if(a->sec < b->sec)
                value = -1;
            else value = 0;
        }
    }
    
    return value;
}