2、数据结构与算法——插入排序 - liuxiaofei2010S/special-column GitHub Wiki

插入排序的思想主要是类似于扑克牌的排序方法。在含有第一张的时候，后面的项会比较前面已经排列好的序列去插入当前项。从右到左依次观察大小顺序，如果大于当前项，则插入到它之前，也就是交换项的位置。

代码如下：

public class InsertSort {

    public static void main(String[] args) {
        System.out.print("——————————————————————————————");
        int[] array = new int[]{2, 4, 7, 0, 6, 8, 1, 5, 9, 3};
        sort(array);
        System.out.print("——————————————————————————————");
    }

    /*从右往左依次比较,如果小于某一项则更换位置*/
    private static void sort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int k = i; k > 0 && array[k] < array[k - 1]; k--) {
                exch(array, k, k - 1);
            }
        }
        for (int d = 0; d < array.length; d++) {
            System.out.print(array[d]);
        }
    }

    private static void exch(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

插入排序的效率一般交换次数为 N²/4，比较次数为 N²/4。最好的情况（完全有序）比较次数为 N-1,更换次数为 0；最坏情况（完全反序）交换次数为N²/2，比较次数为 N²/2。

插入排序适合于 部分有序 的数组，或者 小规模 数组。

倒置指的是数组中两个顺序颠倒的元素。插入排序的交换次数与倒置的次数是一致的。

部分有序数组：1、数组中每个元素与它的最终位置都不远；2、一个有序的大数组接一个小数组；3、数组中只有几个元素位置不正确。