C 语言 `qsort` 函数介绍

C 语言qsort函数介绍

qsort是 C 标准库<stdlib.h>中提供的通用排序函数，可以对任意类型的数组进行排序（通常内部使用快速排序，但标准并未规定具体算法）。

1. 函数原型

#include<stdlib.h>voidqsort(void*base,size_tnmemb,size_tsize,int(*compar)(constvoid*,constvoid*));

参数说明

返回值

无返回值，排序结果直接写回base指向的数组。

2. 比较函数

比较函数是qsort的核心，签名必须是：

intcompar(constvoid*a,constvoid*b);

它需要比较a、b指向的两个元素，返回值约定如下：

• 返回负数：a应排在b前面
• 返回 0：两者相等（顺序不确定）
• 返回正数：a应排在b后面

在比较函数内部，通常需要先把void *强制转换为实际元素类型。

3. 使用示例

3.1 排序整数数组

#include<stdio.h>#include<stdlib.h>intcmp_int(constvoid*a,constvoid*b){intia=*(constint*)a;intib=*(constint*)b;return(ia>ib)-(ia<ib);/* 避免 ia - ib 溢出 */}intmain(void){intarr[]={5,2,9,1,5,6};size_tn=sizeof(arr)/sizeof(arr[0]);qsort(arr,n,sizeof(int),cmp_int);for(size_ti=0;i<n;i++)printf("%d ",arr[i]);printf("\n");return0;}

注意：不要写成return *(int*)a - *(int*)b;，当两个数相差很大时可能发生整数溢出，导致比较结果错误。

3.2 排序结构体数组

#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstruct{charname[32];intage;}Person;/* 先按年龄升序，年龄相同按姓名升序 */intcmp_person(constvoid*a,constvoid*b){constPerson*pa=(constPerson*)a;constPerson*pb=(constPerson*)b;if(pa->age!=pb->age)return(pa->age>pb->age)-(pa->age<pb->age);returnstrcmp(pa->name,pb->name);}intmain(void){Person people[]={{"Alice",30},{"Bob",25},{"Carol",30},{"Dave",20},};size_tn=sizeof(people)/sizeof(people[0]);qsort(people,n,sizeof(Person),cmp_person);for(size_ti=0;i<n;i++)printf("%s (%d)\n",people[i].name,people[i].age);return0;}

3.3 排序字符串指针数组

intcmp_str(constvoid*a,constvoid*b){/* 数组元素是 char*，所以 a、b 实际是 char** */constchar*const*sa=(constchar*const*)a;constchar*const*sb=(constchar*const*)b;returnstrcmp(*sa,*sb);}intmain(void){constchar*words[]={"banana","apple","cherry","date"};size_tn=sizeof(words)/sizeof(words[0]);qsort(words,n,sizeof(char*),cmp_str);for(size_ti=0;i<n;i++)printf("%s\n",words[i]);return0;}

这是新手最常出错的地方：字符串数组的元素类型是char *，所以传给比较函数的是char **。

4. 复杂度与特性

• 平均时间复杂度：O(n log n)
• 最坏时间复杂度：取决于具体实现，理论上可能是 O(n²)
• 空间复杂度：通常 O(log n)（递归栈）
• 稳定性：qsort不保证稳定排序。若需要稳定排序，需自行附加原始下标作为次级比较键，或改用归并排序等算法。

5. 注意事项与常见陷阱

1. 整数溢出：比较函数里不要直接用a - b，改用(a > b) - (a < b)。
2. 严格弱序：比较函数必须满足严格弱序（反对称、传递），否则行为未定义。
3. 不要修改元素：比较函数只应读取，不应写入a、b指向的内容。
4. 浮点数比较：若数组含NaN，<、>比较均为假，排序结果可能异常，需要特殊处理。
5. size_t是无符号类型：向qsort传元素个数和元素大小时不要传负数，否则会被转换为巨大的无符号数，导致越界。
6. 元素大小必须一致：size必须是所有元素共同的字节大小，qsort不支持变长元素。
7. 类型转换保持 const：强制转换时保留const限定（如const int *），避免意外写入。
8. C11 的qsort_s：部分实现（如 MSVC、C11 附录 K）提供带上下文参数的qsort_s，但可移植性差，一般仍用qsort。

6. 小结

qsort通过void *+ 函数指针实现了对任意类型的通用排序，是 C 语言中“泛型编程”的经典范例。使用时记住三点：正确传入元素个数与元素大小、正确编写比较函数、注意整数溢出与类型转换，就能应对绝大多数排序场景。