插入排序 图解题解
这道题到底在问什么
- 输入
- [5, 2, 4, 1, 3]
- 输出
- [1, 2, 3, 4, 5]
先想最直接的笨办法
为什么不像选择排序那样扫全局？因为左边已经有序了，新牌只要和左边从右往左挨个比，遇到第一个不比它大的就停——逆序时最慢要比到头（O(n²)），但近乎有序时几乎一比就停（O(n)）。（动画第 3 步）
最优解：一步一步想明白
- 3为什么不像选择排序那样扫全局？因为左边已经有序了，新牌只要和左边从右往左挨个比，遇到第一个不比它大的就停——逆序时最慢要比到头（O(n²)），但近乎有序时几乎一比就停（O(n)）。
- 4每插入完第 i 个数，前缀 0..i 一定有序。插入靠的是"把左边比它大的整体右移一格腾出空位"，而不是交换——右移比交换省一次赋值，还保持稳定。
- 5i=1先把第一个数 5 看作已排序区（绿色）。从下标 1 开始，把右边的数一张张往左插。
- 6i=1 cur=2轮到下标 1 的 2（橙色）。把它取出暂存，下标 1 这格视作空位，接下来和左边已排序的数从右往左比。
- 7cur=2 j=0和左边下标 0 的 5 比：5 大于 2，它得给 2 让位，右移一格。
- 8cur=2 j=-1把 5 右移到下标 1（不是交换，只是复制一格）。空位左移到下标 0，cur=2 继续往左比。
- 9落 0左边到头（j=-1），没有更多牌可比，把暂存的 2 放进腾出的下标 0。前缀 0..1 变成 [2, 5]，依旧有序。
- 10i=2 cur=4轮到下标 2 的 4（橙色）。把它取出暂存，下标 2 这格视作空位，接下来和左边已排序的数从右往左比。
- 11cur=4 j=1和左边下标 1 的 5 比：5 大于 4，它得给 4 让位，右移一格。
- 12cur=4 j=0把 5 右移到下标 2（不是交换，只是复制一格）。空位左移到下标 1，cur=4 继续往左比。
- 13落 1下标 0 的 2 不大于 4，循环停下，把暂存的 4 放进腾出的下标 1。前缀 0..2 变成 [2, 4, 5]，依旧有序。
- 14i=3 cur=1轮到下标 3 的 1（橙色）。把它取出暂存，下标 3 这格视作空位，接下来和左边已排序的数从右往左比。
- 15cur=1 j=2和左边下标 2 的 5 比：5 大于 1，它得给 1 让位，右移一格。
- 16cur=1 j=1把 5 右移到下标 3（不是交换，只是复制一格）。空位左移到下标 2，cur=1 继续往左比。
- 17cur=1 j=1和左边下标 1 的 4 比：4 大于 1，它得给 1 让位，右移一格。
- 18cur=1 j=0把 4 右移到下标 2（不是交换，只是复制一格）。空位左移到下标 1，cur=1 继续往左比。
- 19cur=1 j=0和左边下标 0 的 2 比：2 大于 1，它得给 1 让位，右移一格。
- 20cur=1 j=-1把 2 右移到下标 1（不是交换，只是复制一格）。空位左移到下标 0，cur=1 继续往左比。
- 21落 0左边到头（j=-1），没有更多牌可比，把暂存的 1 放进腾出的下标 0。前缀 0..3 变成 [1, 2, 4, 5]，依旧有序。
- 22i=4 cur=3轮到下标 4 的 3（橙色）。把它取出暂存，下标 4 这格视作空位，接下来和左边已排序的数从右往左比。
- 23cur=3 j=3和左边下标 3 的 5 比：5 大于 3，它得给 3 让位，右移一格。
- 24cur=3 j=2把 5 右移到下标 4（不是交换，只是复制一格）。空位左移到下标 3，cur=3 继续往左比。
- 25cur=3 j=2和左边下标 2 的 4 比：4 大于 3，它得给 3 让位，右移一格。
- 26cur=3 j=1把 4 右移到下标 3（不是交换，只是复制一格）。空位左移到下标 2，cur=3 继续往左比。
- 27落 2下标 1 的 2 不大于 3，循环停下，把暂存的 3 放进腾出的下标 2。前缀 0..4 变成 [1, 2, 3, 4, 5]，依旧有序。
- 28done五张牌全部插完，前缀铺满整个数组，[1, 2, 3, 4, 5] 完全有序。这就是插入排序的全过程。
⚠️ 容易写错的地方
✗ 错：while a[j] > cur:（漏了 j 越界判断）
✓ 对：while j >= 0 and a[j] > cur:
插到最前时 j 会一路减到 -1，先判 j >= 0 才不会数组越界；and 短路让越界判断在前
✗ 错：用边比边交换（三次赋值）
✓ 对：只右移、循环结束后落位一次
右移每步只一次赋值比交换省，且相等不动保证稳定
完整代码（Python / C++ / Java）
Python
for i in range(1, len(nums)):
cur = nums[i] # 取出待插入的牌，腾出空位
j = i - 1 # 从前缀最右开始往左找
while j >= 0 and nums[j] > cur: # 比 cur 大的整体右移
nums[j + 1] = nums[j] # 右移一格（不是交换）
j -= 1
nums[j + 1] = cur # 遇到不比它大的，落位C++
class Solution {
public:
void insertionSort(vector<int>& nums) {
for (int i = 1; i < nums.size(); ++i) {
int cur = nums[i];
int j = i - 1;
while (j >= 0 && nums[j] > cur) {
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = cur;
}
}
};Java
class Solution {
public void insertionSort(int[] nums) {
for (int i = 1; i < nums.length; ++i) {
int cur = nums[i];
int j = i - 1;
while (j >= 0 && nums[j] > cur) {
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = cur;
}
}
}复杂度
时间复杂度
O(n²)
最坏（完全逆序）每个数都要移到头；近乎有序时退化到 O(n)
空间复杂度
O(1)
只在原数组上右移，不开额外数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 插入排序 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
插入排序为什么用"右移"而不是"交换"？+
取出 cur 后，把比它大的元素逐个复制到右边一格，最后把 cur 落到空位。右移每步只一次赋值，交换要三次；而且相等元素不移动，保证了稳定性。
它和冒泡、选择排序比有什么优势？+
插入排序是自适应的：数组近乎有序时接近 O(n)，而选择排序无论如何都跑满 n²/2 次比较。它还是稳定排序，冒泡也稳定但常数更大。
为什么 while 条件要先判 j >= 0？+
当 cur 是最小值要插到最前时，j 会一直减到 -1。利用 and 的短路，先判 j >= 0 再访问 nums[j]，避免下标越界。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 插入排序 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。