插入排序

思想

1. 当插入第i (i >= 1) 个对象时, 前面的V[1], V[2], …, V[i-1]已经排好序。
2. 这时, 用V[i]的排序码与V[i-1], V[i-2], …的排序码顺序进行比较, 找到插位置即将V[i]插入, 原来位置上的对象向后顺移。

图片

代码

public static <AnyType extends Comparable<? super AnyType>>
    void insertSort(AnyType[] a) {

        //1.定义要找的那个元素在有序列符合的位置
        int j;

        //2.循环，最开始只有一个有序
        for (int p = 1; p < a.length; p++) {
            //1.要找的那个元素放到临时变量里面
            AnyType tmp = a[p];

            //2.在有序列里面从后往前找符合的位置，因为p从1开始，故跟j-1比
            for (j = p; j > 0 && tmp.compareTo(a[j - 1]) < 0; j--) {
                a[j] = a[j - 1];//比前一个小，前面那个往后挪
            }
            //3.上面循环结束时j--，故这时j是正确位置
            a[j] = tmp;
        }

    }

分析

嵌套循环的每一个都花费W次迭代，因此插人排序为 O(n2)