• 进阶指针（三）--- qsort函数(快速排序)的使用和（用冒泡排序）模拟实现

    图片来源于网络

    ✨博客主页：小钱编程成长记
    🎈博客专栏：进阶C语言
    🎈推荐相关博文：进阶C语言（一）、进阶C语言（二）

    进阶指针（三）

    8.回调函数（下）

    我们接着上次的回调函数开始讲解剩下的qsort部分，如果没看过的话，大家可以先看看进阶C语言（二）

    8.2 qsort函数的使用

    8.2.1 介绍：

    回调函数的案例：qsort

    • qsort是一个库函数，头文件是stdlib.h，声明头文件后可直接使用。
    • qsort是底层使用的快速排序的方式，是对数据进行排序的。
    • qsort可以用来排序任意类型的数据。

    我们可以在网站cplusplus中查询这个函数的使用方法。
    来自网络截图

    qsort函数，有四个参数： 
    void qsort(void* base,//待排序数组的第一个元素的地址，并将其转化为void*型
			size_t num,//待排序数组的元素的个数
			size_t size,//待排序数组的一个元素的大小（单位字节）
			
			int (*compar)(const void* e1, const void* e2)
			//函数指针---compar指向了一个函数，这个函数是用来比较两个元素的; 
			//e1,e2中存放的是需要比较的两个元素的的地址
			);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    compar函数: 
    //举例： 
比较函数--提供整型数据的比较方法 
int compar(const void* e1, const void* e2)  
{ 		
	return *(int*)e1 - *(int*)e2;//升序排序， 	
//当结果>0（e1指向的元素位于e2之后）时，返回一个>0的数； 	 	 
//当结果==0（e1指向的元素和e2指向的元素相同），返回0；
//当结果<0（e1指向的元素位于e2之前）时，返回一个<0的数； 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    注意重点：

    1.排序整型数组，两个元素可以直接用>比较
    2.排序结构体数组，两个结构体的数据可能不能直接使用>比较，
    》也就是说，不同类型的数据，比较大小的方式有差异。

    • void* 是无具体类型的指针类型
    • void* 类型的指针可以存放各种类型数据的地址
    • void* 类型的指针不能解引用，也不能进行 ± 整数的操作(因为是无类型，不知道要跳过几个字节)

    void* 类型的指针不能解引用，我们可以先强转为其它类型再进行±操作。
    qsort并不知道它要排序的数组中元素的类型，并且不同类型数据的比较方式不同。
    所以在使用qsort之前，要先给它提供要比较的类型数据的比较方法。

    8.2.1 用qsort函数排序整型数组

    用qsort函数排序整型数组

#include 
#include 

//比较函数--提供整型数据的比较方法
int int_compar(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;//升序排序，
	//当结果>0（e1指向的元素位于e2之后）时，返回一个>0的数；
	//当结果==0（e1指向的元素等于e2指向的元素）时，返回0；
	//当结果<0（e1指向的元素位于e2之前）时，返回一个<0的数；
}

//打印函数
void print(int arr[], size_t sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

int main()
{
	int arr[] = { 0,9,8,7,6,5,4,3,2,1 };
	size_t sz = sizeof(arr) / sizeof(arr[0]);
	print(arr, sz);
	//快速排序
	qsort(arr, sz, sizeof(arr[0]), int_compar);
	print(arr, sz);
	return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    8.2.3 用qsort函数排序结构体数组

    #include 
#include 
#include 

//结构体
struct Stu
{
	char name[20];
	int age;
};



按年龄排序
打印函数
//void print_test1(struct Stu *s1, size_t sz)
//{
//	int i = 0;
//	for (i = 0; i < sz; i++)
//	{
//		printf("%s %d ", s1[i].name, s1[i].age);
//	}
//	printf("\n");
//}
//
比较函数
//int compare_age(const void* e1, const void* e2)
//{
//	return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
//}
//
//void test1()
//{
//	struct Stu s1[] = { {"zhangsan", 20},{"lisi", 12},{"wangwu", 30} };
//	size_t sz = sizeof(s1) / sizeof(s1[0]);
//
//	print_test1(s1, sz);//排序前
//	qsort(s1, sz, sizeof(s1[0]), compare_age);
//	print_test1(s1, sz);
//}



//按名字字母ASCII从小到大排序
//打印函数
void print_test2(struct Stu* s2, size_t sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%s %d ", s2[i].name, s2[i].age);
	}
	printf("\n");
}

//比较函数
int compare_name(const void* e1, const void* e2)
{
	return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}

void test2()
{
	struct Stu s2[] = { {"zhangsan", 20},{"lisi", 12},{"wangwu", 30} };
	size_t sz = sizeof(s2) / sizeof(s2[0]);

	print_test2(s2, sz);//排序前
	qsort(s2, sz, sizeof(s2[0]), compare_name);
	print_test2(s2, sz);
}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77

    8.3 用冒泡排序模拟实现qsort函数的快速排序

    目标： 包含回调函数，使用冒泡排序的算法，模拟实现一个排序函数(qsort)，可以排序任意类型的数据。

    8.3.1 回顾冒泡排序

    冒泡排序的思想： 两两相邻的元素进行比较

    在这里插入图片描述
    在这里插入图片描述

    //冒泡排序
#include 

//冒泡排序函数
void bubble_sort(int arr[], size_t sz)
{
	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;
			}		
		}
	}
}

