冒泡排序（C++实现）

冒泡排序简介：

• 冒泡排序是一种比较简单的排序算法，根据一个序列，比较两个元素，如果顺序不对就交换。
• 然后依次遍历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;
}