插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法，其核心思想类似于整理扑克牌：每次从待排序序列中取出一张牌，插入到已排序序列的正确位置。

排序序列的划分

• 已排序序列：序列的前部分，已经有序
• 未排序序列：序列的后部分，尚未处理

插入排序的共性

1. 将排序序列分为已排序序列和未排序序列
2. 每一趟将选定的目标值插入到已排序序列的正确位置
3. 每一趟排序不能保证有一个元素到达最终位置（区别于冒泡排序）
4. 插入排序进行 $n$ 趟后能保证前 $n+1$ 个元素有序，但不能保证在最终位置

两种变体

• 直接插入排序：边查找插入位置边移动元素
• 折半插入排序：先用二分查找找到插入位置，再统一移动元素

直接插入排序

1. 初始时，将第一个元素视为已排序序列，其余元素为未排序序列
2. 从第二个元素开始，依次取出未排序序列中的元素
3. 将取出的元素与已排序序列中的元素从后往前逐个比较
4. 如果已排序元素 > 当前元素，则将已排序元素后移一位
5. 找到插入位置后，将当前元素放入该位置
6. 重复步骤 2-5，直到所有元素都插入到已排序序列

折半插入排序

1. 与直接插入排序类似，但查找插入位置时使用二分查找
2. 在已排序序列中用二分查找找到插入位置
3. 将插入位置之后的元素统一后移一位
4. 将当前元素放入插入位置

直接插入排序

void InsertSort(int A[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) {  // 从第二个元素开始
        if (A[i] < A[i-1]) {   // 如果当前元素比前一个小，需要插入
            temp = A[i];        // 暂存当前元素
            // 从后往前查找插入位置
            for (j = i - 1; j >= 0 && A[j] > temp; j--)
                A[j+1] = A[j];  // 元素后移
            A[j+1] = temp;      // 插入到正确位置
        }
    }
}

折半插入排序

void BinaryInsertSort(int A[], int n) {
    int i, j, low, high, mid, temp;
    for (i = 1; i < n; i++) {
        temp = A[i];           // 暂存当前元素
        low = 0; high = i - 1;
        // 二分查找插入位置
        while (low <= high) {
            mid = (low + high) / 2;
            if (A[mid] > temp)
                high = mid - 1;
            else
                low = mid + 1;  // 相等时也往右找，保证稳定性
        }
        // 统一后移元素
        for (j = i - 1; j >= high + 1; j--)
            A[j+1] = A[j];
        A[high+1] = temp;      // 插入到正确位置
    }
}