2.冒泡排序

2.冒泡排序

2.1冒泡排序的思想和复杂度

冒泡思想

冒泡排序，顾名思义就是像气泡一样，大小不一的气泡会依次逐个交换位置，然后形成从小到大的顺序。冒泡排序可以从左向右冒泡，也可以从右向左冒泡，但正宗的冒泡是从右向左的。意思就是说如果要排成从小到大的顺序，就要从最右端向最左端扫描并交换。

时间和空间复杂度

时间复杂度如表所示

算法	平均情况	最好情况	最差情况
冒泡	O(N^2)	O(N)	O(N^2)

空间复杂度：O(1)

2.2冒泡排序的操作

假设有这样一个数组vec：

下标	0	1	2	3	4	5	6	7	8	9
数组	4	3	5	2	1	9	8	6	0	7

对这个数组进行冒泡排序，我们首先设定一个外层循环 i (0<i<N-1)，循环次数为N=vec.size()。然后在每个外层循环的内层循环 j (i+1<j<N-1)中进行扫描。内层循环的目的是为了从右向左扫描，通过依次相邻比较的方式找到最小的数，放到数组vec的最左边i的位置上，下一次内循环之前i++，就不再扫描这个最小的数字了。外层循环的目的是为了保证排序完成后的每一个数字都是经过冒泡放在了正确的位置上，而不遗漏对每个数字的冒泡。

内层循环(i<j<number-1, j--)

可以通过下表理解内层循环中一次扫描中的交换：

指针	i									j
原始数组	4	3	5	2	1	9	8	6	0	7
指针	i								j-1	j
更新数组	4	3	5	2	1	9	8	6	0	7
指针	i							j-1	j
更新数组	4	3	5	2	1	9	8	0	6	7
指针	i						j-1	j
更新数组	4	3	5	2	1	9	0	8	6	7
指针	i					j-1	j
更新数组	4	3	5	2	1	0	9	8	6	7
指针	i				j-1	j
更新数组	4	3	5	2	0	1	9	8	6	7
指针	i			j-1	j
更新数组	4	3	5	0	2	1	9	8	6	7
指针	i		j-1	j
更新数组	4	3	0	5	2	1	9	8	6	7
指针	i	j-1	j
更新数组	4	0	3	5	2	1	9	8	6	7
指针	i&j-1	j
更新数组	0	4	3	5	2	1	9	8	6	7

外层循环(0<=i<vec.size(), i++)

可以通过下表理解外层循环的交换：

指针	i
原始数组	4	3	5	2	1	9	8	6	0	7
指针		i
更新数组	0	4	3	5	2	1	9	8	6	7
指针			i
更新数组	0	1	4	3	5	2	6	9	8	7
指针				i
更新数组	0	1	2	4	3	5	6	7	9	8
指针					i
更新数组	0	1	2	3	4	5	6	7	8	9
指针						i
更新数组	0	1	2	3	4	5	6	7	8	9
...

到这里实际上已经排序完成了。

优化

为了提高冒泡排序的效率，我们在代码里加一个flag，用这个flag来检查是不是已经排序完成了。冒泡排序完成以后是不会再有数字交换的情况了，所以我们用flag来记录是否进行了交换，如果没有交换，那么我们就认为排序完成，不再进行外层循环。
OK, 可以上代码了。

2.3 C++代码###

#include <iostream>
#include <vector>
using namespace std;

class Sort
{
public:
    void bubble(vector<int> &vec)
    {
        int number=vec.size();
        vector<int> nullvec;
        if(number==0)return;
        bool flag=true;
        for(int i=0;i<number && flag;i++)
        {
            flag=false;
            for(int j=number-1;j>i;j--)
            {
                if(vec[j-1]>vec[j])
                {
                    exch(vec,j-1,j);
                    flag=true;
                }
            }
            show(vec);
        }
    }
    void show(vector<int> &vec)
    {
        for(int i=0;i<vec.size();i++)
        {
            cout << vec[i] << " ";
        }
        cout << endl;
    }
    vector<int> init()
    {
        vector<int> vec;
        int arr[10]={4,3,5,2,1,9,8,6,0,7};
//        int arr[10]={9,8,7,6,5,4,3,2,1,0};
        vec.insert(vec.begin(),arr,arr+10);
        cout <<"ori:"<<endl;
        show(vec);
        cout <<"-------------------"<<endl;
        return vec;
    }
    bool checkorder(vector<int> &vec)
    {
        for(int i=0;i<vec.size()-1;i++)
        {
            if(vec[i]>vec[i+1])return false;
        }
        return true;
    }
private:
    void exch(vector<int> &vec,int a,int b)
    {
        int tmp;
        tmp=vec[a];
        vec[a]=vec[b];
        vec[b]=tmp;
    }
};

int main()
{
    Sort sortob;
    vector<int> mvec=sortob.init();
    sortob.bubble(mvec);
    cout <<"------result-------"<<endl;
    if(sortob.checkorder(mvec))
        sortob.show(mvec);
    else
    {   cout << sortob.checkorder(mvec);
    }
    return 0;
}

输出结果：

image.png