「冒泡排序算法」简单易懂排序算法（一）【冒泡排序】

冒泡排序算法

冒泡排序：一种交换排序，基本思想是两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止

1.容易理解的代码：

void BubbleSort(vector<int>& vec)
{
	int n = vec.size();
	for (int i = 0; i < n - 1; ++i)
	{
		for (int j = i + 1; j < n; ++j)
		{
			if (vec[i] > vec[j]) 
				swap(vec[i], vec[j]);
		}
	}
}

在这里我们传入向量的引用，可以直接改变 $v e c t o r vector$ vector的值，后续也是如此应用

上述代码理解起来还是比较简单的，但效率非常低，可以以一个简单的例子来测试一下：

初始序列：9，1，5，8，3，7，6，2

在这里插入图片描述

可以看到在第二次排序之后3被换到了最后面，即在排好了1和2的位置后，对于其他关键字的排序并没有什么帮助，由此可以看出这个算法的效率非常低。

2.标准的冒泡排序

void BubbleSort(vector<int>& vec)
{
	int n = vec.size();
	for (int i = 0; i < n; ++i)
	{
		for (int j = n - 1; j >= i; --j) //注意j说从后往前循环
		{
			if (vec[j] > vec[j + 1]) 
				swap(vec[j], vec[j + 1]);
		}
	}
}

还是以上述例子来进行测试：

初始序列：9，1，5，8，3，7，4，6，2

在这里插入图片描述

可以看到每一次排序过后最小的值都到了指定的位置，同时我们与上一个算法比较一下，即在第二次排序之后，上一个算法中3到了最后面，而在这个算法中3、4都较之前的序列往前进了，这种差异在小序列可能并不是很明显，但当序列足够大时这种差异就会体现出来。

从结果可以看到，每一个较小的数字像气泡一样慢慢浮到了前面，因此也被称为冒泡排序

3.改进的冒泡排序

在给出的序列已基本有序的情况下，例：2，1，3，4，5，6，7，8，9

简单测试一下：

在这里插入图片描述

可以看到，在序列基本有序的情况下，在第一次排序后就已经完全有序，但此时算法仍在不断的进行循环判断，这种无意义的循环判断明显的降低了效率，因此，为了减少这种无意义的判断，我们可以将算法作如下改进：

void BubbleSort(vector<int>& vec)
{
	int n = vec.size();
	bool flag = 1;
	for (int i = 0; i < n && flag; ++i)
	{
		flag = 0;
		for (int j = n - 1; j >= i; --j)
		{
			if (vec[j] > vec[j + 1]) {
				swap(vec[j], vec[j + 1]);
				flag = 1;  //有交换则置为1
			}
		}
	}
}

结果如下：

在这里插入图片描述

可以看到明显的减少了无意义的循环判断，再来简单分析一下代码的改动：

代码改动的关键在于i变量的for循环中，增加了对flag是否为1的判断，经过这样的判断，就能知道代码是否有序，因为如果有序的话则 $f l a g flag$ flag为 $f a l s e false$ false直接跳出循环.

冒泡排序时间复杂度分析

简单分析一下时间复杂度。

在最好的情况下，也就是要排序的表本身是有序的，根据我们改进的代码，可以得出经过 $n - 1 n-1$ n−1次的比较，没有数据交换，时间复杂度为O(n)
在最坏的情况下，即待排序表是逆序的情况下，此时需要比较

$\sum_{i = 1}^{n} (i - 1) \sum\limits_{i=1}^n (i-1)$ i=1∑n(i−1) = 1 + 2 + 3 + … + (n - 1) = $\frac{n (n - 1)}{2} \frac{n(n-1)}{2}$ 2n(n−1)次

并作等数量级的记录移动。

因此，总的时间复杂度为O(n^2)
一种稳定的排序算法

测试代码：

#include <iostream>
#include <vector>
using namespace std;

void BubbleSort(vector<int>& vec);
void PrintStep(vector<int> vec, int n, int i);
void PrintResult(vector<int> vec, int n);

void BubbleSort(vector<int>& vec)
{
	cout << "--------------冒泡排序--------------" << endl;
	int n = vec.size();
	bool flag = 1;
	for (int i = 0; i < n && flag ; ++i)
	{
		flag = 0;
		for (int j = n - 2; j >= i; --j)
		{
			if (vec[j] > vec[j + 1]) {
				swap(vec[j], vec[j + 1]);
				flag = 1;
			}
		}
		PrintStep(vec, n, i);
	}
	cout << "最终排序结果为：";
	PrintResult(vec, n);
}

void PrintStep(vector<int> vec, int n, int i)
{
	cout << "第" << i + 1 << "次排序结果： ";
	for (int j = 0; j < n; ++j)
		cout << vec[j] << ' ';
	cout << endl;
}

void PrintResult(vector<int> vec, int n)
{
	for (int j = 0; j < n; ++j)
		cout << vec[j] << ' ';
	cout << endl;
}
int main(int argc, char **argv)
{
	int a[] = {2,1,3,4,5,6,7,8,9};
	vector<int > vec(a, a+9);
	BubbleSort(vec);
	return 0;
}

简单易懂排序算法（一）【冒泡排序】