//打印函数
void print_arr(int arr[], size_t sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void test()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };//降序
	size_t sz = sizeof(arr) / sizeof(arr[0]);
	print_arr(arr, sz);//排序前
	
	//升序排列
	bubble_sort(arr, sz);
	print_arr(arr, sz);//排序后
}


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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    8.3.2 开始模拟

    通过上面对冒泡排序的回顾，我们得到冒泡排序函数的基本框架：

    //冒泡排序函数
void bubble_sort(int arr[], size_t sz)
{
	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;
			}		
		}
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    qsort函数：

    在这里插入图片描述

    如何模拟：

    1. 首先要给冒泡排序函数传递数组的首元素地址，
      因为我们要模仿qsort排序任意类型的数据，所以形参要能接收任意类型的地址。
      上篇文章讲了void* 类型的指针可以接收任意类型的地址，所以参数我们可以这样写bubble_sort(void *base)

    2. 想要给任意一个数组排序，都要先知道数组有几个元素，
      因为计算数组 / 元素大小的操作数sizeof的返回值是size_t类型的，
      所以参数可以写成bubble_sort(void *base, size_t num)

    3. 有了首元素地址和数组元素个数还不够，还不能知道每个元素的地址。
      站在冒泡排序函数的角度并不知道传来的是什么类型的地址，所以不能通过指针+1的方式找到下一个元素的地址，
      在这里插入图片描述
      但是我们可以将要排序数组每个元素的大小（字节）传过来，知道了一个元素有几个字节，指针跳过这几个字节就指向了下一个元素。 所以参数可以写成bubble_sort(void *base, size_t num, size_t size)

    4. 进阶指针（三）中讲过，不同类型的数据比较大小的方式可能不同， 所以要排序数据的程序员需要先给冒泡排序函数 传 数据的比较函数，冒泡排序函数用函数指针接收，所以参数可以写成 bubble_sort(void *base, size_t num, size_t size, int compar(const void *e1, const void *e2))

    5. 比较函数:
      int compar(const void *e1, const void *e2)
      因为要排序多种类型的数据，所以要用void*类型的指针接收。
      e1是一个指针，存放一个要比较元素的地址
      e2是一个指针，存放一个要比较元素的地址
      e1指向的元素 > e2指向的元素，返回 > 0的整型数字
      e1指向的元素 == e2指向的元素，返回整型数字0
      e1指向的元素 < e2指向的元素，返回 < 0的整型数字
      这也是比较函数返回类型是int的原因。

    6. 在冒泡排序函数中要调用比较函数，来判断两个元素是否需要交换，返回值>0交换。
      比较函数中的参数应该填要比较元素，那就要先找到元素的地址。
      站在冒泡排序函数的角度并不知道传来的是什么类型的地址，所以不能通过指针+1的方式找到下一个元素的地址。
      已知首元素的地址，元素的个数num，一个元素占size字节，我们可以将首元素的地址强转成char*型的，指针向后移size个字节就指向了下一个元素，（一个size个字节大小的元素的地址，在数值上==这个元素所占的第一个字节的地址）
      (char *) base + size * 1 就是下标为1的元素的地址，
      (char *)base + size * j 是下标为 j 的元素的地址,
      (char *)base + size * (j+1) 是下标为 j+1 的元素的地址。
      在这里插入图片描述

    //冒泡排序函数
