浅析冒泡排序-c++

  • 时间:
  • 浏览:
  • 来源:互联网

基本思想

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

冒泡排序算法

#include <iostream>
using namespace std;

int main()
{
	int a[8]{ 11,2,5,23,6,8,33,12 };
	for (int i = 0; i < 8; i++)
	{
		for (int j = 7; j > i; j--)
		{
			if (a[j] > a[j - 1])
			{
				int tmp = a[j - 1];
				a[j - 1] = a[j];
				a[j] = tmp;
			}
		}
	}

	for (int i = 0; i < 8; i++)
		cout << a[i] << " ";

	system("pause");
    return 0;
}

这种情况冒泡排序的时间复杂度最优和最差都是O(n^2)

冒泡排序优化

#include <iostream>
using namespace std;

int main()
{
	int a[8]{ 11,2,5,23,6,8,33,12 };
	for (int i = 0; i < 8; i++)
	{
		bool bFlag = false;
		for (int j = 7; j > i; j--)
		{
			if (a[j] > a[j - 1])
			{
				int tmp = a[j - 1];
				a[j - 1] = a[j];
				a[j] = tmp;
				bFlag = true;
			}
		}

		if (!bFlag)  
		{
			break;  //无需重新排序
		}
	}

	for (int i = 0; i < 8; i++)
		cout << a[i] << " ";

	system("pause");
    return 0;
}

这种情况冒泡排序的时间复杂度最差是O(n^2),最优情况则是无需重新排序,直接返回

 

本文链接http://element-ui.cn/article/show-297241.aspx