4.插入排序

4.插入排序

4.1插入排序的思想和复杂度

插入排序思想

插入排序每次扫描的元素个数递增一个，且将最小的插入到最前面，然后将其余数字向后移动。直到逐个扫描到最后一个元素。

时间和空间复杂度

时间复杂度如表所示

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

空间复杂度：O(1)

4.2插入排序操作

假设有这样一个数组vec：

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

插入排序同样以外层循环和内层循环的逻辑来分析，内层循环的目的是找到当前轮次中最小的值，然后将其插入到最前面，其余数字原模原样地向后移动。内层循环遍历的顺序是从右到左。
外层循环的目的是依次递增扫描的窗长，每次都增加扫描一个数。

内层循环(0<j<=i, j--)

i=3的内层循环：

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

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

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

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

OK, 可以上代码了。

4.3 C++代码

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

class Sort
{
public:
    void insert(vector<int> &vec)
    {
        int number=vec.size();
        vector<int> nullvec;
        if(number==0)return;
        for(int i=1;i<number;i++)
        {
            for(int j=i;j>0;j--)
            {
                if(vec[j]<vec[j-1])
                {
                    exch(vec,j,j-1);
                }
            }
            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};
        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.insert(mvec);
    cout <<"------result-------"<<endl;
    if(sortob.checkorder(mvec))
        sortob.show(mvec);
    else
    {   cout << sortob.checkorder(mvec);
    }
    return 0;
}

输出结果：

image.png