直接插入排序

直接插入排序把序列看成已排序前缀 + 未排序后缀；每次把后缀第一个元素插入前缀的合适位置。

本文解决什么问题

• 插入排序如何写
• 复杂度与稳定性
• 为何小数组 / 基本有序时很实用

算法过程

初始: [ 已排序 | 未排序 ]
每趟: 取未排序第一个，在已排序区从后往前挪出空位插入

void insertion_sort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

比较用 > 而不是 >=，相等时不挪动，从而稳定。

复杂度

	时间	说明
最好	$O(n)$	已有序，内层不移动
平均 / 最坏	$O(n^2)$	逆序时移动最多
空间	$O(1)$	原地
稳定	是

应用

• 小 $n$（如 $n \le 32$）时常数好，常嵌在快排优化里
• 基本有序数据表现好
• 希尔排序 在其思想上改进

小结

插入排序是理解「维护有序区」的入门。下一篇：希尔排序。