算法导论C++实现

算法基础-4.1-插入排序

2018-12-16  本文已影响0人  zhouycoriginal

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

插入排序.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;
}

时间复杂度分析:
当待排序的表内的元素为正序时,需要比较的次数明显为:
\sum_{i=1}^{n}1=n-1
当全部元素为逆序时,需要比较的次数为:
\sum_{i=1}^{n}i=(n-1)(n-2)
此时移动数量为: \sum_{i=1}^{n}(i+1)=\frac{(n+4)(n-1)}{2}

上一篇 下一篇

猜你喜欢

热点阅读