插入排序

算法思路

可以把插入排序想象成扑克中的插牌，步骤如下：

• 手中的牌永远是从小到大排序好的
• 新抽到的牌会放在手牌的最右侧
• 然后将新抽到的牌与其左侧的牌进行比较，如果小于左侧的牌则与其互换位置
• 重复上一步骤，直到新抽的牌大于其左侧的牌为止
• 重新抽取一张新牌放在手牌的最右侧，重复以上步骤，直到抽完所有牌为止

应用在实际的数组中，步骤如下（假设数组a中含有n个元素）：

• 在最开始时，a[0]可以看做为已经排序好的手牌
• a[1]为新抽的手牌
• 比较a[0]和a[1]，如果a[0] > a[1]，互换位置
• 此时，a[0] ~ a[1]为已经排序好的手牌
• a[2]为新抽的手牌
• a[2]先于a[1]比较，如果小于a[1]，则互换位置；a[2]继续和a[0]比较，如果小于a[0]，则互换位置。以上步骤如果a[2]大于与其比较的元素，则立即停止
• 重复以上步骤，直到遍历完整个数组

代码

从上面的例子可以看出，插入排序需要两个指针进行循环：

• 指针1：永远指向新抽的手牌，即，需要排序的元素的位置。并依次向右循环指针。
• 指针2：永远指已排序好的元素的最末位置。并依次向左循环与指针1进行比较。
• 因为默认a[0]为已经排序好的手牌，所以指针1应该从索引1的位置开始遍历

insertion(int[] a)
{
    int N = a.length;
    for (int i = 1; i < N; i++) { // 指针1从索引位置1开始，向右遍历
        for (int j = i; j > 0 && (a[j] < a[j - 1]); j--) { // j-1为指针1上一元素，依次向左遍历
            exch(a, j, j - 1); // 互换位置
        }
    }
}

时间&空间

• 空间：因为直接在原数组中进行排序操作，无需额外的空间，空间复杂度为O(1)
• 时间：最坏情况下，时间复杂度为~O(N²/2)

  • 证明：

    插入排序的最坏情况为将一个倒序排序的数组排列为一个正序排序的数组。以上面的手牌例子来讲，即每次抽到的新手牌小于所有已排序好的手牌。因为新抽的手牌需要依次与前面排序好的每一张手牌进行比较和互换。

    以上例子可以写作为一个长度为N的数组a = {n, n-1, n-2, n-3, ... 3, 2, 1}，n为数组中最大的元素。如果将这个数组进行排序：

    0. {n, n-1, n-2, n-3, ... 3, 2, 1} // 原数组
    1. {n-1, n, n-2, n-3, ... 3, 2, 1} // 1次操作
    2. {n-2, n-1, n, n-3, ... 3, 2, 1} // 2次操作
    3. {n-3, n-2, n-1, n, ... 3, 2, 1} // 3次操作
    ...
    n. {1, 2, 3, ... n-3, n-2, n-1, n} // n-1次操作
    
    操作和：
      1 + 2 + 3 + ... + (n-3) + (n-2) + (n-1) 
    = (n-1) * ((n-1)+1) / 2 
    = n(n-1)/2
    ~ n^2/2