模拟实现qsort万能排序

引言📃

如果读者学过排序算法，应该知道我们初阶学习的排序算法其实只能排整型类型的数据，而我们即将要解析的qsort函数则是一个万能的排序函数，它可以排序各种类型的数据。

接下来，我们将从引言初识、使用、模拟实现来深度解析这个库函数。

qsort包含于<stdlib.h> 头文件内。

1️⃣下面看一下qsort函数的参数：

2️⃣对于qsort函数参数的认识：

• base的类型是void*（无具体类型的指针），它的意义是指向起始地址。
• num的类型是size_t（无符号整型unsigned int），它的意义是将待排序数组内的元素个数传过来。
• width的类型是size_t（无符号整型unsigned int），它的意义是将待排序数组内每个元素的大小（byte）传过来。
• compare的类型是int (*)(void* , void*)的函数指针，它的意义是指向一个比较函数。

3️⃣void*类型的认识和compare指针的用法：

1. void*类型：

因为我们的目的是需要排序所有的数据类型，那么如果我们将接收待排序的数据的参数类型设置为char/int/float，无论是设计为其中的哪一种，我们最终结果都只能排序这一种类型。这时，我们就将接收数据的参数类型设置无具体类型的指针也就是void*。

• void*类型的指针可以接收任意数据类型的地址。
• 但是因为它没有具体类型，它是不能够进行运算的，并且也不能够解引用。

注意⚠：因为qsort函数通过void*类型接收数据，那么传参过来的数据将会因为void*而变得未知，可是如果我们排序，我们需要知道待排序的数据的个数和每个数据的类型吧（因为每个数据类型的大小我们都知道）？可是数据的类型不得而知，那么我们总得知道每个数据的大小（以字节为单位）吧？这就引出了num和width这两个参数。

2. compare指针：

int (*compare)(const void *elem1, const void *elem2);

可以发现，compare是一个函数指针，它是int (*)(void*, void*)的指针类型。我们说compare指向一个比较函数，这个函数的返回值类型是int，形参是(void*, void*)。

假设这个比较函数形式为：int cmp(const void *elem1, const void *elem2);则：

• 如果elem1 > elem2，比较函数返回值>0
• 如果elem1 = elem2，比较函数返回值=0
• 如果elem1 < elem2，比较函数返回值<0

注意⚠：因为不同的数据类型比较的方式可能不尽相同，要实现排序不同数据类型需要将比较数据这一步单独抽离出来封装。故使用时，compare指向的比较函数需要自己根据需求实现。

学会使用📝qsort

使用qsort函数的例子（附注释）下面是这几个例子的函数声明：

int cmp_name(const void* elem1, const void* elem2);//比较名字的回调函数
int cmp_age(const void* elem1, const void* elem2);//比较年龄的回调函数
int cmp_int(const void* elem1, const void* elem2);//比较整型数据的回调函数
int cmp_float(const void* elem1, const void* elem2);//比较浮点型的回调函数

在这段代码中笔者并没有直接将结果打印到控制台上以便直接向读者展现排序后的效果，而是建议读者拷贝到编译器上自己一步步调试观察。

//qsort的使用
#include<stdlib.h>
#include<string.h>

int cmp_name(const void* elem1, const void* elem2);//比较名字的回调函数
int cmp_age(const void* elem1, const void* elem2);//比较年龄的回调函数
int cmp_int(const void* elem1, const void* elem2);//比较整型数据的回调函数
int cmp_float(const void* elem1, const void* elem2);//比较浮点型的回调函数

//定义一个包含name和age的结构体类型
struct student
{
	char name[20];
	int age;
};
int main()
{
	//创建结构体数组
	struct student s[3] = { {"zhangsan",8},{"lisi",3},{"wangwu",29} };
	//元素个数
	int sz = sizeof(s) / sizeof(s[0]);
	//按照名字来排序
	qsort(s, sz, sizeof(s[0]), cmp_name);
	//按照年龄来排序
	qsort(s, sz, sizeof(s[0]), cmp_age);

	//创建整型数组
	int arr[10] = { 9,8,7,6,5,4,3,2,1 };
	int sz1 = sizeof(arr) / sizeof(arr[0]);
	//按照整型来排序
	qsort(arr, sz1, sizeof(arr[0]), cmp_int);

	//创建浮点型数组
	float f[] = { 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0 };
	int sz2 = sizeof(f) / sizeof(f[0]);
	//按照浮点型来排序
	qsort(f, sz2, sizeof(f[0]), cmp_float);
}
//比较age的回调函数
int cmp_age(const void* elem1, const void* elem2)
{	//必须要先将void*类型强制转换为所需的类型
	return ((struct student*)elem1)->age - ((struct student*)elem2)->age;
}
//比较name的回调函数
int cmp_name(const void* elem1, const void* elem2)
{
	return strcmp(((struct student*)elem1)->name, ((struct student*)elem2)->name);
}
//比较int型数据的回调函数
int cmp_int(const void* elem1, const void* elem2)
{
	return *(int*)elem1 - *(int*)elem2;
}
//比较float型数据的回调函数
int cmp_float(const void* elem1, const void* elem2)
{	//因为比较函数的返回类型是int，故最后的返回类型需要强转为int
	return (int)(*(float*)elem1 - *(float*)elem2);
}

需要注意的几个点（比较函数的返回值和形参）在注释里都有提到，这里为读者再次总结：

qsort函数的最后一个参数为函数指针，指向一个比较函数，这个比较函数需要比较不同的类型的数据从而实现通用排序，而函数同样为了接收各种类型的数据但是需要避免类型不匹配，所以将形参类型设计为无具体类型的指针void*，所以函数也不知道自己接收的参数是什么类型的数据，所以这时的比较函数就需要程序员自己来实现。

1. 比较函数的返回类型为int，返回类型若不是int则需要强转为与函数返回类型匹配的类型。
2. 比较函数的两个形参为void*，在进行运算的时候需要将void*转换为所需的类型。

模拟实现💖my_qsort

既然这个函数这么厉害，我们自己模拟实现它才是对它最大的respect！这也使得我们可以快速的学习到它底层实现的原理，我们以最基本的冒泡排序（Bubble_sort）来实现qsort的底层排序。

//万能排序函数
void my_qsort(void* base, int num, int width, int (*compare)(const void*, const void*));
//交换函数
void swap(char* elem1, char* elem2, int width);

实现自己的my_qsort排序函数（以冒泡排序作为底层来排序）

//排序函数
void my_qsort(void* base, int num, int width, int (*compare)(const void*, const void*))
{
	int i = 0;
	for (i = 0; i < num - 1; i++)
	{
		int j = 0;
		for (j = 0; j < num - 1 - i; j++)
		{
			if ( (compare((char*)base + j * width, (char*)base + (j + 1) * width)) > 0 )
			{
				swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
	}
}
//交换函数，因为形参类型设计为char*，故只能一个字节一个字节的交换以达到互换数据的目的
void swap(char* elem1, char* elem2, int width)
{
	int i = 0;
	for ( i = 0; i < width; i++)
	{
		char temp = *elem1;
		*elem1 = *elem2;
		*elem2 = temp;
		elem1++;
		elem2++;
	}
}

粗略看一遍代码之后可以发现，上述代码大体框架就我们所说的冒泡排序。

用冒泡排序实现的my_qsort的【区别之一】,在于判断数据大小（也可以说【比较数据大小】）的部分将通过函数指针指向的比较函数来先行进行不同数据类型的比较之后依据比较函数的返回值来进行判断。

if ( (compare((char*)base + j * width, (char*)base + (j + 1) * width)) > 0 )
{
    swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
}

这一段代码就是实现my_qsort的核心：

注意base是void*类型，那么我们实际上不知道base的数据类型。但是我们知道一个元素有多少个字节并且知道元素的个数，故此需要我们自己来计算偏移量。

• 首先我们将base类型强转为步长最小的类型char*
• (char*)base + (n * 每个元素的字节数)就可以实现指针向后走n个元素。
• 那么对比冒泡排序可知，将这里的n改为j即可。

​ 用冒泡排序实现的my_qsort的【区别之二】在于【数据的交换】的部分因为交换的就是比较后的两个值（我们刚刚已经自己计算出了偏移量可以准确得出每次循环需要比较的两个数的准确位置），故继续沿用if语句内的判断代码，而这两个值因为不知道类型都被强转为char*，所以我们在交换函数内只能一个字节一个字节的走，那么也就是只能够一个字节一个字节的进行交换。既然这样我们就需要将每个元素的字节大小也传过来进行循环交换每个字节。

void swap(char* elem1, char* elem2, int width)
{
	int i = 0;
	for ( i = 0; i < width; i++)
	{
		char temp = *elem1;
		*elem1 = *elem2;
		*elem2 = temp;
		elem1++;
		elem2++;
	}
}

（全剧终）感谢食用！
|
|
|
往期回顾：
详解浮点型在内存中的存储
字节序之Little-Endian&Big-Endian