2. qsort 函数详解qsort是 C 标准库提供的通用排序函数可以对任意类型的数组进行排序。2.1 qsort 函数原型#includestdlib.h//头文件voidqsort(void*base,// 数组首地址size_tnum,// 元素个数size_tsize,// 每个元素的大小字节int(*compar)(constvoid*,constvoid*));// 指向不同类型数据的比较函数四个参数记忆口诀地址、个数、大小、怎么比2.2 使用 qsort 排序整型数组#includestdio.h#includestdlib.h// qsort 的比较函数// 返回值 0 → 交换 0 → 不交换intint_cmp(constvoid*p1,constvoid*p2){//void*不能直接解引用要强制转换成int*类型在解引用return(*(int*)p1-*(int*)p2);// 只是让qsort知道该怎么排序}intmain(){intarr[]{1,3,5,7,9,2,4,6,8,0};inti0;qsort(arr,sizeof(arr)/sizeof(arr[0]),sizeof(int),int_cmp);for(i0;isizeof(arr)/sizeof(arr[0]);i){printf(%d ,arr[i]);}printf(\n);// 输出: 0 1 2 3 4 5 6 7 8 9return0;}关键点比较函数的参数是const void*使用时必须强制转换回原类型再解引用。2.3 使用 qsort 排序结构体数组定义一个学生结构体支持按年龄和按姓名两种排序方式#includestdio.h#includestdlib.h#includestring.hstructStu{charname[20];// 姓名intage;// 年龄};// 方式一按年龄排序//e1指的是第j个元素的地址这地址要从void*换成 struct Stu*,才能让编译器知道解引用需要访问多少个字节才能解引用并访问该结构体的成员intcmp_stu_by_age(constvoid*e1,constvoid*e2){//这里是结构体指针用-访问否者用* 注意整体-agereturn((structStu*)e1)-age-((structStu*)e2)-age;//return (*(struct Stu*)e1).age - (*(struct Stu*)e2).age;}// 方式二按姓名排序strcmp 比较字符串intcmp_stu_by_name(constvoid*e1,constvoid*e2){//strmp比较字符串returnstrcmp(((structStu*)e1)-name,((structStu*)e2)-name);}// 测试按年龄排序voidtest2(){structStus[]{{zhangsan,20},{lisi,30},{wangwu,15}};intszsizeof(s)/sizeof(s[0]);qsort(s,sz,sizeof(s[0]),cmp_stu_by_age);// 结果{wangwu, 15}, {zhangsan, 20}, {lisi, 30}}// 测试按姓名排序voidtest3(){structStus[]{{zhangsan,20},{lisi,30},{wangwu,15}};intszsizeof(s)/sizeof(s[0]);qsort(s,sz,sizeof(s[0]),cmp_stu_by_name);// 结果{lisi, 30}, {wangwu, 15}, {zhangsan, 20}//这里可以自行了解字符穿的比较}intmain(){test2();// 按年龄排test3();// 按姓名排return0;}代码解析const void* e1, const void* e2指向两个待比较元素的指针void* 是通用类型(struct Stu*)e1将 void* 强制转换为 struct Stu* 类型指针指向结构体的指针* (struct Stu*)e1解引用得到结构体本身(* (struct Stu*)e1).age访问结构体的 age 成员核心理解qsort 不知道你要排什么类型它只负责比和换。怎么比你通过比较函数告诉它。怎么换你通过size告诉它每个元素多大。2.4 比较函数速查排序目标比较函数核心代码整型升序return (*(int *)p1 - *(int *)p2);整型降序return (*(int *)p2 - *(int *)p1);结构体按数值return ((struct X*)e1)-field - ((struct X*)e2)-field;结构体按字符串return strcmp(((struct X*)e1)-str, ((struct X*)e2)-str);3. 模拟实现 qsort — 用冒泡排序理解泛型思想3.1 设计思路用冒泡排序的框架模仿qsort实现一个通用的排序函数bubble让它也能排任意类型。需要解决的核心问题挑战qsort 的解法我们的实现不知道元素类型用void*接收void *base不知道元素大小传size参数int size不知道怎么比较传比较函数指针int(*cmp)(void*, void*)不知道怎么交换按字节逐字节交换_swap(void*, void*, size)3.2 完整实现#includestdio.h// ── 比较函数以整型为例──//这里要用const void*是为了接收传上来的char *类型的参数在这里换成int*类型intint_cmp(constvoid*p1,constvoid*p2){return(*(int*)p1-*(int*)p2);}// ── 交换函数逐字节交换 ──// 思想不知道具体类型但知道每个元素占 size 个字节// 那就每个元素一个字节一个字节地交换void_swap(char*p1,char*p2,intsize){inti0;for(i0;isize;i){chartmp*p1;*p1*p2;*p2tmp;p1;p2;}}// ── 通用冒泡排序 ──// base: 数组首地址// count: 元素个数// size: 每个元素的大小字节// cmp: 比较函数指针voidbubble(void*base,intcount,intsize,int(*cmp)(void*,void*)){inti0;intj0;for(i0;icount-1;i){for(j0;jcount-i-1;j){// 关键通过 base j*size 和 base (j1)*size// 定位到相邻两个元素的首地址//调用int_cmp函数if(cmp((char*)basej*size,(char*)base(j1)*size)0){_swap((char*)basej*size,(char*)base(j1)*size,size);}}}}// ── 测试 ──intmain(){intarr[]{1,3,5,7,9,2,4,6,8,0};inti0;bubble(arr,sizeof(arr)/sizeof(arr[0]),sizeof(int),int_cmp);for(i0;isizeof(arr)/sizeof(arr[0]);i){printf(%d ,arr[i]);}printf(\n);// 输出: 0 1 2 3 4 5 6 7 8 9return0;}p1 指向元素A整块内存 ┌─────┬─────┬─────┬─────┐ │A字节0│A字节1│A字节2│A字节3│ └─────┴─────┴─────┴─────┘ ↓ 逐字节循环交换 ┌─────┬─────┬─────┬─────┐ │B字节0│B字节1│B字节2│B字节3│ └─────┴─────┴─────┴─────┘ p2 指向元素B整块内存 循环i从0到size-1 第i轮 1. 暂存 A[i] → tmp 2. A[i] B[i] 3. B[i] tmp3.3 逐个拆解_swap函数 — 逐字节交换void_swap(void*p1,void*p2,intsize){inti0;for(i0;isize;i){chartmp*((char*)p1i);// ①*((char*)p1i)*((char*)p2i);// ②*((char*)p2i)tmp;// ③}}图解假设交换两个 intsize 4交换前: p1 → [ byte0 | byte1 | byte2 | byte3 ] p2 → [ byte0 | byte1 | byte2 | byte3 ] 第1轮循环 (i0): 交换 byte0 第2轮循环 (i1): 交换 byte1 第3轮循环 (i2): 交换 byte2 第4轮循环 (i3): 交换 byte3 交换后: 两个 int 被完整交换核心思想void*不能直接解引用但char*可以。强转成char*后就能按字节操作管你是什么类型我都一个字节一个字节地搬bubble函数 — 地址定位(char*)basej*size// 第 j 个元素的地址(char*)base(j1)*size// 第 j1 个元素的地址图解int 数组size 4base ↓ [ 0x1000 | 0x1004 | 0x1008 | 0x100C | ... ] arr[0] arr[1] arr[2] arr[3] ↑ ↑ | | base 2*4 0x1008 base 3*4 0x100C为什么必须强转成char*因为void*不能做指针运算——不知道步长是多少。转成char*后1就是前进 1 个字节 j * size就是前进j * size个字节精确定位到第 j 个元素。3.4 泛型 vs 类型限定对比维度普通冒泡排序通用bubble参数int arr[]void *baseint size比较arr[j] arr[j1]cmp(base j*size, base (j1)*size)交换tmp arr[j]逐字节_swap适用范围只能排int数组可排任意类型整型、浮点、结构体…