void bubble_sort(const void *base, size_t num, size_t size, int compar(const void *e1, const void *e2))
{
	int i = 0;
	//冒泡排序的趟数
	for (i = 0; i < num-1; i++)
	{
		int j = 0;
		//每趟要比较的对数
		for (j = 0; j < num - 1 - i; j++)
		{
			//判断是否要交换
			if ((compar((char*)base + size*j, (char*)base + size*(j+)) > 0)
			{
				//交换
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}		
		}
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    1. 如果两个元素需要交换，因为站在冒泡排序函数的角度不知道有排序数组的类型，所以不能直接用 * 解地址将元素整个交换。（*访问的范围是类型的大小）。
      我们知道一个元素有size个字节，所以可以一个字节一个字节的交换，先创建一个字节的空间用来过渡，通过这个空间来交换。
      在这里插入图片描述
    //注意：函数不能嵌套定义
//交换函数
void swap(char *buf1, char *buf2)
{
	char tmp = *buf1;
	*buf1 = *buf2;
	*buf2 = tmp;
} 

//判断是否要交换
if ((compar((char*)base + size*j, (char*)base + size*(j+)) > 0)
{
	//交换
	swap((char*)base + size*j, (char*)base + size*(j+1))
}		

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    8.3.3 代码展示

    //交换函数
void swap(char *buf1, char *buf2)
{
	char tmp = *buf1;
	*buf1 = *buf2;
	*buf2 = tmp;
} 

//冒泡排序函数---泛型编程-什么类型都支持的编程
void bubble_sort(const void *base, size_t num, size_t size, int compar(const void *e1, const void *e2))
{
	int i = 0;
	//冒泡排序的趟数
	for (i = 0; i < num-1; i++)
	{
		int j = 0;
		//每趟要比较的对数
		for (j = 0; j < num - 1 - i; j++)
		{
			//判断是否要交换
			if ((compar((char*)base + size*j, (char*)base + size*(j+)) > 0)//此时，compar指向的函数就是回调函数
			{
				//交换
				swap((char*)base + size*j, (char*)base + size*(j+1))
			}		
		}
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    8.3.4 用新的冒泡排序函数排序整型数组

    #include 


通用冒泡函数
//交换函数
void swap(char* buf1, char* buf2, size_t size)
{
	int i = 0;
	for (i = 0; i < size; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}

//泛型编程---什么类型都支持的编程
void bubble_sort(const void* base, size_t num, size_t size, int compar(const void* e1, const void* e2))
{
	int i = 0;
	//冒泡排序的趟数
	for (i = 0; i < num - 1; i++)
	{
		//一趟冒泡排序
		int j = 0;
		for (j = 0; j < num - 1 - i; j++)
		{
			//通过比较判断两个元素是否需要交换
			if (compar((char*)base + size * j, (char*)base + size * (j + 1)) > 0)
			{
				//交换
				swap((char*)base + size * j, (char*)base + size * (j + 1), size);
			}
		}
	}
}



//打印函数
void print_test1(int* arr, size_t sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

//比较函数
int compare_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}

//主要程序
void test1()
{
	int arr[] = { 0,9,8,7,6,5,4,3,2,1 };
	size_t sz = sizeof(arr) / sizeof(arr[0]);

	print_test1(arr, sz);
	bubble_sort(arr, sz, sizeof(arr[0]), compare_int);
	print_test1(arr, sz);
}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74

    流程图展示

    在这里插入图片描述

    8.3.5 用新的冒泡排序函数排序结构体数组

    注意：
    • ->的优先级比 强制转换操作符 高。
    • strcmp用来比较字符串，头文件是string.h
    • 函数在使用之前要先声明，函数的定义也是一种特殊的声明
    #include 
#include 

通用冒泡函数
//交换函数
void swap(char* buf1, char* buf2, size_t size)
{
	int i = 0;
	for (i = 0; i < size; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}

//泛型编程---什么类型都支持的编程
void bubble_sort(const void* base, size_t num, size_t size, int compar(const void* e1, const void* e2))
{
	int i = 0;
	//冒泡排序的趟数
	for (i = 0; i < num-1; i++)
	{
		//一趟冒泡排序
		int j = 0;
		for(j=0; j<num-1-i; j++)
		{
			//通过比较判断两个元素是否需要交换
			if (compar((char*)base + size * j, (char*)base + size * (j + 1)) > 0)
			{
				//交换
				swap((char*)base + size * j, (char*)base + size * (j + 1), size);
			}
		}
	}
}





//结构体
struct Stu
{
	char name[20];
	int age;
};


按年龄比较
比较函数——给排序函数提供要排序的数据的比较方法。函数在使用之前要先声明，函数的定义也是一种特殊的声明
//int compar_age(const void* e1, const void* e2)
//{
//	return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
//}
//
//
//
打印函数
//void print_test1(struct Stu* S1, size_t sz)
//{
//	int i = 0;
//	for (i = 0; i < sz; i++)
//	{
//		printf("%s %d  ", S1[i].name, S1[i].age);
//	}
//	printf("\n");
//}
//
//
主要程序
//void test1()
//{
//	struct Stu S1[] = { {"zhangsan", 20},{"lisi", 12},{"wangwu", 30} };
//	size_t sz = sizeof(S1) / sizeof(S1[0]);
//
//	print_test1(S1, sz);//排序前
//
//	bubble_sort(S1, sz, sizeof(S1[0]), compare_age);//按年龄排序
//	print_test1(S1, sz);//排序后
//}




//按名字的字母大小(ASCII)从小到大排序

//打印函数
void print_test2(struct Stu* S2, size_t sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%s %d ", S2[i].name, S2[i].age);
	}
	printf("\n");
}


//比较函数
int compare_name(const void *e1, const void *e2)
{
	return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);//->的优先级比 强制转换操作符 高。strcmp用来比较字符串，头文件是string.h
}


//主要程序
void test2()
{
	struct Stu S2[] = { {"zhangsan", 20},{"lisi", 12},{"wangwu", 30} };
	size_t sz = sizeof(S2) / sizeof(S2[0]);

	print_test2(S2, sz);//排序前
	bubble_sort(S2, sz, sizeof(S2[0]), compare_name);//按名字排序
	print_test2(S2, sz);
}



int main()
{
	//test1();
	test2();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126

    总结

    本篇文章我们学习了qsort函数，如何用冒泡排序模拟qsort函数实现能够排序任意类型的数据。最后，感谢大家的阅读！大家一起进步！

    点赞收藏加关注，C语言学习不迷路！
    图片来源于网络

  • 相关阅读:
    安装micropython到esp8266
    【面经】美团大数据开发面经
    创邻科技获评环紫金港创新生态圈智源创新企业
    Java学习笔记---多态
    Mac navicat连接mysql出现1045 - Access denied for user ‘root‘
    Python操控HDFS
    Sping源码（九）—— Bean的初始化（非懒加载）— Bean的创建方式（factoryMethod）
    UI自动化测试、接口测试等自动化测试
    IDEA项目下不显示target目录或者target目录不完整没有新添加的资源，idea隐藏target目录
    鉴源论坛 · 观模丨形式化建模（一）
  • 原文地址：https://blog.csdn.net/xue_bian_cheng_/article/details/133421098