【C/C++】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); }
上一篇: python 手机App数据抓取实战一
下一篇: 喜欢我的请亮灯
推荐阅读