算法导论-算法基础-插入排序

插入排序

输入:n个数的一个序列<a1,a2,…,an>。
输出:输入序列的一个排列<a1',a2',…,an‘>,满足a1'≤a2'≤…≤an'。

    public static void insertionSort(int[] a){
        int key,i;
        for(int j=1;j<a.length;j++){
            key=a[j];
            i=j-1;
            while(i>=0&&a[i]>key){
                a[i+1]=a[i];
                i=i-1;
            }
            a[i+1]=key;
        }
    }

j表示正准备插入的数的下标，a[0,j-1]构成了当前排序好的数组，事实上，a[0,j-1]就是原来位置a[0,j-1]的元素，但现在已按序排列。

InsertionSort.java