【C语言】用冒泡排序实现my_qsort

大家好，我是苏貝，本篇博客带大家了解如何用冒泡排序实现my_qsort，如果你觉得我写的还不错的话，可以给我一个赞👍吗，感谢❤️

---

一. 前言

用冒泡排序实现my_qsort？你或许觉得没有必要这样做，有现成的qsort函数，为什么还要自己写一个呢？于我而言，它可以让我对冒泡排序和qsort函数的印象加深。至于这到底有没有用，仁者见仁，智者见智吧。好了，就说这么多，现在让我们来回忆一下什么是冒泡排序和qsort函数。了解qsort函数

---

二. 冒泡排序

冒泡排序的原理：从左往右，依次比较相邻元素的大小，若符合条件，则两元素位置交换，每一趟可以找出最大值或最小值，并显示在序列的最右边。注意：冒泡排序只能排序整形序列，而qsort函数可以排序任意类型的序列

以想要升序排序为例，数组{5，2，4，3}，条件：如果相邻元素的左边>右边，则两元素位置交换。第一趟：5>2，交换位置。5>4，交换位置。5>3，交换位置。所以第一趟结束后数组为{2，4，3，5}。第二趟：2<4，不符合条件，位置不变。4>3，交换位置。所以第二趟结束后数组为{2，3，4，5}。第三趟，2<3，位置不变

代码：

