AllinToyou

这个屌丝很懒，什么也没留下！

热门标签

【C语言进阶】qsort函数详解以及它的模拟实现

作者：AllinToyou | 2024-04-08 19:21:23

踩

qsort

一、qsort函数介绍

qsort是一个库函数，可以对任意数据类型的数组进行排序。它的底层是通过快速排序来实现的
cplusplus网站中对qsort函数的解释如下：
在这里插入图片描述
qsort的函数声明：

 void qsort (void* base, size_t num, size_t size, int (*compar)(const void*,const void*));

1
2

qsort函数的参数：

void* base
size_t num
size_t size
int(*compar)(const void*,const void*)

qsort函数的返回值：
qsort函数的返回值void型

二、qsort函数参数介绍

2.1：void* base

参数base的类型是void*（空指针），说明base是一个指针，它指向待排序数组的第一个元素，换言之：base存放的是待排序数组的首元素地址

补充：void*类型介绍：
void*是无具体指向的指针类型，任何类型变量的地址都可以存放到void型指针变量里面，这可以说是void*变量的一个优点。当然它也有一个致命的缺点：void*指针不能解引用。

为什么base的类型是void*呢?
回到base的用途，base是用来存放待排序数组首元素的地址，既然存放的是地址，那首先base一定是一个指针类型，那为什么是void型的指针呢？这就要回到qsort函数设计的初衷，qsort函数希望实现对任何类型的数组都可以排序，这就包括：整型数组、字符数组、结构体数组等等，既然面对的排序对象是各种类型的数组，那数组首元素的类型一定也是各种各样的，比如：对整型数组进行排序，数组首元素就是整型；对字符数组排序，数组首元素就是字符型。既然数组首元素的类型可能有多种，那数组首元素的地址一定也是各种各样的，可能是整型的地址，可能是字符的地址，等等。此时就要求base能够存放各种类型的地址，因此就让base是void*型。void*变量就可以存放各种类型的地址。假如：让base是int*型，当待排序的是字符数组，字符数组的首元素是一个字符，字符的地址就不能存到int*的变量里。

2.2：size_t num

num中存的是待排序数组的元素个数，他的类型是size_t，size_t其实就是把unsigned int重命名的得到的。

2.3：size_t size

size中存的是数组中每个元素的大小（以字节为单位）。

2.4：int(* compar)(const void ,const void )

compar是一个函数指针类型，所谓函数指针就是可以指向一个函数，里面存放的是函数的地址。

compar到底指向什么函数呢?
compar是英文单词compare（比较）的缩写，所以顾名思义，compar是比较的意思，说明它指向一个比较函数。

什么是比较函数？
要实现对数组元素的排序，那一定要对数组里面的元素进行逐一比较，而对于不同类型的数组来说，它们的比较方法也有所不同。比如：整型数组可以比较它们元素之间的大小关系，而字符数组则有专门的字符串比较函数strcmp，如果是一个结构体数组，一个结构体里面有不同的数据，我们就可以按照不同的标准进行排序。就像对一群人进行排序，可以按照年龄排，也可以按照身高排等等。此时就需要用户自己确定一个排序的标准，用函数封装起来，然后把这个函数的地址传给qsort函数用函数指针compar来接收。

对比较函数的要求：
形参compar已经规定了它所指向的函数类型是：int (const void*,const void).即：所指向的比较函数有两个void*类型的参数，函数的返回值是int型。

比较函数的参数、返回值的意义：
int compar (const void* p1, const void* p2);
其中两个void*类型的参数 p1 和 p2 用来存放数组中待比较的两个元素的地址。如果compar函数的返回值小于0，会把p1指向的元素排到p2指向的元素前面；如果返回值等于0，不会改变p1和p2指向的元素位置；如果返回值大于0，会把p1指向的元素排到p2指向的元素后面。

三、实际应用

3.1：利用qsort函数对整型数组排序

int comper(const void* e1, const void* e2)
//comper函数是用户自己写的，我们自己当然知道要排序的元素类型是什么
//我们就可以利用强制类型转化来实现对e1和e2的比较
{
	return *(int*)e1 - *(int*)e2;//void*类型不能直接解引用
}
//*(int*)e1 - *(int*)e2<0
//说明e1指向的元素比e2指向的元素小，此时刚好返回一个小于0的数，qsort就会把e1指向的元素排在e2指向的元素前面
//*(int*)e1 - *(int*)e2>0
//说明e1指向的元素比e2指向的元素大，此时刚好返回一个大于0的数，qsort就会把e2指向的元素排到e1指向的元素前面

int main()
{
	int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), comper);//利用库函数qsort来排序
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}
//结果：
0 1 2 3 4 5 6 7 8 9
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

