C语言qsort()函数的使用
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; }
运行结果如下所示:
使用 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; }
下一篇: ComboBox 控件的用法教程