03插入排序

原理

口语描述：第二个和第一个比，从小到大排。第三个和第二个比，再和第一个比，从小到大排。第四个和第三个、第二个、第一个比，从小到大排。。。。。

数组a[n]，lenght=n
从a[1] 开始到a[n-1]结束和之前的值进行比较，按从小到大的顺序排。
a[1]和a[0]比较，若a[1] < a[0]，交换a[1] 和 a[0]。
a[0]-a[1]已经排好序，让a[2]和a[1]比较，
①若a[2] < a[1]，则交换a[2] 和 a[1]，再比较a[1]和a[0]，若a[1]< a[0]则交换。
②若a[2]不小于a[1]则不动。
这时a[0],a[1],a[2]已经排好序。
接着轮到a[3]和前面的a[0],a[1],a[2]作比较，发现比自己大的就交换。一直轮到a[n-1]

代码

//插入排序
public class Sort03 {

    public static void main(String[] args) {
        int[] array = { 2, 15, 7, 9, 30, 1, 5 };
        insertSort(array);
        for (int i : array) {
            System.out.print(i+" ");
        }
    }

    /**
     * 数组a[n], lenght=n
     * 按照最坏的情况计算
     * i∈[1,n-1]
     * i=1时j∈[1],循环1次
     * i=2时j∈[2,1],循环2次
     * i=n-1时j∈[n-1,1],循环n-1次
     * 
     * 所以，当数组长度为n时，内层循环执行的次数=swap()方法执行的次数，为(n²-n)/2
     * 时间复杂度为O(n²)
     */
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j > 0; j--) {
                if (array[j] < array[j - 1]) {
                    swap(array, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }

    public static void swap(int[] array, int x, int y) {
        int temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }
    
}

输出结果

1 2 5 7 9 15 30