目录
前言
一、回调函数
二、qsort函数
2.1 使用qsort函数排序整型数据
2.2 使用qsort排序结构数据
三、qsort函数的模拟实现
总结
前言
今天我们主要来学习一下C语言中的qsort排序函数。
一、回调函数
回调函数就是⼀个通过函数指针调用的函数。
如果你把函数的指针（地址）作为参数传递给另⼀个函数，当这个指针被用来调用其所指向的函数
时，被调用的函数就是回调函数。回调函数不是由该函数的实现方直接调用，⽽是在特定的事件或
件发生时由另外的⼀⽅调⽤的，用于对该事件或条件进⾏响应。
我们之前写的计算器程序，也可以用回调函数来完成：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int add(int a, int b)
{return a + b;
}
int sub(int a, int b)
{return a - b;
}
int mul(int a, int b)
{return a * b;
}
int div(int a, int b)
{return a / b;
}
void num(){printf("*************************\n");printf(" *****1:add 2:sub********\n");printf(" *****3:mul 4:div********\n");printf(" *****0:exit ********\n");printf("*************************\n");
}
int col(int(*pf)(int, int)) {int x, y = 0;scanf("%d%d", &x, &y);int z = pf(x, y);return z;
}
int main() {int input = 1;int (*pf[5])(int, int) = { 0,add,sub,mul,div };do{num();printf("请选择：");scanf("%d", &input);int z = 0;switch (input) {case 1:z=col(add);printf("%d\n", z);break;case 2:z=col(sub);printf("%d\n", z);break;case 3:z=col(mul);printf("%d\n", z);break;case 4:z=col(div);printf("%d\n", z);break;case 0:printf("退出程序\n");break;default:printf("输入错误\n");}} while (input);return 0;
}int main() {int arr[10] = { 1,2,3,4,5,1,2,3,4,6 };int sz = sizeof(arr) / sizeof(arr[0]);int i,j= 0;for (i = 0; i < sz; i++) {int count = 0;for (j = 0; j < sz; j++) {if (arr[i] == arr[j])count++;}if (count == 1)printf("%d ", arr[i]);}}二、qsort函数
qsort函数定义
对数组的元素进行排序
对数组中按base数指向的 num 个元素进行排序，每个元素size字节长，使用 compar 函数确定顺序。
语法形式：
void qsort (void* base,指针，指向待排数组的第一个元素 size_t num, //是base指向待排数组的元素个数size_t size,//是base指向待排数组的元素大小int (*compar)(const void*,const void*));//函数指针 指向两个元素比较的函数
其中compar函数的返回值有三种情况：
如果前一个元素比后一个元素大，返回值大于零，相等返回值等于零，小返回值小于零。
2.1 使用qsort函数排序整型数据
#include <stdio.h>
//qosrt函数的使⽤者得实现⼀个⽐较函数
int int_cmp(const void * p1, const void * p2)
{return (*( int *)p1 - *(int *) p2);
}
int main()
{int arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };int i = 0;qsort(arr, sizeof(arr) / sizeof(arr[0]), sizeof (int), int_cmp);for (i = 0; i< sizeof(arr) / sizeof(arr[0]); i++){printf( "%d ", arr[i]);}printf("\n");return 0;
}其中int_cmp就是 compar 函数来确定两个元素的大小
int int_cmp(const void * p1, const void * p2)
{return (*( int *)p1 - *(int *) p2);//需要强制类型转换为int *
}
2.2 使用qsort排序结构数据
实现我们来定义一个结构体
struct stu
{ char name[20];int age;
};
//假设按照年龄来⽐较
int cmp_stu_by_age(const void* e1, const void* e2)
{return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;//强制类型转换为结构体指针
}
//strcmp - 是库函数，是专⻔⽤来⽐较两个字符串的⼤⼩的
//假设按照名字来⽐较
int cmp_stu_by_name(const void* e1, const void* e2)
{return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}
//按照年龄来排序
void test2()
{struct Stu s[] = { {"zhangsan", 20}, {"lisi", 30}, {"wangwu", 15} };int sz = sizeof(s) / sizeof(s[0]);qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);
}
//按照名字来排序
void test3()
{struct Stu s[] = { {"zhangsan", 20}, {"lisi", 30}, {"wangwu", 15} };int sz = sizeof(s) / sizeof(s[0]);qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);
}
int main()
{test2();test3();return 0;
}按名字排序：
按年龄排序：
在上面我们采取了两种方法，分别是比较名字(字符串)或者比较年龄(整型)两种方式。
三、qsort函数的模拟实现
使用回调函数，模拟实现qsort（采用冒泡的⽅式）。
我们之前讲过如何进行冒泡排序，我们今天来试试通过冒泡排序来实现qsort函数
我们知道qsort函数有四个参数，那么我们定义的函数应该也要有四个参数：
bubb_comp_qsort(arr, sz, width, int_cmp); 和qsort类似，分别是第一个元素地址，数组大小，数组每个元素大小，元素比较函数。
首先是主函数：
int main() {int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };size_t sz = sizeof(arr) / sizeof(arr[0]);size_t width = sizeof(arr[0]);bubb_comp_qsort(arr, sz, width, int_cmp);int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}
}其中qsort函数可以接受不同类型的数据，所以我们冒泡函数的判断和交换语句就要发生改变：
void bubb_comp_qsort(void* bash, size_t sz, size_t width, int(*cmp)(void*, void*)) {int i = 0;for (i = 0; i < sz - 1; i++) {int j = 0;for (j = 0; j < sz - 1 - i; j++) {if (cmp((char*)bash + j * width, (char*)bash + (j + 1) * width) > 0){_swap((char*)bash + j * width, (char*)bash + (j + 1) * width, width);}}}}首先是比较函数cmp
int int_cmp(const void* p1, const void* p2)
{return (*(int*)p1 - *(int*)p2);
}这里需要两个地址来当函数参数，我们给bash进行强制类型转换为char*(更好的计算，如果转换为int*指针，加1跳过四个字节，如果元素大小为7个字节，那么不会加到7）
然后在加上j乘以每个元素的大小就是元素的地址来，后一个元素地址就是j+1；
接下来如果条件判定成功，就交换函数了
void _swap(void* p1, void* p2, size_t width) {int i = 0;for (i = 0; i < width; i++) {char tmp = *((char*)p1 + i);*((char*)p1 + i) = *((char*)p2 + i);*((char*)p2 + i) = tmp;}
}其中需要的也是两个元素的地址，同时也要知道元素的大小(宽度),不然不知道交换到哪里。
我们采用一个字节一个字节交换，进行循环，循环次数就是元素的大小。
完整代码：
#include <stdio.h>int int_cmp(const void* p1, const void* p2)
{return (*(int*)p1 - *(int*)p2);
}
void _swap(void* p1, void* p2, size_t width) {int i = 0;for (i = 0; i < width; i++) {char tmp = *((char*)p1 + i);*((char*)p1 + i) = *((char*)p2 + i);*((char*)p2 + i) = tmp;}
}void bubb_comp_qsort(void* bash, size_t sz, size_t width, int(*cmp)(void*, void*)) {int i = 0;for (i = 0; i < sz - 1; i++) {int j = 0;for (j = 0; j < sz - 1 - i; j++) {if (cmp((char*)bash + j * width, (char*)bash + (j + 1) * width) > 0){_swap((char*)bash + j * width, (char*)bash + (j + 1) * width, width);}}}}
int main() {int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };size_t sz = sizeof(arr) / sizeof(arr[0]);size_t width = sizeof(arr[0]);bubb_comp_qsort(arr, sz, width, int_cmp);int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}
}
总结
上述文章我们继续深入了解指针，同时讲了qsort函数的运用和实现。希望对你有所帮助。
![[leetcode~dfs]1261. 在受污染的二叉树中查找元素](https://img-blog.csdnimg.cn/direct/12acb393fa414fe2bb0638f023b681fb.png)
