共计 872 个字符，预计需要花费 3 分钟才能阅读完成。
插入排序
最近在复习算法导论，总结一下经验蛤
插入排序的模式就像是排序一手扑克牌 , 设总共牌库数量为 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 的一刻，认定排序了整个手中牌数组
