简单易懂排序算法(一)【冒泡排序】

Source
版权声明:本文为博主原创文章,转载请注明出处-- https://blog.csdn.net/qq_38790716/article/details/85929469

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

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 的值,后续也是如此应用

上述代码理解起来还是比较简单的,但效率非常低,可以以一个简单的例子来测试一下:
初始序列: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 f a l s e false 直接跳出循环.

冒泡排序时间复杂度分析

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

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

i = 1 n ( i 1 ) \sum\limits_{i=1}^n (i-1) = 1 + 2 + 3 + … + (n - 1) = n ( n 1 ) 2 \frac{n(n-1)}{2}

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

  • 因此,总的时间复杂度为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;
}