c语言冒泡排序（含循环和递归）_冒泡循环

一 、概念

冒泡排序（Bubble sort）顾名思义就是像气泡上升的过程，是一种计算机科学领域的较简单的排序算法，它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。 走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。（网上的定义）简单点说就是相邻两个数字大小比较，将较大的数放在后边，然后依次如此进行排序，过程比较像气泡上升，也就是小气泡上浮快，较大的气泡相对就下沉了。因此就叫冒泡法。定义比较容易理解。
比如有一组数：44、12、7、45、56、5、1
第一次比较是12和44进行，12是小于44，因此顺序换成12、44，然后是44和7比较，交换，之后都如此做。
第一趟进行后：12、7、44、45、5、1、56
一共比较了6次。
第二趟进行后：7、12、44、5、1、45、56
最后一共执行了6趟（也就是n-1趟，其中n是数字的总数）

二、代码实现

1. 循环

假设输入十个数，比较大小，输出顺序，那么代码如下所示：

#include<stdio.h>
int main()
{
	int i, j , h , temp;//其中i是为了输入输出十个数
	//h为比较的趟数
	//j为每趟比较的次数
	//temp是一个临时变量，用于互换相邻两数的大小
	int a[10];
	//输入十个数
	for (i = 0; i < 10; i++)
	{
		scanf_s("%d", &a[i]);
	}
	for(h = 9;h > 0;h --)
	{
		for (j = 0; j < h; j++)
		{
			if (a[j] > a[j + 1])
			{
				temp = a[j + 1];
				a[j + 1] = a[j];
				a[j] = temp;//互换大小
			}
		}
	}
	
	for (i = 0; i < 10; i++)
	{
		printf("%d", a[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

对于核心代码

for(h = 9;h > 0;h --)
{
	for (j = 0; j < h; j++)
	{
		if (a[j] > a[j + 1])
		{
			temp = a[j + 1];
			a[j + 1] = a[j];
			a[j] = temp;//互换
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13

也可以换成下边的形式，主要是分清循环执行的次数就不会写错。

for (h = 1; h < 10 ; h++)
{
	for (j = 0; j < 10 - h; j++)
	{
		if (a[j] > a[j + 1])
		{
			temp = a[j + 1];
			a[j + 1] = a[j];
			a[j] = temp;//互换
		}
	}
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14

最后是互换的代码：

if (a[j] > a[j + 1])
	{
		temp = a[j + 1];
		a[j + 1] = a[j];
		a[j] = temp;//互换大小
	}
1
2
3
4
5
6

2、递归

递归就是函数调用自身，跟循环类似但是代码会很简洁，但是会浪费空间（最典型的递归就是斐波那契数列），递归是函数的高级操作，一个大佬说过：“如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。”，递归是从一个大的方面回推，会锻炼逻辑思维（就像是大事化小）如果想要完成某件事，那么可以先完成一个子事件，子事件又可以拆分。
书上关于递归的一个理解
上面的图片可以帮助理解递归
对于冒泡排序，也可以递归实现，
例如比较五个数：5，4，3，2，1（排成正序）
第一趟 ：4.，3，2，1，5
第二趟 ：3，2，1，4，5
第三趟 ：2，1，3，4，5
第四趟 ：1，2，3，4，5
此时可以理解为想完成排序，那么得先完成第一趟排序，想完成第一趟就要先完成第二趟，想完成第二趟就要先完成第三趟……以此类推。
那么根据这个理解可以写出代码

#include<stdio.h>
void BubbleSort2(int* arr, int sz)//切记别写错了
{
	if (sz < 2)
		return;//如果小于两个元素不用排
	int  i ;
	for (i = 0; i < sz - 1; i++)
	{
		if (arr[i] > arr[i + 1])
		{
			int temp = arr[i];
			arr[i] = arr[i + 1];
			arr[i + 1] = temp;
		}
	}
	 BubbleSort2(arr, --sz);//先--
}

int main()
{
	int i = 0;
	int arr[] = { 5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	BubbleSort2(arr, sz);
	for (i = 0; i < sz; i++)
		{
			printf("%d", arr[i]);//输出
		}
	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

使用递归可以简化代码，但是过程不容易想到

3、对指针的使用

如果你学习了指针相关的知识，那么就可以把代码的核心部分转化为一个函数BubbleSort从而使代码更具有条理性。通过指针进行传址，函数的核心跟上文写的代码类似，就不过多解释了，直接上代码。

#include<stdio.h>
void BubbleSort(int arr[],int sz )
{
	int i = 0 ;
	for(i = 0 ;i <=sz ;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;
				}
			}
	}
}
	int main()
	{
	int i = 0;
	int arr[] = {9,8,7,6,5,4,3,1,2};
	int sz = sizeof(arr) / sizeof(arr[0]);
	BubbleSort( arr,sz);
	for(i = 0 ;i <sz ;i++)
		{
			printf("%d",arr[i]);
	
		}
	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

以上就是转换成函数的形式的冒泡排序，输出排序后的数组也可以转化为函数，这里就不多赘述了

三、优化

如果所给数据是完全逆序的（要求排成正序）那么上边的冒泡很合适，但是如果所给数据部分有序，假设极端一些（1，2，3，4，5，6，7，9，8）大部分都是有序的，但是上边的程序却依旧会执行最繁琐情况的次数，所以很低效，因此可以引入一个flag，先把flag赋值为1，只要执行一次交换位置，那么flag就赋值为0，如果未交换位置，那么flag仍为1，此时跳出循环，就节省了循环执行的次数
代码如下(其实是上边的代码加上几个语句）

#include<stdio.h>
void BubbleSort(int arr[],int sz )
{
	int i = 0 ;
	for(i = 0 ;i <=sz ;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(flag ==1)//增加部分
		{
		break;
		}	
	}
}
int main()
{
int i = 0;
int arr[] = {9,8,7,6,5,4,3,1,2};
int sz = sizeof(arr) / sizeof(arr[0]);
BubbleSort( arr,sz);
for(i = 0 ;i <sz ;i++)
	{
		printf("%d",arr[i]);
	}
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

如果是这样执行会大大提高冒泡的效率（虽然也不高）
最后冒泡排序可以很好的加强我们对数组，函数，递归，指针等知识的深入理解，独立的写出来可以提升自己的代码能力。
最后的最后代码都执行过，按理说不会报错（vs2022版），但是如果某些地方不太严谨，请大佬指正，会及时修改。