void bubble_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[] = { 9,8,7,6,5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
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

结果为：

---

三. 4个参数

3.1 第一个参数void* base

回顾上面的bubble_sort函数，它的第一个参数是int arr[ ],也可以写成int* arr,意思是接受一个整形数组的首元素地址。可是我们想要的是能接受任意类型的指针，所以用int* 就不合适，采用void* (void* 能接受任意类型的指针) ，所以第一个参数写为void* base

3.2 第二个参数szie_t num

上面的bubble_sort函数的第二个参数是int sz，代表数组有多少个元素，其实用int sz也可以，只是如果我们想更贴近qsort函数的话，将int改成size_t(无符号整型)也没有问题，写成szie_t num

3.3 第三个参数szie_t size

上面的bubble_sort函数并没有第三个参数，但是qsort函数有，意思是数组中的一个元素占多少个字节。因为我们不知道要排序的数组是什么类型的，所以如果没有第三个参数，我们无法表示出除首元素以外的地址，也就无法交换相邻元素

3.4 第四个参数int ( * cmp)(const void* e1,const void* e2)

第四个参数是用来判断相邻元素的关系，不能直接使用>,<,=的原因是如果我们想排序多个字符串，那么我们是不能使用>,<,=的，我们需要使用strcmp函数。不同类型的数组排序的函数可能不一样，像qsort函数一样，程序员又不知道用户想要排序的是什么类型的数组，所以程序员只能用函数指针cmp来接收用户自己写的cmp函数，而用户当然知道自己想要排序的数组的类型，所以用户能写出判断相邻元素的关系的函数

cmp函数的细节：
1.e1和e2是相邻元素的地址，被const修饰，保护e1和e2不能被修改
2.因为不知道排序的数组是什么类型的，所以e1和e2都是void * 类型的
3.如果相邻元素的左边>右边，返回>0的数；左边==右边，返回0；左边<右边，返回<0的数。所以返回值的类型为int

void bubble_sort(void* base, size_t num, size_t size, int (*cmp)(const void* e1,const void* e2))
{}
1
2

---

四. bubble_sort函数

虽然函数的参数变化了很多，但函数原理并没有改变，依旧是比较相邻元素的大小，若符合条件，则两元素位置交换，每一趟可以找出最大值或最小值，并显示在序列的最右边。所以下面的框架不变（只将之前的sz变成了num），变得只是第二个for循环里面的内容，而里面的内容就是判断相邻元素的左边是否大于右边（以想要升序排序为例），如果是则交换位置，否则位置不变

void bubble_sort(void* base, size_t num, size_t size, int (*cmp)(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++)
		{
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

好的，那我们现在就想办法如何填写里面的代码，先是判断相邻元素的大小，用cmp函数，函数的两个参数分别为相邻元素的地址。那它们的地址该如何表示呢？首元素地址就是base，不用多说，那第二个元素呢？base+1？不行，我们不知道base的具体类型，所以base+1不知道会跳过几个字节。
那不妨将base强制类型转化为char* ，这样第二个元素（下标为1）的地址为（char*）base+1* size，第三个元素（下标为2）的地址为（char*）base+2* size，所以下标为j的地址为（char*）base+ j * size，代码为：

if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
{}
1
2

好的，那我们继续完善if语句后面的代码，代码的目的是将两元素交换位置，编写swap函数实现交换功能，swap函数的第一、二个参数自然是相邻元素的地址，即(char*)base + j * size, (char*)base + (j + 1) * size，它们都是char * 类型的，所以用两个char * 类型的指针来接收。
但问题又来了，我们平时实现a与b交换，是通过一个变量c来进行的，如下：

	int a = 10;
	int b = 20;
	int c = a;
	a = b;
	b = c;
1
2
3
4
5

上面能交换的原因是我们知道了a和b的类型都是int，所以再创造一个int类型的变量作它们的中转站，即可实现交换。但我们事先并不知道数组的类型，所以不能创建一个和数组同类型的变量实现交换。那不如将两元素的每一个字节都交换（如下图），刚好它们是用char * 指针buf1、buf2来接收的，buf1++，buf2++即可访问两元素的每一个字节，因此我们也需要数组元素的字节数size作为swap函数的第三个参数

所以if语句后面的代码为：

swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
1

swap函数：

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++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

所以bubble_sort函数的全部代码为：

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

---

五. 排序

对任意类型的数组排序都需要下面的代码，故把这些代码单独放在最前面，其余的main函数和cmp函数都因数组类型的变化而有所改变，所以将main函数和cmp函数单独写出来

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(void* base, size_t num, size_t size, int (*cmp)(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 (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
			{
				swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
			}
		}
	}
}
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

5.1 对整型数组排序（char/short/int/long）

字符在内存中存储的是字符的ASCII码值，ASCII码是整型，所以char的写法同int

void cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;//升序
	//return *(int*)e2 - *(int*)e1;//降序
}

int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//升序
	bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
	//打印数组
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5.2 对浮点型数组排序(float/double)

void cmp_double(const void* e1, const void* e2)
{
	return *(double*)e1 > *(double*)e2 ? 1 : -1;//升序
	//return *(double*)e1 < *(double*)e2 ? 1 : -1;
}

int main()
{
	double arr[] = { 3.2 ,4.5, 2.4, 1.3 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//升序
	bubble_sort(arr, sz, sizeof(arr[0]), cmp_double);
	//打印数组
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%lf ", arr[i]);
	}
	printf("\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5.3 对字符串长度排序

void cmp_string(const void* e1, const void* e2)
{
	return strlen((char*)e1) - strlen((char*)e2);//升序
	//return strlen((char*)e2) - strlen((char*)e1);//降序
}

int main()
{
	char arr[][20] = { "helloworld","yes,sir","dian ge zan ba" };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr[0], sz, sizeof(arr[0]), cmp_string);
	int i = 0;
	for (i = 0; i < sz; i++)
		printf("%s\n", arr[i]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.4 对字符串大小排序

void cmp_string(const void* e1, const void* e2)
{
	return strcmp((char*)e1, (char*)e2);//升序
	//return strcmp((char*)e2， (char*)e1);//降序
}

int main()
{
	char arr[][20] = { "helloworld","yes,sir","dian ge zan ba" };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//升序
	bubble_sort(arr, sz, sizeof(arr[0]), cmp_string);
	//打印数组
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%s\n", arr[i]);
	}
	printf("\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5.5 对结构体排序

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

void cmp_stu_by_age(const void* e1, const void* e2)
{
	return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;//升序
	//return ((struct Stu*)e2)->age - ((struct Stu*)e1)->age;//降序
}

int main()
{
	struct Stu arr[] = { {"zhang",20},{"lisi",10},{"wangwu",30} };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//升序
	bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_by_age);
	//打印
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%s\t", arr[i].name);
		printf("%d\n", arr[i].age);
	}
	printf("\n");
	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

---

好了，那么本篇博客就到此结束了，如果你觉得本篇博客对你有些帮助，可以给个大大的赞👍吗，感谢看到这里，我们下篇博客见❤️