插入排序

场景引入

打扑克牌时，你是怎么整理手牌的？每摸到一张新牌，你会从右向左扫描手牌，找到合适的位置插入。这就是插入排序的核心思想。

插入排序虽然平均时间复杂度也是 O(n²)，但它有一个重要特性：对近乎有序的数据极其高效。实际上，Java 的 Arrays.sort() 和 Python 的 sorted() 所使用的 TimSort 算法，其内部就是用插入排序来处理小规模或近乎有序的子数组。

核心思路

插入排序将数组分为已排序部分和未排序部分。每次从未排序部分取出第一个元素，在已排序部分中从后往前找到合适位置，将其插入。

算法步骤

将第一个元素视为已排序部分
取出未排序部分的第一个元素作为 key
从已排序部分的末尾开始，逐个与 key 比较
如果当前元素比 key 大，将其向右移动一位
直到找到不大于 key 的元素（或到达数组头部），将 key 插入该位置
重复步骤 2-5

为什么插入排序比冒泡排序好？

两者都是 O(n²) 的算法，但插入排序在实际运行中明显更快。原因有三：

赋值代替交换：冒泡排序每次交换需要 3 次赋值（temp = a; a = b; b = temp），而插入排序每次移动只需 1 次赋值（a[j+1] = a[j]）。同样的逆序度下，插入排序的赋值操作量约为冒泡排序的 1/3。
提前终止：找到插入位置后，内层循环立即停止，不需要继续扫描。
比较次数更少：冒泡排序即使加了 swapped 优化，每趟仍需扫描整个未排序区间。插入排序找到位置就停。

实测对比

用数据说话。下面的工具在你的浏览器中实时运行冒泡排序和插入排序，统计比较次数和移动/交换次数：

数组大小

数据分布

点击「运行测试」，在你的浏览器中实时运行排序算法，统计比较和交换次数。

可以观察到：相同的随机数据，插入排序的比较次数和移动次数都显著少于冒泡排序的比较次数和交换次数。平均来看，插入排序的移动和比较次数之和约为 0.25n²，而冒泡排序要高得多。

算法流程图

可视化演示

加载可视化中...

代码实现

javascript

function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    let key = arr[i];   // 待插入的元素
    let j = i - 1;
    // 将比 key 大的元素依次右移
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;   // 插入到正确位置
  }
  return arr;
}

二分插入排序

在已排序部分中查找插入位置时，可以用二分查找代替线性查找，将比较次数从 O(n) 降到 O(log n)。但元素移动次数不变，整体仍为 O(n²)。

javascript

function binaryInsertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    let key = arr[i];
    // 二分查找插入位置
    let lo = 0, hi = i;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (arr[mid] > key) hi = mid;
      else lo = mid + 1;
    }
    // 将 [lo, i-1] 的元素右移一位
    for (let j = i; j > lo; j--) {
      arr[j] = arr[j - 1];
    }
    arr[lo] = key;
  }
  return arr;
}

复杂度分析

	时间复杂度	空间复杂度
最好	O(n) — 已有序，内层循环不执行	O(1)
平均	O(n²)	O(1)
最坏	O(n²) — 完全逆序	O(1)

稳定性：稳定。相等元素不会越过彼此（arr[j] > key 用的是严格大于）。

适用场景：

数据量小（n < 50 左右）
数据基本有序（逆序对数量少）
在线排序（数据流式到达，边接收边排序）

深入理解

插入排序是稳定的原地排序算法
最好情况 O(n)，这是它胜过选择排序的关键
"哨兵"优化：将 arr[0] 作为哨兵，可省去 j >= 0 的边界检查
TimSort（JavaScript/Python/Java 标准排序）在小规模子数组上使用的就是插入排序

LeetCode 练习

LC 912. 排序数组 — 插入排序实现（大数据量会超时，用于学习）
LC 147. 对链表进行插入排序 — 链表版插入排序
LC 35. 搜索插入位置 — 二分查找插入位置，与二分插入排序的内层逻辑一致

插入排序 ​

场景引入 ​

核心思路 ​

算法步骤 ​

为什么插入排序比冒泡排序好？ ​

实测对比 ​

算法流程图 ​

可视化演示 ​

代码实现 ​

二分插入排序 ​

复杂度分析 ​

深入理解 ​

LeetCode 练习 ​