​

目录

冒泡排序算法分析

冒泡算法的改进

改进版冒泡排序代码实现

冒泡排序时间复杂度分析

冒泡排序算法分析

冒泡排序：Bubble sort，也叫做起泡排序，是一种交换性质的排序，基本思想是相邻两条记录进行比较，不符合规则就交换，符合规则不交换。冒泡排序的具体步骤描述如下

第一趟排序：

第1个元素与第2个元素比较，如果第1个元素大于第2个元素则交换，否则不进行任何操作；第2个元素与第3个元素比较，如果第2个元素大于第3个元素，则交换两个元素，否则不进行任何操作；重复上面操作，两两比较直到第n-1个元素和第n个元素比较完毕，第一趟冒泡结束。

​

编辑

经过第一趟排序后，整个数列中最大的数，通过冒泡冒到了数列的最后一个位置。

第二趟排序：

对前n-1个元素进行冒泡排序，即第1个位置与第2个位置比较，大于则交换，否则无操作；一直到第n-2个位置和第n-1个位置比较，大于则交换，否则无操作。通过第二趟冒泡排序，前n-1个元素中最大的数冒泡到n-1位置，也就是原始数组的倒数第二个位置（原始数组第二大的数）。

​

编辑

 第n-1趟排序：

 通过这种两两比较，经过n-1趟冒泡就可以将整个数组变为有序数组。并且从示意图中可以看出，红色的22本来就在黑色的22的前面，排序后红色22依然在黑色22前面，这说明冒泡排序不会改变相同数据原来的顺序，这说明，冒泡排序算法是稳定的。

冒泡算法的改进

有时候会有这样的情况，一组数据只有少数数据的顺序不对，而其他数据的顺序都是符合我们需要的顺序的（比如从小到大），比如下图中的情况

​

编辑

 这组数据只有前两个位置不符合从小到大的顺序，而后面三个数据都已经符合从小到大的顺序了。此时，只需要一趟排序就可以完成整个数组的排序

​

编辑

 但是，如果按照冒泡排序算法的全部流程，需要走完n-1趟排序才能完成，而第一趟冒泡排序之后的剩余流程其实是没有必要的。

这时，可以在冒泡排序中增加一个标志Flag，如果某一趟冒泡排序过程中，没有发生任何数据交换，则认为整个数组已经有序了，不需要在进行下一趟的冒泡排序，算法结束。比如上图中，在第一趟排序后整个数组已经从小到大排序完毕了，第二趟冒泡排序时，没有发生任何数据交换，则不再进行后续的冒泡，算法结束。这样就节省了很多不必要的时间，只需两趟冒泡就可以结束排序，而正常冒泡排序需要四趟冒泡。

改进版冒泡排序代码实现

//交换 i j 位置的元素
void swap(int array[], int i, int j)
{
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

//冒泡排序
void bubble_sort(int array[], int num) //数组做函数参数会退化为指针，所以要传入数组元素个数
{
	int i = 0, j = 0, ChangeFlag = 1;
	for (i = 0; (i < num - 1) && (ChangeFlag == 1); i++) //总共多少趟排序 num - 1
	{
		ChangeFlag = 0; //默认假设无数据交换
		for (j = num - 1; j > i; j--)
		{
			if (array[j] < array[j - 1])
			{
				swap(array, j, j - 1);
				ChangeFlag = 1;
			}
		}
	}
}

冒泡排序的时候，从后往前冒或者从前往后冒都是可以的，也就是代码中的j从num-1开始或者从1开始都可以。

冒泡排序时间复杂度分析

时间复杂度是衡量一个排序算法好坏的重要标志，特别是在大量数据排序的时候。对于冒泡排序算法，最好的情况下，经过一趟排序就可以完成排序，总共需要n-1次两两比较的操作，此时复杂度为O(n)；最坏的情况下，需要n-1趟排序才能完成整个数组的排序，此时需要的操作次数为，第一趟冒泡n-1次交换，第二趟冒泡n-2次交换，直到第n-1趟排序1次交换结束，共需要

​编辑

 次两两比较的操作，时间复杂度为O(n*n)。所以，冒泡排序的时间复杂度为​编辑。

总结：冒泡排序是一种，稳定的，时间复杂度为​编辑的，简单的内排序。

​