插入排序最近在复习算法导论，总结一下经验蛤插入排序的模式就像是排序一手扑克牌 , 设总共牌库数量为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的一刻，认定排序了整个手中牌数组