简介

排序算法的目的是将一组无序的元素，按照有序方式排列
输入：n个数<a1,a2,a3,...,an>
输出：输入序列的一个排序<a1',a2',a3',...,an'>使得 a1'<=a2'<=a3'<=...<=an'.
插入排序如同摸扑克牌，开始时左手是空的，一次一次从桌上模起一张牌并插入到合适的位置。为了找这个牌的合适位置，需要从左向右依次比较。
如图所示：

image.png

插入排序过程

下图表示数组A=<5,4,2,6,1,3>上的工作过程。

image.png

首先，在第一轮迭代开始之前，子数组只包含一次元素A[1],所以它是有序的。
接下来，比如迭代到 j ,要将A[j-1],A[j-2]等元素向后移动。直到找到合适的位置。这时将A[j]插入。这样A[j]及之前的子串都是有序的。
最后，当 j 迭代到数组最后一个元素时，迭代完成后，此时j = n(数组长度)。A[j]及之前的子串都是有序的，即A[n]之前的数组是有序的，数组中所有的数字就是有序的。

插入排序代码

func InsertSort(data []int) []int {
    N := len(data)
    for i := 1; i < N; i++ {
        v := data[i]
        j := i - 1
        for ; j >= 0 && data[j] > v; j-- {
            data[j+1] = data[j]
        }
        data[j+1] = v
    }

    return data
}

插入排序算法分析

func InsertSort(data []int) []int {
    N := len(data)                                     总次数        单位时间
    for i := 1; i < N; i++ {                            n-1                c1
        v := data[i]                                   n-1                c2
        j := i - 1                                        n-1                c3
        for ; j >= 0 && data[j] > v; j-- {     Σt(i),i=0..n      c4
            data[j+1] = data[j]               Σt(i),i=0..n      c5
        }
        data[j+1] = v                               n-1                 c6
    }

    return data
}

由上所得总消耗为 T(n) = (n-1)c1+(n-1)c2+(n-1)c3+Σt(i)c4+Σt(i)c5+(n-1)c6
设Σt(i) i从1到n t(i)求和
还有两步没算进去 i++和j--,i++执行n-1次 j--执行Σt(i)次
最终 T(n) = (n-1)c1+(n-1)c2+(n-1)c3+Σt(i)c4+Σt(i)c5+(n-1)c6+(n-1)c7+Σt(i)c8
单位时间可以认为是一致的所以 c1=c2=...=c8=t(i)=c 简化后结果为：
T(n) = 5c(n-1)+4Σic
由于 Σi = n(n+1) / 2 即1+2+...+n的求和
可以将T(n)转化为 T(n)=an^2 + bn +c 其中a,b,c为常量

最优情况

最优是Σi i取值为1 所以 T(n) = an+b 的形式

最坏和平均的情况

最坏时 Σi 每次i从1到n 所以 T(n)=an^2 + bn +c
平均时Σi 每次i从1到n/2 迭代最简式仍然为： T(n)=an^2 + bn +c

增长的量级

n的不断增长 T(n)的增长至于 an^2+bn有关。在做进步一抽象 n增长越快。与高阶关联越大，低级影响变小
所以插入排序的最坏情况时间复杂度为O(n^2)