插入排序算法 伪代码

a 需要排序的数组for j=1 to a.length    //insert a[j] to  a[0,1...j-1] {循环不变式}    key=a[j]    i =j-1        while i>=0 and a[i]>key            a[i+1]=a[i]            i=i-1      a[i+1]=key    // 其中 a[0,1...j] 表示 a 的子数组    // and or 具有短路功能    // 变量没有特殊声明,都是局部变量    // 数组下标 是从0开始

循环不变式和数学归纳法

**循环不变式,辅助我们理解算法的正确性**循环不变式必须要满足3条性质:1. 初始化：它在循环的第一轮迭代开始之前，应该是正确的。2. 保持：如果在某一次循环迭代开始之前是正确的，那么在下一次迭代开始之前，它也应该保持正确（假设当循环变量等于k时符合，再看执行一遍循环体后是否还符合循环不变式）。3. 结束：当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的针对此题,其数学化表示为:1. 当 j=0时,A[0]已正确排序2-1. 假设 j=k时,A[k]插入A[0,1,2,...k],能使子列正确排序2-2. 当j=k+1时,验证A[k+1]插入A[0,1,2,...,k,k+1]能否使子列正确排序    key=a[k+1]    i =k        while i>=0 and a[i]>key            a[i+1]=a[i]            i=i-1      a[i+1]=key    这轮排序,确实可以使排序成功3. 当循环结束时,确实能使整个数组都正确排序

java 代码

public class Test {    public static void main(String[] args) {        Test t = new Test();        int[] a = new int[] { 1, 3, 5, 6, 7, 43, 2 };        t.sort(a);        t.out(a);    }    public void sort(int[] a) {        if (a.length <= 1) {            return;        }        for (int j = 1; j < a.length; j++) {            int key = a[j];            int i = j - 1;            //反向扫描            while (i >= 0 && a[i] < key) {                a[i + 1] = a[i];                i--;            }            a[i + 1] = key;        }    }    public void out(int[] a) {        for (int i : a) {            System.out.print(i + " ");        }        System.out.println();    }}