【指针进阶三】实现C语言快排函数qsort＆回调函数

0. 经典快速排序算法-Quick_sort

先来手动实现一下Quick_sort 排序函数

#include<stdio.h>
void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

void Quick_sort(int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int keyi = begin;
	int left = begin, right = end;
	while (left < right)
	{
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}
		Swap(&arr[left], &arr[right]);
	}
	int meeti = left;
	Swap(&arr[keyi], &arr[meeti]);

	Quick_sort(arr, begin, meeti-1);
	Quick_sort(arr, meeti+1, end);
	
}

void Print(int* arr, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%d\t", arr[i]);
	}
}

int main()
{
	int arr[5] = { 12,43,5,23,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Quick_sort(arr, 0,sz-1);
	Print(arr, sz);
	return 0;
}

排序结果：

 

 

但是这里有一个问题: 如果下次我想对一个结构体进行排序，我对这个排序算法的改动就会非常大（几乎每一处都有改动），下面我也给出排序结构体相应的代码实现，给各位看看。

#include<stdio.h>
#include<string.h>
typedef struct stu
{
	char name[20];
	int age;
}stu;

void Swap(stu* a,stu* b)
{
	stu temp = *a;
	*a = *b;
	*b = temp;
}

void Quick_sort(stu* ps, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = begin;
	int left = begin, right = end;
	while (left < right)
	{
		while (left < right && strcmp(ps[right].name, ps[keyi].name) >= 0)
		{
			right--;
		}
		while (left < right && strcmp(ps[left].name, ps[keyi].name) <= 0)
		{
			left++;
		}
		Swap(&ps[left], &ps[right]);
	}
	int meeti = left;
	Swap(&ps[keyi], &ps[meeti]);

	Quick_sort(ps, begin, meeti - 1);
	Quick_sort(ps, meeti+1, end);
}

void Print(stu* ps, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%s\n", ps[i].name);
	}
}

int main()
{
	stu s[3] = { {"张三",18},{"李四",20},{"王五",19} };
	int sz = sizeof(s) / sizeof(s[0]);
	Quick_sort(s,0,sz-1);
	Print(s, sz);
	return 0;
}

排序结果：

 

 由此我们就想：能不能设计出一个函数使得在给不同数据类型的元素进行排序时能够增加排序函数Quick_sort代码的复用性，因此，库函数qsort应运而生 ，那这个函数长什么样子呐？

1. qsort排序函数的基本介绍

qsort排序函数是C语言标准库里的函数,实现原理是快速排序算法,函数原型如下:

 qsort函数的相关参数的介绍和意义:

• 头文件: #include<stdlib.h>
• 返回值: 无
• void  base: 待排序数据元素的起始地址
• size_t num:  待排序数据元素的个数
• size_t width:待排序数据元素所占的大小,单位是字节
• int( * cmp)(const void*,const void*): 函数指针-比较数据元素大小的函数,排序依据

举个例子: 

#include<stdio.h>
#include<stdlib.h>
//以qsort库函数实现整型数组排序为例
int main()
{
	int arr[5] = { 12,43,5,23,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), cmp);
	//arr:数组名,也是数组首元素的地址,数值上等于首元素中4个字节中地址最低的那个字节的地址
	//sz:数组arr的元素个数
	//sizeof(arr[0]):每一个数组元素所占的字节数
	//cmp_int:回调函数-比较数组元素的函数,根据调用者的需要自行实现
	Print(arr, sz);
	return 0;
}

先抛去qsort函数具体实现不谈，看到这里，你就知道了qsort函数的灵活性在于第四个参数（比较函数）是可以根据使用者的具体排序要求来自行设计。

2. 比较函数

比较函数的设计举例：整型数组，结构体数组等等

整型数组排序：（全部代码）

担心你看花函数之间的调用关系：给你个图理解一下

 

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

int cmp_int(const void* e1, const void* e2)
{
    //比较两个整型元素
	//void*是无具体类型的指针
	//void*的指针可以接收任意类型的地址,类似垃圾桶
	//void*的指针没有具体类型,不能+1-1(因为不知道加多少)

	//升序:
	return *(int*)e1 - *(int*)e2;

	//降序:
	//return *(int*)e2 - *(int*)e1;
}


void Print(int* arr, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%d\t", arr[i]);
	}
}

void test1()
{
	int arr[6] = { 14,35,4,42,6,12 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(&arr[0], sz, sizeof(arr[0]), cmp_int);
	Print(arr, sz);
}


int main()
{
	test1();

	return 0;
}

由于void空类型的指针：

• 可以接收任何类型的指针
• 不能直接加减整数，使用前需要强转 

因为cmp比较函数需要使用者自行设计，所以对于不同的使用者在qsort函数里传给cmp函数的参数类型可能是任何类型的指针，所以在cmp比较函数内得用void*类型的指针来接收，使用时只需将void* 类型的指针做出相应的强转即可。

排序结果：

 

 

结构体数组排序：

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

typedef struct stu
{
	char name[20];
	int age;
}stu;

int cmp_struct_by_name(const void* e1, const void* e2)
{
	return strcmp(((stu*)e1)->name, ((stu*)e2)->name);//妙哉之处
}

void Print(stu* ps, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%s\n", ps[i].name);
	}
}


void test2()
{
	stu s[3] = { {"zhangsan",18},{"lisi",20},{"wangwu",19} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s,sz,sizeof(s[0]),cmp_struct_by_name);
	Print(s, sz);
}

int main()
{
	test2();

	return 0;
}

排序结果：

比较字符串用strcmp函数，头文件#include<string.h> 

• 妙哉之处：strcmp比较函数和规定的cmp比较函数的返回值的意义相同
• 返回值>0             elem1>elem2
• 返回值==0           elem1==elem2
• 返回值<0             elem1<elem2

 2. qsort函数的具体实现

学习qsort函数的具体实现，你将学到这个C语言库函数另一个绝妙的地方。

void Swap(char* buff1,char* buff2,int width)
{
	if (buff1 != buff2)
	{
		//way1
		//while (width--)
		//{
		//	char temp = *buff1;
		//	*buff1 = *buff2;
		//	*buff2 = temp;
		//	buff1++;
		//	buff2++;
		
		//way2
		for (int i = 0; i < width; i++)
		{
			char temp = *(buff1+i);
	        *(buff1+i) = *(buff2+i);
	        *(buff2+i) = temp;
		}
	}
}

void bubble_sort(void* base, int sz, int width, int(*cmp)(const void*, const void*))
{
	int flag = 1;
	//趟数
	for (int i = 0; i < sz-1; i++)
	{
		for (int j = 0; j < sz - 1 - i; j++)
		{
			if (cmp_struct_by_name((char*)base + j * width, (char*)base + (j+1) * width)>0)
			{
				Swap((char*)base + j * width, (char*)base + (j+1) * width, width);
				flag = 0;
			}
		}
		if (flag == 1) break;
	}
}

巧妙之处在于将实际参数void* 类型的base指针强转为char*类型。

类比int arr[5]={34,5,35,62,1};
Print(arr,5),这里的arr其实就是首元素的地址，在数值上和首元素4个字节中最低字节的地址是相同的，所以cmp函数的参数即使是char* 一个字节的地址，在cmp函数内同样可以强转为所需要的类型，进行解引用，拿到相应的字节数进行比较，这样就能做到在bubble_sort函数内得到统一，所以无论我们要对任何类型的数据进行排序，都可以直接调用bubble_sort函数，只需要更改cmp函数即可，这就增加了bubble_sort函数代码的复用性。