排序算法 | 交换排序 一：冒泡算法的图解、实现、复杂度和稳定性分析与优化

---

交换排序 一：冒泡排序

交换排序的定义: 交换交换，换的是两个元素的位置，根据序列中，两个元素关键字的比较结果，对两个元素在序列中的位置进行交换。
交换排序，最常见的就是冒泡排序和快速排序

1、冒泡排序定义

冒泡排序的基本思想就是：序列从前到后（一般都是从前到后）或者从后到前去两两比较相邻元素的值，
如果逆序，就交换一下，一直这样走下去，直到序列比较完，这就是第一趟冒泡。
下一趟冒泡的时候，前一趟已经确定了的最小的（或是最大的）元素就不用参加比较了。
如此重复，最多需要 N - 1 次就可以把所有的元素排序好

2、名字由来以及注意点

冒泡名字的由来：是大的元素，会在排序过程中通过交换“浮现”到序列顶端，过程就像水中水泡冒泡一样，因此得名。

但是不能有误区;
那就是序列升序的时候，用冒泡来比喻最形象
降序的时候，用沉底比喻更不错
这个也不必纠结，结合代码马上就能够理解了。

3、算法示例

定义数组如下：

	int arr[] = {3,44,38,15,47,43};

① 排序之前：

② 排序过程：

第一趟，从头开始，依次比较两个元素的大小，前面的元素 > 后面的，则交换两个元素；

• 下一趟继续上述的步骤，只是刚刚已经确认过的最后元素已经是最大了，就不用继续参与比较了
• 后续趟数的比较同理，直到序列是有序的

③ 排序结果：

（最多）重复 N - 1次之后，就排序完成了

④代码每一趟执行的过程

4、常见代码实现，以及代码的优化

①常见的代码实现：

void Bubble_Sort(int *arr, int length)
{
	if (arr == NULL || length <= 0)
	{
		return;
	}

	bool IsSwap = false;

	for (int i = 0; i < length; i++)
	{
		for (int j = 0; j < length - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])  // 两两比较
			{
				int temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
			}
		}
		printf("第%d步排序结果：", i + 1);   // 输出每步排序结果
		for (int k = 0; k < length; k++)
		{
			printf("%5d", arr[k]);
		}
		printf("\n");
	}
}

②代码的优化：

但是我们可以发现后续的步骤是已经就排好了的；

如果使用上述的普通方法，后续的步骤依旧是会有比较的

但是从结果的角度看，完全没有必要呀~，虽然计算机很快，但是这依然是一种没必要的浪费

思路：因此就可以从此处优化：增加flag标志位，根据有无数据交换，去决定是继续冒泡还是结束冒泡

void Bubble_Sort(int *arr, int length)
{
	if (arr == NULL || length <= 0)
	{
		return;
	}

	bool IsSwap = false;

	for (int i = 0; i < length; i++)
	{
		IsSwap = false; //增加flag标志位，根据有无数据交换，去决定是继续冒泡还是结束冒泡
		for (int j = 0; j < length - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])  // 两两比较
			{
				int temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
				IsSwap = true;
			}
		}
		
		if (IsSwap == false)
		{
		break;
		}

		printf("第%d步排序结果：", i + 1);   // 输出每步排序结果
		for (int k = 0; k < length; k++)
		{
			printf("%5d", arr[k]);
		}
		printf("\n");
	}
}

随后，我们来看优化的结果：

到了第三步的时候，由于没有发生数据的交换，所以就结束冒泡，直接返回排序的结果了，并没有继续走剩下的四步

5、算法分析

①空间复杂度：

O(1)；因为辅助空间是常数级别的

②时间复杂度：

最好的情况：初始的时候，序列就是正序的，所以时间复杂度是 O(n)
最坏的情况：初始的时候，序列是完全逆序的，所以时间复杂度是O(n^2)
平均时间复杂度：综上，平均时间复杂度是O(n^2)

③算法稳定性：

对于算法的稳定性而言，我们先假设，在此时序列中有两个相邻的值为 13 的元素（其它重复元素同理，不是相邻的话在冒泡的过程中也会有相邻的状态），根据判断条件 i > j , 且 A[i] == A[j] ，在做冒泡排序的时候，13 和 另外一个13之间不会发生位置的交换；
所以，冒泡排序是一种稳定的排序算法。

---

文中代码在Github可下载： https://github.com/FYY-YOUNG