【C语言】——指针六：冒泡排序与qsort函数的实现

一、冒泡排序

1.1、冒泡排序的原理

  
  在实践过程中，我们难免会碰到要给一组数据排序的情况。如果我们掌握一些排序的算法，效率就会高很多。排序的方法有方法有很多，如：希尔排序，快速排序，堆排序……，今天，我们讲的排序方法就是——冒泡排序！
  
  冒泡排序的原理是什么呢？
  
  他的核心就是相邻两元素两两比较。
  
这里，我们以大小为 10 的数组从小到大排序为例，详细讲解冒泡排序的原理：

• 首先，我们将首元素与数组第二个元素相比较，若首元素大，则两两换位，否则不进行任何操作。
    
• 接着，我们将第二个元素与第三个元素相比较，若第二个元素比第三个元素大，则两数交换，否则不变。
    
• 接下来，依次往后，第三与第四，第四与第五……不断按顺序进行两两比较，符合条件，则两两换位，直到将位置最后两个元素比较完.
    
• 10 元素的数组要比较 10 - 1= 9 组。若前一个元素大，则交换两数位置，否则无事发生(若是从大到小排序，则反之) 这样，一趟冒泡排序就完成啦。
    
    

  不难发现，一趟冒泡排序后，最大的那个元素排到了最后面，即完成第一个数的排序。
  

  
  接下来则进行第二趟排序，与第一趟基本一样，不同的是，因为最后一个元素已经排好了，因此最后一个元素不用比较，少比较一组。
  
  
  
  可以看到，第二大的数也排好了。
  

  
  以此类推，不断进行下一冒泡排序，每一趟排序都能让未排序的数中，最大的那个数归位，
  
  同时每次冒泡排序较之上一趟少比较一组，直到某一趟排序没有进行任何比较，排序结束。
  
  

  

  冒泡排序的过程就像气泡在水中不断上升的，较大（或较小）的元素不断像气泡一样浮到数组的顶端，因此该排序叫冒泡排序。

  
  

1.2、用代码实现冒泡排序

  
  好啦，现在我们知道了冒泡排序的原理，便可以上手进行代码实践了，试试将一个无序数组从小到大排序吧
  
参考代码：

#include<stdio.h>

int* bubble(int* arr, int sz)
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		for (j = 0; j < sz - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	return arr;
}

