要学习qsort()函数首先要先了解回调函数

文章目录

• 一.回调函数
• 二.qsort函数是什么？
• 三.用qsort函数排序
• • 1. 整型
  • 2. 结构体
  • 3. 字符型
  • 4. double型
• 四.具体样例
• • 1. 整型数组排序
  • 2. 结构体数据排序
  • 3.字符型数组排序
  • 4.double型数组排序
• 五.使用冒泡排序思想模拟实现qsort函数
• • 1.冒泡排序代码
  • 2.qsort函数演示

一.回调函数

回调函数就是一个通过函数指针调用的函数。如果你把函数的指针（地址）作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，我们就说这是回调函数。回调函数不是由该函数的实现方直接调用，而是在特定的事件或条件发生时由另外的一方调用的，用于对该事件或条件进行响应。

用上一次博客里讲的计数器演示一下回调函数
看代码：

#include <stdio.h>
int Add(int x, int y)
{
	return x + y;
}
int Sub(int x, int y)
{
	return x - y;
}
int Mul(int x, int y)
{
	return x * y;
}
int Div(int x, int y)
{
	return x / y;
}
void menu()
{
	printf("******************************\n");
	printf("****   1. add    2.sub   *****\n");
	printf("****   3. mul    4.div   *****\n");
	printf("****   0. exit           *****\n");
	printf("******************************\n");
}

void Calc(int(*pf)(int, int))
{
	int x = 0;
	int y = 0;
	int ret = 0;
	printf("请输入两个操作数:>");
	scanf("%d %d", &x, &y);
	ret = pf(x, y);
	printf("%d\n", ret);
}

int main()
{
	int input = 0;
	
	do
	{
		menu();
		printf("请选择:>");
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			Calc(Add);
			break;
		case 2:
			Calc(Sub);
			break;
		case 3:
			Calc(Mul);
			break;
		case 4:
			Calc(Div);
			break;
		case 0:
			printf("退出计算器\n");
			break;
		default:
			printf("选择错误\n");
			break;
		}
	} while (input);
	return 0;
}

二.qsort函数是什么？

qsort函数是一个库函数，是一个可以用来快速排序的库函数
qsort函数与冒泡排序比它的好处是：

我们用搜索库函数的网址或者MSDN来进行查找。

参数说明：
void qsort
(void* base, //指向了待排序数组的第一个元素
size_t num, //待排序的元素个数
size_t width, //每个元素的大小，单位是字节
int (__cdecl *compare )(const void *elem1, const void *elem2 ) );//指向一个函数，这个函数可以比较2个元素的大小

返回值：

三.用qsort函数排序

1. 整型

int com_int(const void* p1,const void* p2)
{
	return *(int*)p1 - *(int*)p2;
}

2. 结构体

struct Stu
{
	char name[20];
	int age;
};

3. 字符型

int comp_char(const void* elem1, const void* elem2)
{
	return*(char*)elem1 - *(char*)elem2;	
}

4. double型

int com_float(const void* p1,const void* p2)
{
	return *(double*)p1 > *(double*)p2?1:-1;
}

注：

这里的两个浮点数相减返回的是一个int型的数，如果浮点型数组相减会丢失小数点后的部分。所以需另加处理，直接判断大小，如果p1大于等于p2，则返回1，否则返回-1。

四.具体样例

1. 整型数组排序

#include <stdio.h>
#include <stdlib.h>
//qsort函数的使用者提供这个函数
int com_int(const void* p1,const void* p2)
{
	return *(int*)p1 - *(int*)p2;
	//强制类型转化，再解引用才是对应的值
}
void print_arr(int arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void test1()
{
	int arr[10] = { 9,6,5,8,4,7,1,2,3,0 };
	int sz = (sizeof(arr) / sizeof(arr)[0]);
	//使用qsort来排序整型数组，这里就要提供一个比较函数，这个比较函数能够比较2个整数的大小
	qsort(arr,sz,sizeof(arr[0]),com_int);
	print_arr(arr, sz);
}
int main()
{
	test1() ;
	return 0;
}

运行结果：

注：

1. void* - 无具体类型的指针，所以它可以接收任何类型的地址（所以比较整形时要强制类型转换）
2. void*-的指针不能解引用操作符，也不能进行++或- -的操作
3. qsort 默认是排成升序的，若我们想排成降序，把p1改成p2就可以了

2. 结构体数据排序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Stu
{
	char name[20];
	int age;
};

//按照年龄来比较
int cmp_stu_by_age(const void* p1, const void* p2)
{
	return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age;
}
//按照名字来比较
int cmp_stu_by_name(const void* p1, const void* p2)
{
	//本质是字符串，所以用strcmp来比较
	return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
}
void test2()
{
	struct Stu s[] = { {"zhangsan", 30}, {"lisi", 25}, {"wangwu", 50} };
	int sz = sizeof(s) / sizeof(s[0]);
	//测试按照年龄来排序
	qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);
	printf("%s %d ", s[0].name, s[0].age);
	printf("%s %d", s[1].name, s[1].age); 
	printf("%s %d", s[2].name, s[2].age);
	printf("\n");
	//测试按照名字来排序
	qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);
	printf("%s %d ", s[0].name, s[0].age);
	printf("%s %d", s[1].name, s[1].age);
	printf("%s %d", s[2].name, s[2].age);
	printf("\n");

}
int main()
{
	test2();
	return 0;
}

