【C语言】深入理解冒泡排序算法（优化+详解）

文章目录

什么叫冒泡排序？

冒泡排序是比较基础的排序算法之一，其思想是相邻的元素两两比较，较大的数下沉，较小的数冒起来，这样一趟比较下来，最大(小)值就会排列在一端。

整个过程如同气泡冒起，因此被称作冒泡排序。

通俗来说，也就是：

从第一个元素开始比较相邻的两个元素，如果第一个比第一个大或小，就互换它们的位置，这样先比较完一次，然后抛弃最大或最小的继续比较，直到排序完成。

冒泡排序的步骤：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
每趟从第一对相邻元素开始，对每一对相邻元素作同样的工作，直到最后一对。
针对所有的元素重复以上的步骤，除了已排序过的元素(每趟排序后的最后一个元素)，直到没有任何一对数字需要比较。

动画演示：

此处引用网上一张比较经典的gif来展示冒泡排序的整个过程：

图解冒泡排序

有8个数组组成一个无序数列：5,8,6,3,9,2,1,7，希望从小到大排序。

按照冒泡排序的思想：把相邻的两个数字两两比较，当一个数字大于右侧相邻的数字时，交换他们的位置，当一个数字和他右侧的数字小于或等于的时候，不交换。

第一轮排序

首先让5和8进行交换，发现5比8小，因此元素位置不变；
接下来让8和6比较，发现8比6大，所以要交换8和6的位置；
继续让8和3比较，发现8比3要大，所以8和3 交换位置；
继续让8和9进行比较，发现8比9小，不用交换；
9和2进行比较，发现9比2大，进行交换；
继续让9和1进行比较，发现9比1大，所以交换9和1的位置；
最后，让9和7交换位置；

这样一来，元素9作为数列的最大元素，就已经排序好了

第二轮排序

首先让5和6比较，发现5比6小，位置不变；
接下来让6和3比较，发现6比3大，交换位置；
接下来让6和8比较，6比8小，位置不变；
8和2比较。8比2大，交换位置；
接下来让8和1比较，8比1大，因此交换位置；
继续让8和7比较，发现8比7大，交换位置；

这样一来，第二轮排序已经好了

第三轮排序

按照以上步骤，可得第三轮排序：

第四轮排序

按照以上步骤，可得第四轮排序：

第五轮排序

按照以上步骤，可得第五轮排序：

第六轮排序

按照以上步骤，可得第六轮排序：

第七轮排序

按照以上步骤，可得第七轮排序，此时已经有序了：

第八轮排序

此时已经排序完成啦！

到此为止，所有的数字都是有序的了，冒泡排序是一种稳定排序，由于该排序算法的每一轮都要遍历所有的数字，一共要遍历n-1，所以时间复杂度为：O(n^2)

那么我们如何区分排序算法是否稳定呢？

如果我们交换的时候，遇到两个相同的数字；

如果两个相同的数字在排序之后相对位置没有交换，那么就是稳定的排序，反之则是不稳定的排序。

代码实现

代码过程如下：

void bubble_sort(int* arr, int sz)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < sz - 1; i++)
	{
		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[10] = { 5, 8, 6, 3, 9, 2, 1, 7 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz);

	int i = 0;
	for (i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
 }

运行结果：

这个代码很简单，使用双循环的方式进行排序。

外部的循环控制所有回合，内部循环代表每一轮的冒泡处理，先进行元素比较，再进行元素交换。

代码优化

从上面的例子不难看出，我们可以对原来的冒泡排序进行优化。

我们仍然用上面呢个数列{ 5, 8, 6, 3, 9, 2, 1, 7 }为例子，从上面的图解可以看出在第六、第七、第八轮排序后，整个数列已经是有序的了，但是排序算法还是执行到了第八轮排序。

优化的思路是：如果能判断出数列已经是有序的了，并且做出标记，那么就不会执行多余的排序。

因此，我们可以进行一个优化，就是设置一个flags;

如果在本轮排序中有元素进行交换，则说明数列无序，如果已经排序了那么设置为0；
如果在本轮排序中，没有元素进行交换，则说明数列有序，那么设置为1。

现在我们来看看优化后的代码：

void bubble_sort(int* arr, int sz)
{
	int i = 0;
	int j = 0;
	int flags = 0;
	for (i = 0; i < sz - 1; i++)
	{
		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;
				flags = 1;//不是有序的，flags设置为1
			}
		}

		if (flags == 0)
			return;
	}
}

int main()
{
	int arr[8] = { 5, 8, 6, 3, 9, 2, 1, 7 };
	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]);
	}

	return 0;
 }