3.2：利用qsort函数对结构体数组排序

按照年龄排序：

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

//根据名字比较
int comper_age(const void* e1, const void* e2)
{
	return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}

int main()
{
		struct Stu arr[3] = { {"zhangsan",100},{"lisi",20},{"wangwu",3} };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;

	//排序前打印
	for (i = 0; i < sz; i++)
	{
		printf("%s %d   ", arr[i].name, arr[i].age);
	}
	printf("\n");

	//根据年龄进行排序
	qsort(arr, sz, sizeof(arr[0]), comper_age);

	
	//排序后打印
	for (i = 0; i < sz; i++)
	{
		printf("%s %d   ", arr[i].name, arr[i].age);
	}
	printf("\n");
	return 0;
}
//结果：
zhangsan 100   lisi 20   wangwu 3
wangwu 3   lisi 20   zhangsan 100
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

按照名字进行排序：

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

//按照名字比较
int comper_name(const void* e1, const void* e2)
{
	return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e1)->name);//名字是字符串，所以名字的比较要用到字符串比较 函数strcmp
}

int main()
{
		struct Stu arr[3] = { {"zhangsan",100},{"lisi",20},{"wangwu",3} };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;

	//排序前打印
	for (i = 0; i < sz; i++)
	{
		printf("%s %d   ", arr[i].name, arr[i].age);
	}
	printf("\n");

	//按照年龄进行排序
	qsort(arr, sz, sizeof(arr[0]), comper_name);

	
	//排序后打印
	for (i = 0; i < sz; i++)
	{
		printf("%s %d   ", arr[i].name, arr[i].age);
	}
	printf("\n");
	return 0;
}
//结果：
zhangsan 100   lisi 20   wangwu 3
lisi 20   wangwu 3   zhangsan 100
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

四、利用冒泡排序模拟实现qsort函数

4.1：冒泡排序

关于冒泡排序的详细讲解可以参考我的这篇文章：初级C语言之【数组】里面详细介绍了冒泡排序

//冒泡排序函数
void bulle_sort(int* arr , int 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;
			}
		}
	}
}

int main()
{
	int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bulle_sort(arr,sz);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}
//结果：
0 1 2 3 4 5 6 7 8 9
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

缺陷1：
用来接收待排序数组首元素地址的指针arr已经被写死了，是int*型，说明只能对整型数组进行排序

缺陷2：
在这里插入图片描述
缺陷2如上图所示，红色方框框起来的部分只适用于对整数之间的大小关系进行比较，然后交换

4.2：模拟实现qsort函数

//利用冒泡排序模拟实现qsort

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

void bulle_sort(void* arr , size_t sz,size_t width,int(*comper)(const void*e1,const void*e2))
//第一个参数 - 用来接收待排序数组的首元素地址，可能会排序各种数组，所以形参数组用void*来接收
//第二个参数 - 用来接收数组元素个数
//第三个参数 - 用来接收数组元素的宽度

{
	size_t i = 0;
	//趟数
	for (i = 0; i < sz - 1; i++)
	{
		//一趟冒泡的过程
		size_t j = 0;
		for (j = 0; j < sz-1-i; j++)
		{
			if (comper((char*)arr+j*width,(char*)arr+(j+1)*width)>0)
			//把arr强转为char*，arr就可以正常使用
			//char类型指针+1只会跳过一个字节
			//+j*width表示跳过j个元素
			{
				//交换
				//由于这里的数组名已经被转为char类型的指针
				//所以要交换数组中的元素，就只能一个字节一个字节进行交换
				Swap((char*)arr + j * width, (char*)arr + (j + 1) * width,width);
				//前两个参数是待交换元素的地址，第三个参数是元素的宽度
			}
		}
	}
}
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

这里说的利用冒泡排序来实现qsort函数，仅仅是实现了qsort函数可以对任意类型的数组进行排序这一特点，并不是说实现qsort函数的底层原理，qsort的底层是通过快速排序来实现的。
因此，为了使改变之后的冒泡函数能够对任意类型的数组进行排序，原本冒泡排序函数的参数就要发生改变，和qsort函数一样，新的冒泡排序函数也要有以下4个参数：

void* arr
size_t sz
size_t width
int(*comper)(const void*e1,const void*e2)