运行结果

注：

1. 比较年龄实际上比较的是整型
2. 比较名字实际上比较的是字符串，使用strcmp()函数比较，需包含头文件#include <string.h>

3.字符型数组排序

#include <stdio.h>
#include <stdlib.h>
int comp_char(const void* elem1, const void* elem2)
{
	return*(char*)elem1 - *(char*)elem2;
	//强制类型转化，再解引用才是对应的值
}
void test3()
{
	char arr[10] = { 'g','a','c','f','d','b','e','l','h'};
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), comp_char);
	for (int i = 0; i < sz; i++)
			{
				printf("%c ", arr[i]);
			}
			printf("\n");
}
int main()
{
	test3();
	return 0;
}

运行结果：

4.double型数组排序

#include <stdio.h>
#include <stdlib.h>
int com_double(const void* p1, const void* p2)
{
	return *(double*)p1 > *(double*)p2 ? 1 : -1;
}
void test4()
{
	double arr[5] = { 5.01, 5.02, 0.02, 4.62, 3.95 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), com_double);
	for (int i = 0; i < sz; i++)
	{
		printf("%.2f ", arr[i]);
	}
	printf("\n");
}
int main()
{
	test4();
	return 0;
}

运行结果：

五.使用冒泡排序思想模拟实现qsort函数

1.冒泡排序代码

先看一下之前学过的冒泡排序代码

#include <stdio.h>
void bubble_sort(int arr[], int sz)
    //因为数组传参传的是地址，所以int arr[] 表示的依然是一个指针： int *arr 
{
	int i = 0;

	//冒泡排序的趟数
	for (i = 0; i < sz - 1; i++)
	{
		//一趟冒泡排序的过程
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}
int main()
{
	int arr[] = { 3,1,5,9,2,4,7,6,8,0 };
	//排序 - 升序
	//冒泡排序
	int sz = sizeof(arr) / sizeof(arr[0]);

	bubble_sort(arr, sz);//arr是数组首元素的地址
	//只传数组不传元素个数进去，这种算法结果是错误的
	int i = 0;
	for (i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}

2.qsort函数演示

qsort函数使用的是什么参数，我们设计的函数就用什么参数

测试函数

void test()
{
	int arr[] = { 3,1,5,2,4,9,8,6,5,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
	print_arr(arr, sz);
}

模拟实现的bubble_sort函数

void bubble_sort(void* base, size_t num, size_t width,
	int (*cmp)(const void* p1, const void* p2))
	//cmp 函数为使用的人设计的
{
	//元素个数和元素大小不可能为负数所以是size_t类型
	//要确定趟数
	size_t i = 0;
	//共进行num-1趟
	for (i = 0; i < num - 1; i++)
	{
		int flag = 1;//假设已经有序了
		//一趟冒泡排序的过程
		size_t j = 0;
		for (j = 0; j < num - 1 - i; j++)
		{
			//两个相邻的元素比较
			//比较的是这两个元素地址arr[j] arr[j+1]，所以要传地址
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
				//width--宽度
				//强制类型转换为char*，char*指针+1跳过一个字节
				//因为base为void类型，不能进行加减乘除的运算，所以强制类型转换
				flag = 0;
				
				//交换
				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
		if (flag == 1)
		{
			break;
		}
	}
}

自定义Swap用来交换的函数

void Swap(char* buf1, char* buf2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}

整体代码如下：

#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void* p1, const void* p2)
{
	return *(int*)p1 - *(int*)p2;
}
void Swap(char* buf1, char* buf2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}
//假设排序为升序
//希望这个bubble_sort函数可以排序任意类型的数据
void bubble_sort(void* base, size_t num, size_t width,
	int (*cmp)(const void* p1, const void* p2))
	//cmp 函数为使用的人设计的
{
	//元素个数和元素大小不可能为负数所以是size_t类型
	//要确定趟数
	size_t i = 0;
	//共进行num-1趟
	for (i = 0; i < num - 1; i++)
	{
		int flag = 1;//假设已经有序了
		//一趟冒泡排序的过程
		size_t j = 0;
		for (j = 0; j < num - 1 - i; j++)
		{
			//两个相邻的元素比较
			//比较的是这两个元素地址arr[j] arr[j+1]，所以要传地址
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
				//width--宽度
				//强制类型转换为char*，char*指针+1跳过一个字节
				//因为base为void类型，不能进行加减乘除的运算，所以强制类型转换
				flag = 0;
				
				//交换
				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
		if (flag == 1)
		{
			break;
		}
	}
}

void print_arr(int arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void test()
{
	int arr[] = { 3,1,5,2,4,9,8,6,5,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
	print_arr(arr, sz);
}
int main()
{
	test();
	return 0;
}

将base强制转换为char*的原因是：

char*指针+1跳过一个字节
因为base为void类型，不能进行加减乘除的运算，所以强制类型转换
+width：跳过width个字节，指向下一个元素

交换函数

因为交换函数传的是地址，所以要知道元素的宽度，把每个元素所占字节传过去

运行结果：

整体代码理解：

关于qsort()函数的讲解七七就介绍到这里了，如果这篇文章对大家有帮助，请佬佬们点个赞再走吧！如果发现什么问题，欢迎评论区留言！