用冒泡排序完成库函数qsort的作用

Hello，今天分享的是我们用冒泡函数实现qsort，也就是快排，之前我们也讲过库函数qsort的使用方法，今天我们尝试用冒泡函数实现一下，当然我们也见过qsort，后面也会继续完善的。这几天我是破防大学生，唉！
先来看一下qsort是怎样的，我们可以登录网站cplusplus


通过该网站我们可以看到的是qsor的使用方法，首先我们可以看到它的返回类型是void，参数有base，num，size，还有compar我们通过英文可以看到的是base其实就是我们要排序的东西，前面用的是一个void*
的指针，void我们可以把它看成其实就是一个垃圾桶，它什么都能接收，它可以接收数组，也可以是结构体，所以这里void* 说明这个指针指向的类型可以是int 也可以是结构体 也可以是double类型的，反正都可以的。

那我们先写一个冒泡函数是怎样的，相信看过我之前文章的人这个应该会了吧，手撕冒泡排序。

void bubble(int* arr, int sz)
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		for (j = 0; i < sz - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = arr[j];
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

来看我们的冒泡程序，第一个循环决定的是我们排序的趟数，比如我们十个元素，难道我们要排序十次吗，其实九次就可以，最后一次已经有序了，那这样就不需要排序了，所以只需要九次，因为我们假设是升序，那就是前一个大于后一个的时候才要交换，所以第一趟的时候我们就可以把最大的数放到最后了，所以我们需要减去i在后面循环的时候。冒泡排序对于大家来说肯定已经很简单了。
那我们模拟实现qsort的时候用冒泡排序该怎么做呢，首先我们可以用qsort的参数

那我们也就可以这样写void bubble(void* base, int num, int sz, int (*cmp)(const void*, const void*))，这样之后我们需要做的其实和冒泡排序的思路是一样的，第一个循环的趟数，所以我们可以看到的是下面的代码

void bubble(void* base, int num, int sz, int (*cmp)(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 (cmp((char*)base + j * sz, (char*)base + (j + 1) * sz) > 0)
			{
				swap((char*)base + j * sz, (char*)base + (j + 1) * sz, sz);
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

我这里就全部放出来了，也比较好解释说明，首先我们比较这里是用一个函数来判断是否大于0，函数该怎么实现呢，这里穿的参数是一个特别重要的地方，为什么这么说，看到代码首先我们先要强转成char*类型，因为这样才方便我们后续的访问，我们可以先来看一下比较函数

int cmp(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
1
2
3
4

我们比较的是整型，所以我们要先强转成整型，然后才能开始访问解引用的操作，我们接收指针也用void类型，所以这里也有好处，就是我们可以比较任何类型的数据，比如double类型，我们需要改变的就是强转成double类型就可以，结构体也是可以进行排序的，这样是不是满足我们快排可以排很多的数据。
那我们再来完善一下swap函数，看代码发现其实我们传参数是一样的，这是为什么呢，因为我们不知道他是什么类型的数据，那这里需要我们一个一个字符，我们要知道这个类型的数据大小，所有还要传一个sz的参数，那我们来看一下交换函数的代码

void swap(char* e1, char* e2,int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		char tmp = *e1;
		*e1 = *e2;
		*e2 = tmp;
		e1++;
		e2++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

这里有一个误区，我一开始也犯了，希望大家不要犯，首先我们是传指针过去，写的是char类型，接收的是char*这样的指针，然后交换的不是地址，因为指针就是地址，这个我们是知道的，所以这里我们是交换的是指针指向的字符，我们是一个一个交换的，所以外面还需要且套一个循环，这样才能全部交换，这里就是我们还要传一个参数sz的原因，下面是完整的代码

#include
void print(int arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
int cmp(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
void swap(char* e1, char* e2,int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		char tmp = *e1;
		*e1 = *e2;
		*e2 = tmp;
		e1++;
		e2++;
	}
}
void bubble(void* base, int num, int sz, int (*cmp)(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 (cmp((char*)base + j * sz, (char*)base + (j + 1) * sz) > 0)
			{
				swap((char*)base + j * sz, (char*)base + (j + 1) * sz, sz);
			}
		}
	}
}
int main()
{
	int arr[] = { 9,8,0,5,5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	print(arr,sz);
	bubble(arr, sz, sizeof(arr[0]), cmp);
	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
37
38
39
40
41
42
43
44
45
46
47
48
49
50

这里也是成功的实现我们冒泡版的qsort函数，这里先不谈效率，主要是要知道这个思想，我们后面学了八大排序会学的是快排，有三种方式可以实现，所以我们也不需要着急。

今天是在学校里写的第二篇文章，昨天电脑坏了，要重装系统，最近总是不顺利，不顺利的时候就会特别难过，也希望自己这几天能调整好心态，谢谢大家，我们后面接着分享，大家一起进步！！！