插入排序 --- Java版

算法思路

插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。 非常类似于打牌时候一边抓牌一遍理牌的情形。
插入排序方法分直接插入排序和折半插入排序两种，这里只介绍直接插入排序。
  文字说比较抽象, 下面有个动态图链接🔗帮助理解:
插入排序动态演示图

算法实现

public class InsertionSort {

    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++)    // i表示现在正在遍历元素的下标
            //从遍历的那个元素开始向前进行比较，碰到比之前一个元素小就交换，
            //不然直接break(因为左边区域已经有序，若a[j]比a[j-1]大那么一定比a[j-2],a[j-3]...大，那就不用比较交换了)
            for (int j = i; j > 0; j--)    
                if (less(a, j, j - 1))
                    swap(a, j, j - 1);
                else
                    break;
    }

    private static boolean less(Comparable[] a, int i, int j) {
        if (a[i].compareTo(a[j]) < 0)
            return true;
        else
            return false;
    }

    private static void swap(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

性能分析

  首先给一个前提，插入排序性能是有最好情况和最坏情况的，不一样。
  那哪种情况是最好情况？相信你猜出来了就是已经有序的待排数组的情况。如果数组已经有序, 那么看代码，里层循环永远不会执行(会执行break语句)，所以只有外层循环起作用那么时间复杂度就是O(N)。
  那哪种情况是最好情况？相信你也猜出来了就是完全逆序的待排数组的情况。数组完全逆序，插入第2个元素时要比较交换前1个元素，插入第3个元素时，要比较交换前2个元素，……，插入第N个元素，要比较交换前 N - 1 个元素。因此，最坏情况下的比较次数是 1 + 2 + 3 + ... + (N - 1)，等差数列求和，结果为 N^2 / 2，所以最坏情况下的时间复杂度为 O(N^2)。空间复杂度则很直观O(1)。
  综上所述，通过某些数学证明(我目前不懂那个证明，还请网友告知)已经证明出，对于一个完全random且元素不重复的带排序数组，用插入排序平均需要 ¼ N^2 次比较和¼ N^2 交换操作。
  我大概只能从下面这张插入排序步骤图大概看出¼ N^2 这个数字的来源。因为每行灰色的是每次都不移动已经排序好的元素，黑色的是移动的元素，可以看出移动的元素面积大概是所有面积的1/4，这就是平均需要 ¼ N^2 次比较和¼ N^2 交换操作的直观证明。(但是我不知道怎么具体证明......)

algorithm4_princeton

拓展

  如果数组中倒序的元素数量小于数组大小的某个倍数，那么我们就说这个数组部分有序。
有几种典型的部分有序数组：

• 数组中每个元素距离它最终位置不远;
• 一个基本有序的大数组接一个无序小数组;
• 数组中只有几个元素位置不对;
  这些数组都适合用插入排序。

  逆序对:

对于一个包含N个非负整数的数组A[1..n]，如果有i < j，且A[ i ]>A[ j ]，则称(A[ i] ,A[ j] )为数组A中的一个逆序对。

inversion_pair.png
比如
上面这个数组就有6个逆序对。
这里有个定理: 插入排序需要的swap操作和数组中逆序对个数是一样的，需要compare操作的个数大于等于逆序对数目,但小于等于逆序对加上数组大小减1。