qsort()函数

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