arr用来接收待排序数组首元素的地址，sz用来接收待排序数组的元素个数，width用来接收数组中每个元素的大小（单位是字节），comper用来接收比较函数的地址。参数的改变解决了原冒泡排序函数的缺陷1。
接下来要解决原冒泡排序函数的缺陷2，缺陷2的主要问题在于它的普适性不够强，首先要对交换的判断条件，即if后面的判断语句做出改变，让他能够比较任意两个类型的数据，这时，比较函数就发挥作用了，我们只需要把待比较的两个元素地址传给比较函数，由比较函数来判断它们之间的关系
新的问题又出现了，comper函数的形参需要接收两个待比较元素的地址，这里的待比较元素一定是当前待排序数组里面的元素，但是待排序数组的首元素地址是用空指针（void*）来接收的，无法直接使用，这意味着现在无法通过数组首元素的地址，顺藤摸瓜去访问数组中的元素。这里问题的关键就是空指针无法使用，那我们就想到把空指针进行强制类型转化，把空指针变成有具体指向的指针不就可以正常使用了，问题又出现了，有那么多的指针类型，到底把空指针强转成什么类型的指针呢？？？答案是：把空指针强转成字符指针（char*）。这里是因为，字符指针+1仅跳过一个字节，我们可以通过改变加数的数值，使指针指向任意内存空间，这也就意味着强转后的arr指针可以存放任意内存单元的地址，并且可通过地址去访问内存中的数据。

(char*)arr+j*width

这里先把arr指强制类型转化成char*类型，这里的加数是：j*width。其中width表示当前数组中每个元素的大小（单位是字节），这里的+j*width就是跳过j*width个字节，由于width是一个元素的字节，所以+j*width也就意味着跳过了j个元素，此时 (char*)arr+j*width就表示下标为j的元素的地址。

(char*)arr+(j+1)*width

同理(char*)arr+(j+1)*width就表示下标为j+1的元素的地址。

此时就可以把待比较的两个元素的地址传给用户自己写的comper函数了，通过comper函数的返回值来判断这两个元素是否要交换。

到这里缺陷2中的问题只解决了一半，即：只把交换的判断条件做了修改，增强了交换判断条件的普适性，使其可以对任意类型的数组中的元素进行比较。具体的交换步骤还没有修改，当前的交换步骤仅仅适用于整型数据。根据经验，对两个变量进行交换，需要创建一个中间变量，比如：交换两个整型变量，需要创建一个整形的中间变量；交换两个字符型变量，需要创建一个字符型的中间变量……可见，对于不同类型的数据元素，在交换时创建的中间变量的类型也是不同的，由于无法预知要交换数据的类型，所以也无法提前确定中间变量的类型。这里的解决方案是：一个字节一个字节的交换，这样中间变量的类型就能确定下来了，即为char型。不同的数据类型对应着不同的字节数，但是它们都是由字节组成，我们有了数组中每个元素的字节大小时，就可以写一个循环，从元素的首个字节开始，一个字节一个字节的交换，直到最后一个字节。这里我们写了一个交换函数Swap

void Swap(char* ele1, char* ele2,int width)

Swap函数有三个参数，ele1和ele2分别用来接收待交换的两个元素的地址，width用来接收数组中每个元素的大小（单位是字节）。

void Swap(char* ele1, char* ele2,int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *ele1;
		*ele1 = *ele2;
		*ele2 = tmp;
		ele1++;
		ele2++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

到此，原来冒泡排序中的两个缺陷已经被成功地解决，经过改造后的冒泡函数bulle_sort就可以对任意类型数组进行排序。

4.3：实际应用

4.3.1：利用bulle_sort函数对整型数组排序：

//利用冒泡排序模拟实现qsort

//交换函数
void Swap(char* ele1, char* ele2,int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *ele1;
		*ele1 = *ele2;
		*ele2 = tmp;
		ele1++;
		ele2++;
	}
}
//改造后的冒泡排序函数
void bulle_sort(void* arr , size_t sz,size_t width,int(*comper)(const void*e1,const void*e2))
//第一个参数 - 用来接收待排序数组的首元素地址，可能会排序各种数组，所以形参数组用void*来接收
//第二个参数 - 用来接收数组元素个数
//第三个参数 - 用来接收数组元素的宽度
{
	size_t i = 0;
	//趟数
	for (i = 0; i < sz - 1; i++)
	{
		//一趟冒泡的过程
		size_t j = 0;
		for (j = 0; j < sz-1-i; j++)
		{
			if (comper((char*)arr+j*width,(char*)arr+(j+1)*width)>0)
			//把arr强转为char*，arr就可以正常使用
			//char类型指针+1只会跳过一个字节
			//+j*width表示跳过j个元素
			{
				//交换
				Swap((char*)arr + j * width, (char*)arr + (j + 1) * width,width);
				//前两个参数是待交换元素的地址，第三个参数是元素的宽度
			}
		}
	}
}
//比较函数
int comper_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
//主函数
int main()
{
	int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bulle_sort(arr, sz, sizeof(arr[0]), comper_int);//调用bulle_sort来排序
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}
//结果：
0 1 2 3 4 5 6 7 8 9
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

4.3.2：利用bulle_sort函数对结构体数组排序：