【排序算法】⑤冒泡排序

前言

冒泡排序属于交换排序的一种。交换排序基本思想：所谓交换，就是按序列中两个数据码值的比较结果来决定是否对换这两个数据在序列中的位置。

交换排序的特点是：将码值大的向尾部移动，码值小的往前移动

冒泡排序实现简单，主要是为后续同属于交换排序的快排做铺垫，故本文篇幅较短。

一、冒泡排序是什么？

冒泡排序的基本思想

1. 比较相邻的元素：首元素设从i=0开始，依次比较相邻的两个元素（j=i+1）。如果第一个比第二个大（升序排序），就交换它们。 2. 然后i不变，j++，循环直到 j 到达数组末尾，此时最后一个数据一定是该数据集最大的。 3. i++，重复上述步骤，直到遍历完整个数组。

核心思想：重复遍历数组，比较相邻元素，如果顺序错误就交换它们

排序过程：每轮遍历会将当前最大的元素"冒泡"到正确位置，类似水中的气泡上浮，因此得名。

二、冒泡排序图解

设数组为int a[ ]={5，3，8，4，2}，两层循环，外层循环控制 i=0，内存控制 j=i+1，各自的循环结束时++，结束条件为到达数组末尾<n;

三、实现代码

以升序为例，降序同理。

//冒泡排序
void BubbleSort(int* a, int n)
{
	if (!a)return;
	for (int i = 0; i < n; ++i)
	{
		int Change = 1;
		for (int j = i + 1; j < n; ++j)
		{
			if (a[i] > a[j])
			{
				swap(&a[i], &a[j]);
				Change = 0;
			}
		}
		//如果Change的值未变,则说明数组后续数据都有序
		if (Change)break;
	}
}


void swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

break优化解释：

如果在i=某值的一轮比较中，Change的值都未发生改变（即内循环没有发生交换），说明后续数据都大于或等于a[i]且呈现递增趋势为有序状态，故此时可以跳出循环，提前结束排序。

四、分析冒泡排序

冒泡排序的特性总结： 1. 冒泡排序是一种较容易理解的排序； 2. 时间复杂度：O(N^2)，（若加上break优化，则较不优化平均快上3倍）； 3. 空间复杂度：O(1) 4. 稳定性：稳定

总结

本文是【排序算法】系类第五篇，主要介绍什么是冒泡排序，以及如何实现冒泡排序，最后分析冒泡排序特性。

冒泡排序较为简单，但它是为同为交换排序的“快速排序”做铺垫，快速排序是当今实际代码中最常使用的排序，也是本系列的重点所在。