|
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); 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;}
| 
收藏
淘帖
踩
