题目描述
把数组左边看作"已排序"。每次取右边第一个未排序的数，从右往左找到它该在的位置插入。
输入 = [5, 2, 4, 1, 3]
输出 = [1, 2, 3, 4, 5]
思路解析
当前要插入的数，和它左边已排序的数从右往左比：只要左边的更大，就把左边的往右挪一格，直到遇到不比它大的，把当前数放进腾出的空位。
5 是已排序起点：先把第一个数 5 看作已排序区（绿色）。从第二个数 2 开始插入。
插入 2 · 2<5 移到前：当前 2 比左边 5 小，5 右移，2 插到最前。现在已排序区是 [2,5]。
插入 4 · 落在 2 和 5 之间：当前 4：比 5 小（5 右移），比 2 大（停），插在中间。已排序区变成 [2,4,5]。
插入 1 · 一路移到最前：当前 1 比左边所有数都小，前面的 5、4、2 依次右移，1 插到最前。
插入 3 · 落在 2 和 4 之间：当前 3：5、4 右移，遇到 2 停下，3 插入。整个数组 [1,2,3,4,5] 有序了。
插入排序“自适应”——越接近有序越快。这也是为什么很多库的排序在小区间用插入排序收尾。
参考代码（Python）
Python
1for i in range(1, len(nums)):
2 cur = nums[i] # 待插入的数
3 j = i - 1
4 while j >= 0 and nums[j] > cur: # 比它大的右移
5 nums[j+1] = nums[j]; j -= 1
6 nums[j+1] = cur # 插入空位复杂度分析
- 时间复杂度：O(n²) —— 最坏；近乎有序时 O(n)
- 空间复杂度：O(1) —— 原地移动
套路模板
记住骨架：取当前数、左边大的右移、腾出位置落下。希尔排序就是“分组的插入排序”，把速度提到亚平方级。
Python
1for i in range(1, n):
2 cur, j = a[i], i - 1
3 while j >= 0 and a[j] > cur: # 大的右移腾位
4 a[j+1] = a[j]; j -= 1
5 a[j+1] = cur # 落位易错点
- ❌ 边比边交换(三次赋值) → ✅ 只右移、最后落位一次（右移比交换省，且保持稳定）
- ❌ while 漏判 j >= 0 → ✅ j >= 0 and a[j] > cur（插到最前时 j 会到 -1，先判越界）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。