算法：插入排序

插入排序
最近在复习算法导论，总结一下经验蛤
插入排序的模式就像是排序一手扑克牌 , 设总共牌库数量为n 当前抽中的牌下标为 i, 有以下论证

手中的牌是有序的，并且为[0…i], 手中牌数量为(i)
剩余的牌库是无序的，并且为[i+1…n], 剩余牌数量(n – i – 1)

整个过程可以概括为：
从剩余牌库中依次循环抽取牌，循环n-1次, 抽取中的牌依次比较手中牌的大小，循环次数不定（ 因为手中牌是有序的，比较成功就会退出循环 ）,最多为i-1次
使用Java实现算法则为:
public class InsertionSort {
public static int[] sort(int[] p) {
for (int i = 1; i < p.length; i++) {
int currentValue = p[i];

int index = i;

while (index > 0 && currentValue < p[index – 1] ) {
int a = 0;
a = p[index];
p[index] = p[index – 1];
p[index – 1] = a;
index–;
}
}
return p;
}

public static void main(String[] args) {
int[] b = InsertionSort.sort(new int[]{5, 2, 4, 6, 1, 3});
for (int i : b) {
System.out.println(i);
}
}
}
根据循环不变式可以验证以上代码( 使用上面代码的变量 )

初始化 : 在i=1时证明循环不变式成立, 手中牌为5，单个元素，排序自然成立.
保持: 证明每次循环迭代循环不变式成立, 测试几条数据如下成立

手中牌: [5] [2,5]

正在抽中的牌: [2] [4]

牌库中的牌: [4,6,1,3] [6,1,3]
终止: 导致外层循环终止的原因是 i < p.length, i = 1, i ++, 必有i > p.length的一刻，认定排序了整个数组.在内层排序手中牌的循环终止原因是index > 0 && currentValue < p[index – 1] index是当前的手牌下标(下标从1开始), index–;必有index <= 0的一刻，认定排序了整个手中牌数组