简介

插入排序是一种用于排序的算法，该算法适合数据较少的应用场景（在后面介绍其他算法的时候会进行对比）。

算法原理简述

插入排序就像是你拿了一手的扑克牌，你要把他排好顺序，你需要拿起一张牌，然后把它和左边的牌做比较，直到找到合适的位置后插入，对这些牌从左到右重复上面的过程，就可以得到正确的排序。

C++ 代码演示

如不习惯使用 C++ 可以移步下面的算法分析查看伪码改写成习惯的语言

/*************************************************************************
    > File Name: Insertion_sort.cpp
    > Author: 
    > Mail: 
    > Created Time: 2018年06月04日 星期一 22时13分36秒
 ************************************************************************/

#include<iostream>
using namespace std;
int main(){
    // 测试数据
    int A[5] = {5,4,0,1,3};

    // 打印测试数据        
    cout << "测试数据: ";
    for(int i=0; i<5; i++){
        cout << A[i] << " ";
    }
    cout << endl;

    int key, j;
    
    // 循环遍历数组 A[1] -> A[数组长度]
    for(int i=1; i<sizeof(A)/sizeof(A[0]); i++){
        // (标记1)--当前要插入的元素的前一个元素
        j = i - 1;
        
        // 将当前要插入的元素保存到变量 key 中
        key = A[i];
        
        // 为当前需要排序的元素找到合适的位置
        while(j>=0 && key<A[j]){

            // 如果 A[i] < A[j] 并且 (标记1) >= 0 则将 A[j 向后推移一位]
            A[j+1] = A[j];

            // 将 (标记1) 再向前推移一位
            j--;
        }

        // 将 A[i] 插入到合适的位置
        A[j+1] = key;
    }

    // 打印运行结果
    cout << "运行结果: ";
    for(int i=0; i<5; i++){
        cout << A[i] << " ";
    }
    cout << endl;
}

###### 运行结果 ######

测试数据: 5 4 0 1 3 
运行结果: 0 1 3 4 5 

算法分析

这里为了更清晰方便使用伪代码分析算法的时间复杂性

伪码

这里分析时间复杂性时为了方便将所有语句的运行时间定为常量 C_i , N = 数组长度, 数组下标从 1 开始，并且只关注最坏的情况，也就是数组中的所有元素为倒序，由于简书不支持显示求和符号我就用截图代替了

image.png

将上面代码的语句全部加起来就是插入算法的时间复杂度了

image.png

因为：

image.png image.png

所以：

image.png

化简：

image.png

假设：

image.png

得到：

image.png

使用 O 符号得到该算法的时间复杂度为：

image.png

以上为本人阅读算法导论的笔记

本人能力有限,如果那里写的不对欢迎在评论区或者加群一起讨论

算法讨论组群二维码.png