目录

1.冒泡排序的定义

2.冒泡排序的原理

3.代码及其解析

4.冒泡排序的改进

5.实现冒泡排序函数

---

生命中永远会有令人懊恼的事，但我知道，我们是为了不留遗憾活着的，对吗？

1.冒泡排序的定义

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端，但是在广泛适用后，冒泡排序可以用来排任意顺序。

2.冒泡排序的原理

假设要将已知无需数列按从小到大排列，将第一个元素与后面的元素依次比较，如果必后面的元素小，就与后面某个元素交换位置，然后用这个元素再依次往后比较，遇到比这个元素小的就与这个元素交换，直到最后一个元素，就完成了一趟冒泡排序，则最后一个元素一定是这个序列里最大的一个元素；然后开始第二趟冒泡排序，继续从第一个元素开始往后一次比较，遇到较小的就交换位置，直到倒数第二个数，那么最后倒数第二个数就变成了第二大的数.......依次排完序列中所有的数，那么这个数的顺序就会变成从小到大，下面我用图来演示

第一趟冒泡排序，是对序列中所有数进行操作

第 i 趟冒泡排序，是对序列中除最后一个数外（10-i）个数进行操作

3.代码及其解析

#include<stdio.h>
int main()
{
	int arr[10] = { 10,9,8,7,6,11,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数
	int i = 0;
	printf("排序前的数组:");
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	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;
			}
		}
	}
	printf("排序后的数组:");
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

运行结果：

 代码解析：外部循环控制冒泡排序的趟数，for循环从0开始，循环sz-1（数组元素-1）次，内部循环控制每次具体的冒泡排序过程，因为每趟冒泡排序需要进行比较的次数递减，所以在循环的控制条件那再减去i来控制每趟冒泡排序进行的比较次数。在内部循环的循环体内，对这趟冒泡排序需要排序的元素进行遍历，小的元素放前面，大的逐次往后走，没趟冒泡结束后都能确定一个元素的位置。（sz-1）趟冒泡排序结束后，冒泡排序及就结束了。当然，如果想进行从大到小排序，只需要改变冒泡排序的判断部分，将大的元素放前面，小的元素往后走即可，代码如下：

#include<stdio.h>
int main()
{
	int arr[10] = { 10,9,8,7,6,11,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数
	int i = 0;
	printf("排序前的数组:");
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	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;
			}
		}
	}
	printf("排序后的数组:");
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

运行结果：

4.冒泡排序的改进

由于冒泡排序的时间复杂度实在太高，所以冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。 

#include<stdio.h>
int main()
{
	int arr[10] = { 10,9,8,7,6,11,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数
	int i = 0;
	printf("排序前的数组:");
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	int flag = 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;
				flag++;
			}
		}
		if(flag==0)
		break;
	}
	printf("排序后的数组:");
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

方法就是在每次冒泡后，检验一下到底这趟冒泡排序有没有交换顺序，如果没有的话，那么flag的值没有发生变化，就可以直接退出循环，这种方法可以略微提升一下效率。 

5.实现冒泡排序函数

用函数实现冒泡排序，传参方法跟数组传参相同，具体可参考C语言函数详解​​​​​​

里面有具体介绍数组传参的方法，这里就直接上代码

#include<stdio.h>
void Bubble_Sort(int arr[], int sz)
{
	int flag = 0;
	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;
				flag++;
			}
		}
		if (flag == 0)
			break;
	}
 
}
int main()
{
	int arr[10] = { 10,9,8,7,6,11,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);//计算出数组元素个数
	int i = 0;
	printf("排序前的数组:");
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	Bubble_Sort(arr, sz);
	printf("排序后的数组:");
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

本文收录于基础算法 、C语言学习专题 、水火莲花-C疑难专题