【数据结构】排序算法系列——冒泡排序（附源码+图解）

冒泡排序

接下来我们要介绍的是排序算法中极为标志性，并且经常在教材中作为经典案例出现的——冒泡排序。

算法思想

冒泡排序(Bubble sort)的算法思想也是较为容易去理解的，我们参照冒泡这一物理现象，会发现，往往大的气泡都会往上运动，而小的气泡往往都在下方。冒泡排序的名字也就是这么由来的。它的算法步骤大致如下：

1. 从数组的开头开始，将第一个数据与第二个数据进行比较，按照指定的比较思想（大的放前面or小的放前面）完成交换操作
2. 再将此时的第二个数据与第三个数据再次进行步骤1中的操作，以此类推，直到比较完最后两个数据
3. 此时的数组如果不是完全有序，那么从头开始进行步骤1和步骤2的操作，直到完全有序。

图解

C语言代码分析

void BubbleSort(int* a, int n)
{
	bool exchange = false;//标记是否发生交换
	for(int j=0;j<n;j++)
	{
		for (int i = 1; i < n-j; i++)
		{
			//如果前一个元素大于后一个元素，交换
			if (a[i - 1] > a[i])
			{
				int temp = a[i - 1];
				a[i - 1] = a[i];
				a[i] = temp;
			}
			if(exchange == false)//如果没有发生交换，说明此时已经有序，那么就直接跳出
			{
				break;
			}
		}
	}

}

时间复杂度

我们可以看出，实际上冒泡排序是华而不实的一种排序算法。它在数据较少或者较为有序的时候，可以有很好的效率，但是一旦数据多起来或者较为无序，那么需要重复的次数就会大幅度增加，从而后期乏力，效率降低。

• 在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为O(n)。
• 在最坏情况下，冒泡排序要执行**(n-1)n/2次交换操作，时间复杂度为O(n2)**。
• 冒泡排序的平均时间复杂度为O(n2)。

稳定性

鉴于冒泡排序不会改变前后元素的相对位置，所以：稳定