int main()
{
	int arr[] = { 6,4,1,2,9,3,7,8,10,5 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble(arr, sz);
	for (int 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
22
23
24
25
26
27
28
29
30
31
32
33

  上面代码基本实现了冒泡排序的功能，但有点缺陷。
  
  大家不妨想一想，如果给的数据较为有序，可能只进行一两趟排序即可完成，可上面的代码一定要进行完整的冒泡排序，是不是太过繁琐？
  
  这时，我们可以在每一次排序后进行判断，如果该次排序完后已经完成目标，则退出排序。
  
  在代码的实现中，我们可以设变量flag，当其为 1 表示排序完成，当一趟排序进行交换元素的操作，则将 $flag$ 置为 0，程序继续运行。若一趟循环结束后，$flag$ 还是 1 ，则表示排序已完成。
  
参考代码：

int* bubble(int* arr, int sz)
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int flag = 1;//假设这一趟已经有序了
		int j = 0;
		for (j = 0; j < sz - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				flag = 0;
			}
		}
		if (1 == flag)
		{
			break;
		}
	}
	return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

  
  

二、qsort函数

2.1、qsort函数的定义

  
  下面，我们学习一个新的函数: $qsort$ 函数¹。
  
  $qsort$ 函数的功能是对 任意类型 的数据进行排序，它是怎么做到的呢？
  
  首先，让我们一起来看看他的定义:

图片来源:cplusplus.com
  
  
参数讲解：
  
（1）$void\ast base$

  
  翻译：指向数组中要排序的第一个对象的指针，转换为 $void$。
  
  第一个参数 $base$ 其实就是传递待排序数组的首元素地址，它的类型是 $void$ * .为什么是 $void$* 呢？因为 $qsort$ 函数要排序的是==任意类型的数据，它事先并不知道你要传递给它的数据类型==，因此这里用 $void$* 指针，以便能接受所有类型的数据。
  

  
（2）$size$_$t$ $num$

  
  翻译：基数指向的数组中元素的个数，$size$_ $t$ 是一个无符号整型。
  
   第二个参数 $num$ 其实就是待排序数组的元素个数，因为元素个数肯定是正数，所以这里用 $size$_$t$ 类型。
  

  

（3）$size$_$t$ $size$

  
  翻译：数组中每个元素的字节大小。$size$_ $t$ 是一个无符号整型。
  
  第三个参数 $size$ 指的是待排序数组中每个元素的大小，单位是字节。
  

  
（4）$int$ ( * $compar$) ($const$ $void$ * , $const$ $void$ )

  介绍之前，我们先来观察第四个元素 $compar$ 的类型：$int$ ( * $compar$) ($const$ $void$ * , $const$ $void$ )。 没错，它是一个函数指针，也就是说我们要给它传递一个函数地址。
  
  这是个怎样的函数呢？有什么要求呢？我们一起来看看。
  

  
  先来看看函数的参数类型： $(const$ $void\ast p1$,  $const$ $void\ast p2)$，它有两个参数，均为 $const$ $void$* 类型，返回类型是 $int$ 。
  
  接着是这个函数的具体功能：它的功能是实现两个元素的比较。

• p1 < p2，返回 < 0 的数，
• 相等，返回 0，
• p1 > p2，返回 > 0 的数。
    

 
  为什么要有这个参数呢，我们这里可以回顾一下上面的冒泡排序：

  
  

 
  在内层循环中，该冒泡排序通过两两数相比较来决定是否换位，以实现最终排序，而arr[j] > arr[j + 1]是整型的比较方式。
  
  但是 $qsort$ 函数需要实现的是任意类型的排序，而每一种类型的比较方式是不同的，一种类型一种写法。
  
  $qsort$ 函数事先并不知道使用者要求用什么类型来排，怎么办呢？
  
  $qsort$ 函数便让函数使用者自己写一个待排序类型的比较函数，然后将该函数地址传给 $qsort$ ，$qsort$ 内部再不断调用该函数进行比较，以达到排序的目的。
 
  同时，该函数仅仅是为了对两个数进行比较，并不会对两个数进行修改，因此前面加上 $const$ 来修饰。
  

2.2、 qosrt函数的使用

  
  了解了 $qsort$ 函数后，让我们一起练习它的使用吧。
  

（1）比较函数的写法

  
  我们已经知道要使用 $qosrt$ 函数，需传递一个比较函数的地址的，那这个比较函数怎么写呢？接下来，让我们试着来写一写这个比较函数吧。

• 它的两个形参均为 $const$ $void$* 类型

• 而返回类型为 $int$ 。
     p1 > p2 返回 > 0 的数。
     p1 = p2 返回 0。
     p1 > p2 返回 < 0 的数。

下面我们来举几个例子吧
  
整型比较：

int cmp_int(const void* p1, const void* p2)
{
	return(*(int*)p1 - *(int*)p2);
}
1
2
3
4

注：运算前，要进行强制类型转换，因为 $void$ * 类型并不能进行解引用和 +- 整数的运算，应强制类型转换成要比较数据的类型，再进行相关运算。
  
结构体数据比较（按字符串比较）：

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

int cmp_stu_name(const void* p1, const void* p2)
{
	return strcmp(((stu*)p1)->name,((stu*)p2)->name);
}
1
2
3
4
5
6
7
8
9
10

注：有关 $typedef$ 关键字的用法详情请看【C语言】——指针四：字符指针与函数指针变量。
注：$strcmp$ 函数是专门用来比较字符串大小的函数，在之后的学习中我们会进一步认识他。
  

（2）使用 $qsort$ 函数

  
下面，一起来尝试使用 $qsort$ 函数来排序吧
  
整型数组排序：

#include<stdio.h>

int cmp_int(const void* p1, const void* p2)
{
	return(*(int*)p1 - *(int*)p2);
}
int main()
{
	int arr[] = { 6,4,1,2,9,3,7,8,10,5 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	
	qsort(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
22

  
运行结果：

  
结构体排序（按字符串）：

#include<stdio.h>

int cmp_stu_name(const void* p1, const void* p2)
{
	return strcmp(((stu*)p1)->name,((stu*)p2)->name);
}


int main()
{
	stu s[] = {{"zhangsan",19},{"lisi",18},{"wangwu",20}};
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(&s, sz, sizeof(s[0]), cmp_stu_name);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%s %d\n", s[i].name, s[i].age);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

  
运行结果：

  

2.3、用冒泡排序模拟实现 $qsort$ 函数

  
  了解了冒泡排序和 $qsort$ 函数，接下来，我们来实现用冒泡排序来模拟实现 $qsort$ 函数。

（1）函数声明

  
  首先，一个函数声明最重要的就是函数名；参数类型；返回类型。既然是模仿，我们就要模仿的像，因此，这部分我们可以直接照着官方的函数声明来。
  

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

  

（2）函数基本骨架

  
  我们是用冒泡排序来实现 $qsort$ 函数，那么我们就可以以上面冒泡排序排整型数组的代码为基础，想想哪些可以保留，那些应该去除。
  

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

  
  既然是用冒泡排序实现 $qsort$ 函数，那么有关冒泡排序核心思想的代码应该保留下来，而具体的实现方法，如：前后量元素比较大小、交换两元素，因为每种类型的具体实现方式不同，应该被替换掉。
  
  这样，我们函数的大体骨干就出来啦：

void my_qsort(void* base, size_t num, size_t size, int(*compar)(const void*, const void*))
{
	int i = 0;
	for (i = 0; i < num - 1; i++)
	{
		int flag = 1;
		int j = 0;
		for (j = 0; j < num - 1 - i; j++)
		{
			if (/*比较两个元素的大小*/)
			{
				//交换两个元素
				//···
				
				flag = 0;
			}
		}
		if (1 == flag)
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

  

（3）比较两个元素的大小

  
  比较两个元素的大小的方法前面已经介绍了，既然每一种类型的比较方式不同，那么 $qsort$ 就让使用者自己写一个比较函数传进来。
  
  这里，我们来讲讲如何在 $qsort$ 函数中使用比较函数

  通过比较函数的声明我们知道，它需要我们传递要比较的两个元素的地址，那这两个元素的地址怎么找呢？
  
  在《【C语言】—— 指针一 ： 初识指针（上）》中，我们了解到，一种类型的变量，不论该类型大小是几个字节，进行取地址操作时，取出的是它所有字节中地址最小的字节的地址，即该元素的地址是其地址最小字节的地址，那么我们只要想办法将数据中各个元素地址最小的字节的地址就好了
  
  开始时，我们传入的 $base$ 的地址是指向首元素的最低字节的地址，为 $void$ * 类型，怎么让他指向第二个元素呢？

• 首先，$void$ * 类型指针不能进行 ± 整数的运算，我们先进行强制类型转换，因为 $char$ * 一次访问权限只有一个字节，所以将其转换成 $char$ * 指针，以方便后面的运算。
• 那么转换成 $char$* 后，又该跳过几个字节呢？别忘了，我们还有一个参数没用到：$size$ 。该元素类型大小为几个字节，我们指针就跳过多少个字节，这样就能指向下一个元素啦，即（$char$*）$base$ + $size$。

  现在找第二个元素没问题了，那么想要找到第 $j$ 个元素怎么办呢？找第 $j$ 个元素，即将指针从起始位置跳过 $j\ast size$ 个字节，即 $((char$ * )$base+j$ * $size)$。

我们以整型数组为例:

  这样，我们就可以将需要比较的元素地址准确传给比较函数啦。
  
这里截取一小段：

for (j = 0; j < num - 1 - i; j++)
	{
		//比较两个元素的大小
		if (compar((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
		{
			//交换两个元素
			//···
				
			flag = 0;
		}
	}
1
2
3
4
5
6
7
8
9
10
11

  

（4）交换两个元素

  
  交换元素部分的代码我们可以直接像交换两个整型数据一样写吗？答案肯定是不可以的，原因还是一样，每一种类型都是不一样的。
  
  那么该怎么交换呢？我们可以 一个字节一个字节地逐一交换。
  

  
  我们可以单独封装一个交换函数。

void swap(char* p1, char* p2, size_t size)
{
	int i = 0;
	for (i = 0; i < size; i++)
	{
		char temp = *(p1 + i);
		*(p1 + i) = *(p2 + i);
		*(p2 + i) = temp;
	}
}
1
2
3
4
5
6
7
8
9
10

• $p1$ 与 $p2$ 为两个要交换元素的地址，$size$ 为需要交换的字节数。
• 在传址时，两元素的传址方法与比较函数的传址方法相同，即$((char$ * )$base+j$ * $size)$。
• 因为在传址时，传的已经是 $char$* 类型的指针了，这里函数形参直接用 $char$ * 就行，不需要$void$ * 再进行强制类型转换
    
    

（5）完整代码

  
  下面是冒泡排序模拟实现 $qsort$ 函数的完整代码（以排序整型数组为例）：

#include<stdio.h>

int cmp_int(const void* p1, const void* p2)
{
	return(*(int*)p1 - *(int*)p2);
}


void swap(char* p1, char* p2, size_t size)
{
	int i = 0;
	for (i = 0; i < size; i++)
	{
		char temp = *(p1 + i);
		*(p1 + i) = *(p2 + i);
		*(p2 + i) = temp;
	}
}


void my_qsort(void* base, size_t num, size_t size, int(*compar)(const void*, const void*))
{
	int i = 0;
	for (i = 0; i < num - 1; i++)
	{
		int flag = 1;
		int j = 0;
		for (j = 0; j < num - 1 - i; j++)
		{
			if (compar(((char*)base + j * size), ((char*)base + (j + 1) * size)) > 0)
			{	
				swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
				flag = 0;
			}
		}
		if (1 == flag)
		{
			break;
		}
	}
}


int main()
{
	int arr[] = { 6,4,1,2,9,3,7,8,10,5 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	my_qsort(arr, sz, sizeof(arr[0]), cmp_int);
	for (int 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
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

  
  
  
  
  好啦，本期关于冒泡排序与 $qsort$函数就介绍到这里啦，希望本期博客能对你有所帮助，同时，如果有错误的地方请多多指正，让我们在C语言的学习路上一起进步！
  
  
  
  

---

1. $qsort$ 函数底层是使用快速排序来实现的，本文将以冒泡排序来模拟实现冒泡函数。 ↩︎