简介
排序算法的目的是将一组无序的元素，按照有序方式排列
输入：n个数<a1,a2,a3,...,an>
输出：输入序列的一个排序<a1',a2',a3',...,an'>使得 a1'<=a2'<=a3'<=...<=an'.
插入排序如同摸扑克牌，开始时左手是空的，一次一次从桌上模起一张牌并插入到合适的位置。为了找这个牌的合适位置，需要从左向右依次比较。
如图所示：
插入排序过程
下图表示数组A=<5,4,2,6,1,3>上的工作过程。
首先，在第一轮迭代开始之前，子数组只包含一次元素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)
