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

【C/C++】qsort函数的使用方法和细节

程序员文章站 2022-09-27 17:21:34
函数概述 qsort 为quick sort的简写,意为快速排序,主要用于对各种数组的排序,在头文件stdlib.h中。 因为数组的元素可能是任何类型的,甚至是结构或者联合,所以必须高数函数qsort如何确定两个数组元素哪一个“更小”,这就需要我们给出比较的规则,即什么算大,什么算小。 通过编写比较 ......

函数概述

qsort 为quick sort的简写,意为快速排序,主要用于对各种数组的排序,在头文件stdlib.h中。
因为数组的元素可能是任何类型的,甚至是结构或者联合,所以必须高数函数qsort如何确定两个数组元素哪一个“更小”,这就需要我们给出比较的规则,即什么算大,什么算小。
通过编写比较函数可以为函数qsort提供这些信息。当给定两个指向数组元素的指针p和q时,比较函数必须返回一个整数。如果*p小于*q,那么返回的数为负数;如果*p等于*q,那么返回0.如果*p大于*q,返回正数。

函数原型

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

函数描述

函数的形式参数从左到右分别为:
指向要排序数组的第一个元素的指针base(如果只是要对数组的一段区域进行排序,那么要是base指向这段区域的第一个元素。)在一般情况下,base就是数组的名字;
nmemb是要排序元素的数量(不一定是数组中元素的数量);
size是每个数组元素的大小,用字节来衡量;
compar为指向比较函数的指针。

比较函数的实现

比较函数的实现是qsort函数能否正确实现的重点。
编写比较函数并没有想象中的那么容易。函数qsort要求它的形式参数类型为void *,但我们不能通过void *型的指针访问数组的成员;我们需要指向要比较元素的类型的指针。为了解决这个问题,我们将在比较函数内部把p与q赋给相应对应类型的指针变量。由于常量指针不能赋值给变量。所以在声明对应指针变量时应该加上const关键字。
下面是一个比较整型数组的比较函数的例子。

    int compare(const void *p, const void *q)
    {
        const int *p1 = p;
        const int *q1 = q;
        if (*p1 < *q1)
            return -1;
        else if (*p1 == *q1)
            return 0;
        else
            return 1;
}

当然除了把用const指针变量的方法,还可以使用强制类型转换的方式来达到这个目的。

    int compare(const void *p,const void *q)
    {
        if(*(int *)p<*(int *)q)
            return -1;
        else if(*(int *)p==*(int *)q)
            return 0;
        else
            return 1;
    }

还可以进一步精简

    int compare(const void *p,const void *q)
    {
          return *(int *)p-*(int *)q;
    }

需要注意的点:比较元素是指针的比较函数的实现。

如果待比较的元素是指针(虽然我们一般不会比较指针的大小,但是我们经常需要对指针代表的空间比较大小,比如比较一个字符串数组的大小,每个字符串都由一个指针代表),那么比较函数的实现就比较麻烦了。
首先我们需要明确的是,比较函数中的两个指针必须要指向需要比较的两个元素。如果这两个元素是指针而不是一个实体,那么这两个指针应该是指向指针的指针。
这里我们以一个比较字符串的比较函数举例:

    int compare(const void *p,const void *q)
    {
        return strcmp(*(char **)p,*(char **)q);  
    }