冒泡排序简介：
- 冒泡排序是一种比较简单的排序算法，根据一个序列，比较两个元素，如果顺序不对就交换。
- 然后依次遍历n个点，一次找出一个最大（最小）值，进行n次，完成排序。
代码实现
基础冒泡排序
#include<iostream>
using namespace std;
int main()
{
int a[9] = {1,9,2,5,8,3,7,4,6};
int i,j;
for(i=0;i<9;i++)
{
for(j=8;j>i;j--)
{
if(a[j-1] < a[j])
{
int temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
for(int i=0;i<9;i++)
cout << a[i] << " ";
return 0;
}
这种冒泡排序无论如何都要执行两层循环，因此无论最优最差时间复杂度均为O(n^2)。
改良版冒泡排序
- 设置flag，如果上一次有交换，那么设为true，如果没有交换，说明排序已完成，设为false，此时最优时间复杂度为O(n)（即排序一次就知道不用排了）
//只完成一轮循环的冒泡排序
#include<iostream>
using namespace std;
int main()
{
int a[9] = {9,8,7,6,5,4,3,1,2};
int i,j;
for(i=0;i<9;i++)
{
bool flag = false;
for(j=8;j>i;j--)
{
if(a[j-1] < a[j])
{
int temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
flag = true;
}
}
if(flag == false)
break;
}
for(int i=0;i<9;i++)
cout << a[i] << " ";
return 0;
}
