简单易懂排序算法（一）【冒泡排序】- 校招VIP

转载声明：文章来源https://blog.csdn.net/qq_38790716/article/details/85929469

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

1.容易理解的代码：

void BubbleSort(vector& 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 vectorvector的值，后续也是如此应用）
上述代码理解起来还是比较简单的，但效率非常低，可以以一个简单的例子来测试一下：
初始序列：9，1，5，8，3，7，6，2

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

2.标准的冒泡排序

void BubbleSort(vector& vec)
{
	int n = vec.size();
	for (int i = 0; i < n; ++i)
	{
		for (int j = n - 2; 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& vec)
{
	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;  //有交换则置为1
			}
		}
	}
}

结果如下：

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

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

冒泡排序时间复杂度分析

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

并作等数量级的记录移动。
因此，总的时间复杂度为O(n^2)
一种稳定的排序算法

测试代码：

#include 
#include 
using namespace std;

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

void BubbleSort(vector& 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 vec, int n, int i)
{
	cout << "第" << i + 1 << "次排序结果： ";
	for (int j = 0; j < n; ++j)
		cout << vec[j] << ' ';
	cout << endl;
}

void PrintResult(vector 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 vec(a, a+9);
	BubbleSort(vec);
	return 0;
}