插入排序详解：原理、代码与时间复杂度

通俗地说，思路是什么

把第一个元素看作长度为 1 的有序列表。取出第二个元素，插到第一个之前或之后。取出第三个元素，插到前两个之间的合适位置。如此继续，直到每个元素都被插入。

插入时，先把新元素拿在一旁（称为 key），然后在已排序部分中向左移动。每个比 key 大的元素都向右移一格。走到一个不比它大的元素，或者到达列表开头时，就把 key 放进空位。

逐步演示

对 [12, 11, 13, 5, 6] 排序。竖线之前的部分已有序（但尚未最终确定）。

注意第 2 步：已经在正确位置的元素只需一次比较。这就是插入排序在接近有序的输入上很快的原因。

Python 实现

def insertion_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    for i in range(1, len(items)):
        key = items[i]
        j = i - 1
        while j >= 0 and items[j] > key:   # strict >, keeps it stable
            items[j + 1] = items[j]        # shift right
            j -= 1
        items[j + 1] = key                 # drop into the gap
    return items
print(insertion_sort([12, 11, 13, 5, 6]))   # [5, 6, 11, 12, 13]
print(insertion_sort([1, 2, 3, 4]))         # [1, 2, 3, 4], 3 comparisons

用移位代替交换，每个被移动的元素只写入一次，工作量约为基于交换的版本的一半。也可以像下面这样用二分查找来定位插入点。这样比较次数总共降为 O(n log n)，但移位仍是 O(n²)，所以整体时间仍是 O(n²)。

from bisect import insort_right
def binary_insertion_sort(items):
    result = []
    for x in items:
        insort_right(result, x)   # stable: equal items go after
    return result
print(binary_insertion_sort([3, 1, 2, 1]))   # [1, 1, 2, 3]

时间与空间复杂度

更精确地说，运行时间是 O(n + I)，其中 I 是逆序对（顺序颠倒的元素对）的数量。如果每个元素离其最终位置至多 k 个位置，则 I 至多为 n · k，因此插入排序是 O(n · k)：k 较小时非常快。

插入排序与其他排序算法的比较

插入排序是稳定的，因为元素只会向左越过严格更大的元素。它还是在线的：数据一边到达一边排序，任何时刻都保持一个有序的前缀。对于短列表，它的低开销胜过 O(n log n) 的算法，所以 Timsort（Python 使用，Java 对对象排序也使用）用二分插入排序处理短的有序段，许多快速排序的实现也会在规模小于某个阈值时切换到插入排序。

变体与常见错误

• 二分插入排序：用二分查找确定位置，再移位。比较次数更少，在比较代价高昂时很有帮助。
• 希尔排序：对相隔一定间距的元素运行插入排序，再把间距缩小到 1。它能让远处的元素快速移动，在大数组上比普通插入排序快得多。
• 链表上的插入排序：无需移位，但寻找位置仍是线性扫描。

何时使用插入排序

它适用于小数组（几十个元素）、接近有序的数据（例如排好序后又追加了几项的列表），以及需要简单、稳定、原地排序的场合。对于大规模的随机数据，请使用 O(n log n) 的排序；在 Python 中就是 sorted() 或 list.sort()，它们内部已经对小的有序段使用了插入排序。

面试题常要求写出追踪过程、最好与最坏情况、它为何稳定，或者它为什么在小规模和接近有序的输入上胜过 O(n log n) 算法。