插入排序 (Insertion Sort)小规模数据的王者摘要堆排序和归并排序保证了最坏 O(n log n)但引入了缓存不友好或 O(n) 空间的代价。插入排序反其道而行——O(n²) 的平均复杂度看似落后但在小规模数据n 20和近乎有序数据上却是实际最快的排序算法。本文从扑克牌整理出发图解插入排序的逐步插入过程给出支持升序/降序的 Python 完整实现对比其与冒泡排序的本质差异并分析 TimSort、IntroSort 等工业级排序为何将其作为小区间回退方案。本文属于专栏《算法》系列 1 第 6 篇 | 上一篇堆排序 (Quick Sort)| 下一篇1-7-选择排序-SelectionSort文章目录插入排序 (Insertion Sort)小规模数据的王者一、问题引入二、算法原理图解核心思想图解执行过程关键观察插入排序 vs 冒泡排序本质区别三、代码实现完整实现运行验证四、复杂度分析时间复杂度空间复杂度稳定性五、横向对比插入排序 vs 冒泡排序 vs 选择排序六、工程实战TimSort 中的插入排序IntroSort 中的插入排序二分插入排序性能实测七、常见误区与面试题高频面试题常见实现错误八、总结一、问题引入前面几篇文章中快速排序、归并排序、堆排序都已达到 O(n log n)。那为什么还要学一个 O(n²) 的排序考虑以下场景TimSortPython/Java 默认排序当区间缩小到 64 个元素时切换为插入排序IntroSortCstd::sort当区间缩小到 16 个元素时切换为插入排序近乎有序数据1000 个元素中只有 10 个错位插入排序比快排还快这些工业级排序在递归到小区间时都不约而同地选择了插入排序作为回退方案。为什么因为插入排序有两个其他 O(n²) 排序不具备的优势最好情况 O(n)已有序数据只需一轮扫描无需任何移动移动代替交换用元素后移腾位 一次插入代替冒泡排序的反复交换写操作减少一半以上生活中的直觉整理扑克牌。左手持已排序的牌右手从桌上逐张拿牌从右向左在左手牌中找到合适位置插入——这正是插入排序。问题定义输入含 n 个元素的可比较数组arr输出按升序或降序排列的数组核心操作逐个将元素插入已排序部分的正确位置二、算法原理图解核心思想将数组分为已排序部分和未排序部分每次从未排序部分取第一个元素在已排序部分中从右向左找到正确位置插入。[已排序部分 | current | 未排序部分] ↑ 待插入 j 指向 ←图解执行过程以[5, 3, 8, 1, 2]升序排序为例|标记已排序部分与未排序部分的边界初始状态: [5 | 3, 8, 1, 2] 已排序: [5] 第 1 轮: current3 3 55 后移 → [_, 5, 8, 1, 2] j 越界插入 3 → [3, 5 | 8, 1, 2] 已排序: [3, 5] 第 2 轮: current8 8 5不移动直接插入 → [3, 5, 8 | 1, 2] 已排序: [3, 5, 8] 第 3 轮: current1 1 88 后移 → [3, 5, _, 8, 2] 1 55 后移 → [3, _, 5, 8, 2] 1 33 后移 → [_, 3, 5, 8, 2] j 越界插入 1 → [1, 3, 5, 8 | 2] 已排序: [1, 3, 5, 8] 第 4 轮: current2 2 88 后移 → [1, 3, 5, _, 8] 2 55 后移 → [1, 3, _, 5, 8] 2 33 后移 → [1, _, 3, 5, 8] 2 1不移动插入 2 → [1, 2, 3, 5, 8] 已排序: [1, 2, 3, 5, 8] 最终结果: [1, 2, 3, 5, 8]关键观察每轮只移动必要的元素比 current 大的元素逐个后移current 一次插入到位而非像冒泡排序那样反复交换已有序时一轮即完成第 2 轮 current8 时8 5 无需移动直接进入下一轮——n 个元素只需 n-1 次比较逆序对决定复杂度每个逆序对需要一次后移总移动次数 数组的逆序对数量插入排序 vs 冒泡排序本质区别维度冒泡排序插入排序核心操作相邻比较 交换后移腾位 一次插入每个逆序对3 次赋值交换1 次赋值后移已有序数据O(n)提前终止O(n)无后移近乎有序较好更好后移次数少写操作多每次交换 3 次写少后移 1 次写 插入 1 次写核心差异冒泡排序每消除一个逆序对需要 3 次赋值a↔b插入排序只需 1 次赋值后移 最后 1 次插入。写操作减少约 2/3这是插入排序实际更快的根本原因。三、代码实现完整代码通过网盘分享的文件算法链接: https://pan.baidu.com/s/1DTJt1X2Is_IQeH5fAXvtZg?pwdyyqf 提取码: yyqf–来自百度网盘超级会员v4的分享完整实现definsertion_sort(arr,ascendingTrue): 插入排序将每个元素插入到已排序部分的正确位置。 类似整理扑克牌左手持已排序的牌右手从桌上逐张拿牌 从右向左在左手牌中找到合适位置插入。 时间复杂度O(n²) | 空间复杂度O(1) | 稳定排序 参数: arr: 待排序列表 ascending: 排序方向True升序默认False降序 返回: 排序后的列表原地排序 nlen(arr)ifn1:returnarr# 从第 2 个元素开始逐个插入到前面已排序部分foriinrange(1,n):currentarr[i]# 待插入元素右手拿到的牌ji-1# 已排序部分的右边界# 升序current 小于前驱则前驱后移降序current 大于前驱则前驱后移ifascending:whilej0andarr[j]current:arr[j1]arr[j]# 元素后移腾出位置j-1else:whilej0andarr[j]current:arr[j1]arr[j]j-1arr[j1]current# 插入到正确位置returnarr三个关键设计current暂存待插入元素避免后移过程中覆盖arr[i]这是插入排序区别于冒泡排序的核心while从右向左扫描比 current 大的元素逐个后移而非交换遇到不大于 current 的位置立即停止arr[j 1] current一次插入后移完成后current 一次写入正确位置写操作仅 (后移次数 1) 次运行验证if__name____main__:data[64,34,25,12,22,11,90]print(f排序前:{data})print(f升序:{insertion_sort(data[:])})print(f降序:{insertion_sort(data[:],ascendingFalse)})# 边界测试print(f空列表:{insertion_sort([])})print(f单元素:{insertion_sort([42])})print(f已有序:{insertion_sort([1,2,3,4,5])})print(f全相同:{insertion_sort([7,7,7,7,7])})print(f逆序:{insertion_sort([5,4,3,2,1])})# 小规模数据性能对比插入排序的优势场景importtimeimportrandom# 近乎有序数据插入排序的王者场景nearly_sortedlist(range(1000))for_inrange(10):i,jrandom.randint(0,999),random.randint(0,999)nearly_sorted[i],nearly_sorted[j]nearly_sorted[j],nearly_sorted[i]starttime.time()insertion_sort(nearly_sorted[:])print(f\n近乎有序(1000): 插入排序{time.time()-start:.6f}s)starttime.time()insertion_sort(random.sample(range(1000),1000))print(f随机数据(1000): 插入排序{time.time()-start:.6f}s)输出排序前: [64, 34, 25, 12, 22, 11, 90] 升序: [11, 12, 22, 25, 34, 64, 90] 降序: [90, 64, 34, 25, 22, 12, 11] 空列表: [] 单元素: [42] 已有序: [1, 2, 3, 4, 5] 全相同: [7, 7, 7, 7, 7] 逆序: [1, 2, 3, 4, 5] 近乎有序(1000): 插入排序 0.000474s 随机数据(1000): 插入排序 0.020274s近乎有序数据下比随机数据快42 倍——这就是插入排序在小规模和近乎有序场景下的王者实力。四、复杂度分析时间复杂度情况复杂度说明最好O(n)数组已有序每轮只比较 1 次不后移平均O(n²)每个元素平均后移 i/2 次总移动 n²/4最坏O(n²)完全逆序每个元素后移到底推导过程第 i 轮current arr[i]最多与前面 i 个元素比较并后移 最好情况已有序 每轮比较 1 次后移 0 次 总比较 1 1 ... 1 n-1 O(n) 最坏情况完全逆序 第 1 轮比较 1 次后移 1 次 第 2 轮比较 2 次后移 2 次 ... 第 n-1 轮比较 n-1 次后移 n-1 次 总比较 1 2 ... (n-1) n(n-1)/2 O(n²) 平均情况 第 i 轮平均后移 i/2 次 总移动 ≈ n²/4 O(n²)核心结论插入排序的复杂度与数组的逆序对数量成正比。逆序对越少排序越快。这正是近乎有序数据下性能极佳的原因。空间复杂度O(1)——仅使用current、i、j等常数个辅助变量原地排序。稳定性稳定排序。while条件为arr[j] current严格大于相等元素不会后移相对顺序保持不变。如果改为相等元素也会后移破坏稳定性。五、横向对比插入排序与同系列算法的对比算法平均时间最好时间最坏时间空间稳定性特点冒泡排序O(n²)O(n)O(n²)O(1)稳定最简单写操作多插入排序O(n²)O(n)O(n²)O(1)稳定小数据 近乎有序最优选择排序O(n²)O(n²)O(n²)O(1)不稳定交换次数最少但无法提前终止快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定通用场景最快归并排序O(n log n)O(n log n)O(n log n)O(n)稳定稳定 不退化插入排序 vs 冒泡排序 vs 选择排序三种 O(n²) 排序的细微差异维度冒泡排序插入排序选择排序每轮操作相邻比较交换后移 插入找最小值 一次交换写操作/逆序对3 次交换1 次后移1 次末尾交换最好情况O(n)O(n)O(n²)稳定性稳定稳定不稳定近乎有序较快最快慢仍需全扫描实际速度最慢中等中等选型建议小规模数据n 20插入排序写操作少常数因子最小近乎有序数据插入排序逆序对少接近 O(n)交换代价极高的场景选择排序交换次数最少每轮最多 1 次大规模数据快速排序或 TimSort六、工程实战TimSort 中的插入排序Pythonlist.sort()和 Java 对象排序使用 TimSort其核心设计之一就是在小区间切换为插入排序TimSort 流程 1. 扫描自然有序的 Run连续升/降序片段 2. 若 Run 长度 32MIN_MERGE用插入排序补充到 32 3. 多个 Run 在栈上归并为什么选插入排序而非冒泡排序维度插入排序冒泡排序写操作后移 1 次 插入 1 次交换 3 次已有序片段直接跳过仍需逐对比较局部性扫描已排序部分相邻比较IntroSort 中的插入排序Cstd::sort使用 IntroSort快排 堆排 插入排序当递归到小区间通常 16 元素时切换为插入排序defintro_sort(arr,low,high,depth_limit):ifhigh-low16:# 小区间插入排序insertion_sort_range(arr,low,high)returnifdepth_limit0:# 递归过深堆排序heap_sort_range(arr,low,high)return# 默认快速排序pivotpartition(arr,low,high)intro_sort(arr,low,pivot-1,depth_limit-1)intro_sort(arr,pivot1,high,depth_limit-1)为什么阈值是 16~64当 n 很小时O(n²) 的常数 n²/4 O(n log n) 的常数 n log n。具体来说n16 时插入排序约 64 次比较快排约 64 次比较 递归开销n64 时插入排序约 1024 次比较TimSort 阈值选 32 作为平衡点二分插入排序插入排序的变体——用二分查找确定插入位置减少比较次数defbinary_insertion_sort(arr):foriinrange(1,len(arr)):currentarr[i]# 二分查找插入位置lo,hi0,iwhilelohi:mid(lohi)//2ifarr[mid]current:himidelse:lomid1# 后移 插入forjinrange(i,lo,-1):arr[j]arr[j-1]arr[lo]currentreturnarr维度直接插入二分插入比较次数O(n²)O(n log n)移动次数O(n²)O(n²)不变总复杂度O(n²)O(n²)移动仍为主二分插入排序减少了比较次数但移动次数不变总复杂度仍为 O(n²)。在比较代价高的场景如字符串排序有优势。性能实测importrandomimporttime# 近乎有序数据nearly_sortedlist(range(1000))for_inrange(10):i,jrandom.randint(0,999),random.randint(0,999)nearly_sorted[i],nearly_sorted[j]nearly_sorted[j],nearly_sorted[i]starttime.time()insertion_sort(nearly_sorted[:])print(f插入排序(近乎有序):{time.time()-start:.6f}s)starttime.time()sorted(nearly_sorted[:])print(fTimSort(近乎有序):{time.time()-start:.6f}s)# 随机数据random_datarandom.sample(range(1000),1000)starttime.time()insertion_sort(random_data[:])print(f插入排序(随机):{time.time()-start:.6f}s)starttime.time()sorted(random_data[:])print(fTimSort(随机):{time.time()-start:.6f}s)典型输出n1000插入排序(近乎有序): 0.000474s TimSort(近乎有序): 0.000090s 插入排序(随机): 0.020274s TimSort(随机): 0.000200s近乎有序场景下插入排序已经非常接近 TimSort 的速度且实现极简。随机数据下 TimSort 快 100 倍但 TimSort 内部本身也在用插入排序处理小 Run。七、常见误区与面试题高频面试题Q1插入排序和冒泡排序都是 O(n²)为什么插入排序实际更快核心差异在写操作。冒泡排序每次交换需要 3 次赋值a↔b需临时变量插入排序用后移代替交换每个逆序对只需 1 次赋值后移 最后 1 次插入。总写操作约为冒泡排序的 1/3。此外插入排序在已排序部分的扫描有局部性CPU 缓存利用率更高。Q2插入排序最好情况为什么是 O(n)当数组已有序时每个current都比前一个元素大while条件arr[j] current立即为False不执行任何后移。n-1 轮各比较 1 次总比较次数 n-1即 O(n)。Q3插入排序是稳定的吗为什么是稳定的。while条件为arr[j] current严格大于相等元素不触发后移current插入到相等元素之后相对顺序不变。如果改为相等元素会被后移current插入到相等元素之前破坏稳定性。Q4为什么 TimSort 和 IntroSort 都用插入排序作为小区间回退三个原因常数因子最小n 16~64 时n²/4 n log n 递归开销写操作少后移代替交换减少内存写自适应有序如果小区间恰好有序插入排序直接 O(n) 完成常见实现错误错误说明修正忘记暂存current后移时覆盖了arr[i]先current arr[i]暂存while条件用相等元素后移破坏稳定性用严格后移方向写反arr[j] arr[j 1]把后面的值覆盖前面应为arr[j 1] arr[j]插入位置算错写成arr[j] current后移后j已减 1应为arr[j 1]外层从 0 开始第一个元素无需排序range(1, n)从第二个开始八、总结插入排序的核心要点扑克牌模型——左手已排序、右手逐张拿牌、从右向左插入后移代替交换——每个逆序对仅 1 次赋值写操作比冒泡少 2/3最好 O(n)——已有序数据一轮扫描完成近乎有序数据接近线性稳定 原地——严格大于比较保证稳定性O(1) 空间工业级排序的回退方案——TimSort 32和 IntroSort 16小区间首选插入排序证明了一个道理算法的实际性能不仅取决于渐近复杂度还取决于常数因子和数据分布。在合适场景下O(n²) 的插入排序可以比 O(n log n) 的快速排序更快。这也是 TimSort、IntroSort 等工业级排序采用混合策略的根本原因——没有一种排序是万能的关键在于根据数据特征选择最合适的工具。专栏导航算法⬅️上一篇堆排序 (Quick Sort) ➡️下一篇1-7-选择排序-SelectionSort如果这篇文章对你有帮助欢迎点赞、收藏、关注支持专栏持续更新