欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言qsort()函数的使用

程序员文章站 2022-03-07 15:27:42
C语言qsort()函数的使用 qsort()函数是 C 库中实现的快速排序算法,包含在 头文件中,其时间复杂度为 O(nlogn)。函数原型如下: 此函数需要四个参数。 第一个参数是需要排序的数组的基地址,因为是 类型,所以此函数可以给任何类型的数组进行排序; 第二个参数是待排序的数量(size_ ......

c语言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;
}

运行结果如下所示:

C语言qsort()函数的使用

使用 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 颠倒位置,结果就会变成降序排列:

C语言qsort()函数的使用

因为可以任意编写比较函数,当比较具有优先级时我们也可以从容解决。

例如:

定义了这样一个表示时间的结构体:

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