插入排序

最近在复习算法导论，总结一下经验蛤

插入排序的模式就像是排序一手扑克牌 , 设总共牌库数量为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的一刻，认定排序了整个手中牌数组