算法导论—排序之插入排序

void insertion_sort(vector<int> &num){
    for(int i = 1; i < num.size(); i++){
        int j = i-1;
        int val = num[i];
        while(j>=0 && num[j] >= val){
            num[j+1] = num[j];
            j--;
        }
        num[j+1] = val;
    }


}

//降序
void insertion_sort(vector<int> &num){
    for(int i = 1; i < num.size(); i++){
        int j = i-1;
        int val = num[i];
        while(j>=0 && num[j] < val){
            num[j+1] = num[j];
            j--;
        }
        num[j+1] = val;
    }


}

效率分析：

最优情况：

原数列已排好序，即不进行while循环，效率为 n

最差情况：

原数列为逆序，则每次迭代要进行i-1次循环，则效率为  n方

算法导论—排序之插入排序,布布扣,bubuko.com

算法导论—排序之插入排序

原文：http://blog.csdn.net/mowayao/article/details/25650561