插入排序

定义与基本思想

插入排序（Insertion Sort）是一种简单直观的排序方法。其基本思想是：每次将一个待排序元素插入到已排好序的序列中，直到全部元素有序。

算法描述

1. 从第 2 个元素开始，依次与前面已排序序列比较，找到合适位置插入
2. 重复直到所有元素排序完成

伪代码如下：

for i = 1 to n-1:
    key = A[i]
    j = i-1
    while j >= 0 and A[j] > key:
        A[j+1] = A[j]
        j--
    A[j+1] = key

代码实现

void InsertSort(int A[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = A[i];           // 待插入元素
        j = i - 1;
        while (j >= 0 && A[j] > key) {
            A[j + 1] = A[j];  // 元素后移
            j--;
        }
        A[j + 1] = key;       // 插入到正确位置
    }
}

折半插入排序

直接插入排序的比较可以用折半查找优化：因为前面部分已有序，用折半定位插入位置，减少比较次数，但移动次数不变。

void BinaryInsertSort(int A[], int n) {
    int i, j, low, high, mid, key;
    for (i = 1; i < n; i++) {
        key = A[i];
        low = 0; high = i - 1;
        while (low <= high) {          // 折半查找插入位置
            mid = (low + high) / 2;
            if (A[mid] > key) high = mid - 1;
            else low = mid + 1;
        }
        for (j = i - 1; j >= low; j--)  // 元素后移
            A[j + 1] = A[j];
        A[low] = key;
    }
}

时间复杂度分析

• 最好情况：$O(n)$（原本有序）
• 最坏/平均情况：$O(n^2)$
• 空间复杂度：$O(1)$
• 稳定性：稳定排序

习题

习题 1

对数组 $A = [5, 2, 4, 6, 1, 3]$ 进行插入排序，写出每一趟排序后的结果。

习题 2

插入排序的时间复杂度和空间复杂度分别是多少？