算法基础-4.1-插入排序

对于插入排序：一个基本理论是将一个记录插入到已经排好序的表中 每次从表中选一个记录，记录数逐渐增加。已排好序的表就是待插入记录位置前的部分。与冒泡排序相似，时间复杂度最坏接近
如下图：

插入排序.png

#include<iostream>
#include <vector>

using namespace std;

void insert_sort(vector<int> &vec){

    for(int idx=1; idx<vec.size();idx++){
        int pre_idx = idx-1;
        int key = vec[idx];
        //ascending order
        while(pre_idx>=0 && vec[pre_idx]>key){
            vec[pre_idx+1] = vec[pre_idx];
            pre_idx--;
        }vec[pre_idx+1] = key;
    }
}


int main(int argc, char const *argv[])
{
    std::vector<int> v={5,2,4,6,1,3};
    insert_sort(v);
    for(auto item:v)
        cout<<item<<" ";
    cout<<endl;
    return 0;
}

时间复杂度分析：
当待排序的表内的元素为正序时，需要比较的次数明显为：

当全部元素为逆序时，需要比较的次数为：

此时移动数量为: