插入排序 | 是熊是猫溜溜

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐>步向后挪位，为最新元素提供插入空间。

主要思想

每次从剩余的未排序的元素中选取一个元素插入到前面已排序的元素中，使整体有序。下面以正序为例说明整个过程。

原数据：

1	[9] [8] [7] [1] [3] [5]

第一步：选择[9]插入到前面已排序的元素中，由于是第一个元素，已经排序好了。可以看到结果如下。

1	[9] [8] [7] [1] [3] [5]

未排序

1	[8] [7] [1] [3] [5]

已排序

[9]

第二步：选择[8]插入到前面已排序的元素中，[8]比[9]小，因此在[9]前面，可以看到结果如下。

1	[8] [9] [7] [1] [3] [5]

未排序

1	[7] [1] [3] [5]

已排序

[8] [9]

第三步：选择[7]插入到前面已排序的元素中，[7]比[8]小，因此在[8]前面，可以看到结果如下。

1	[7] [8] [9] [1] [3] [5]

未排序

1	[1] [3] [5]

已排序

1	[7] [8] [9]

第四步：选择[1]插入到前面已排序的元素中，[1]比[7]小，因此在[7]前面，可以看到结果如下。

1	[1] [7] [8] [9] [3] [5]

未排序

[3] [5]

已排序

1	[1] [7] [8] [9]

第五步：选择[3]插入到前面已排序的元素中，[3]小于[7]大于[1]，因此[3]在[1]和[7]之间，可以看到结果如下。

1	[1] [3] [7] [8] [9] [5]

未排序

[5]

已排序

1	[1] [3] [7] [8] [9]

第六步：同理插入[5]，可以看到结果如下。

1	[1] [3] [5] [7] [8] [9]

未排序

已排序

1	[1] [3] [5] [7] [8] [9]

最终得到一个正序数组。

时间与空间复杂度

插入排序是稳定的排序算法，其时间复杂度计算公式如下。可以看到插入排序最好的情况时间复杂度为n，最坏的情况下时间复杂度均为2^n，空间复杂度为O(1)，平均时间复杂度为2^n。

$$
k1 + k2 + k3 + k4 + … kn = \sum_{k=1}^{n}{k_n} (1 <= k1,k2,…,kn <= n-1)
$$

代码实现

public static void insertion(Comparable[] c){
    int N = c.length;
    for(int i = 1; i < N; i++){
        for(int j = i; j > 0 && less(c[j], c[j-1]); j--){
            exch(c, j, j-1);
        }
    }
}