（e）插入排序

官官方信息技术老师·11 页·深入（追求细节与边界）·0 次浏览·3 天前

✦ （e）插入排序信息技术（e）插入排序经验

排序算法稳定排序原地排序边界场景

（e）插入排序

看透插入排序：从直觉到代码实现，拆解比较-后移-插入机制，掌握复杂度与稳定性

按空格/→ 演示下一步

1 / 11 页

全部页面点击任意一页，跳回舞台从这页播放

排序算法稳定排序原地排序边界场景

（e）插入排序

看透插入排序：从直觉到代码实现，拆解比较-后移-插入机制，掌握复杂度与稳定性

1第 1 页 · （e）插入排序

经验

你摸牌时不会把整手牌打乱重排,而是把新牌直接插进手里已排好的序列——插入排序正是建立在这种“经验”之上。

摸牌直觉

新元素到来时,不是重排全部,而是就地插入

局部有序

每一轮结束后,数组左侧始终是有序区

增量生长

排序区每次只向右扩展一个位置

整理手中扑克牌对应 →插入排序

新牌插入手中已排序的位置,而非把整手牌重新洗一遍

2第 2 页 · 经验

构思

你有没有过这种经验——手里攥着一把排好的牌，每抓一张新牌，就从右向左找位置插进去？这就是插入排序的朴素构思。

双区结构

把数组拆成「已排序」和「未排序」两部分，边界从左向右逐步推进

逐个插入

从未排序区取首元素，在已排序区从后往前比较、腾位、插入

稳定 + 在线

相等元素不交换；可流式处理——数据来一个处理一个，无需一次性就绪

自适应复杂度

最坏 O(n²)，但接近有序时退化到 O(n)，输入越有序反而越快

理手中扑克牌对应 →插入排序

已排好的牌 = 已排序区；新抓的牌从右往左找位置插入

3第 3 页 · 构思

对比

前页用"整理扑克牌"理解了插入排序的核心动作。现在把它和选择、冒泡排序摆在一起——三者都是 O(n²)，但干活姿势、稳定性和适用场景差别很大。这一页来做对比。

定义

把每个元素插入到左侧已排序序列的正确位置

vs 选择 / 冒泡

同为 O(n²)，但插入就地插入、选择找最小、冒泡靠交换

三大隐藏属性

稳定 + 自适应（近有序→接近 O(n)） + 在线（流式输入可处理）

典型应用

小规模数组、近乎有序、在线流式、混合排序内层

插扑克牌 vs 挑最小 vs 换位置对应 →三种 O(n²) 排序

三种思路对应三种动作：插入直接落位、选择全局挑最小、冒泡和邻居反复换

4第 4 页 · 对比

实例

对比看完了，现在让它实际跑一次。拿一个具体数组，按时间顺序走完插入排序的每一轮，看每个元素是怎么找到自己位置的。

初始数组

[5,2,4,6,1,3]。把第 1 位视为已排好，从第 2 位起逐个往前插

核心动作

手握当前元素从右往左比；比它大的就往后挪一位；找到位置后再插

逐轮状态

[5]|[2,5]|[2,4,5]|[2,4,5,6]|[1,2,4,5,6]|[1..6]

适用场景

小数组、近乎有序的数据、在线流式数据，以及混合排序的底层段

把新书插进排好的书架对应 →插入排序逐轮插值

排好的左半边⇄已排序前缀；新书⇄当前待插元素；右半整体右挪⇄比它大的往后挪一位

5第 5 页 · 实例

实现

前面看到插入排序思路简单、且对小数组和近有序数据格外划算。这一页落到代码层——核心两件事：循环怎么走，移动怎么做。

双层循环结构

外层 i 从 1 到 n-1，每轮把 a[i] 当作待插入键；内层在已排序区间里找位置

移动代替交换

边比较边把元素后移腾空位，比反复 swap 少约 2/3 的赋值

稳定且原地

相等元素相对次序不变；只需 O(1) 额外空间

哨兵与二分变体

哨兵省去内层边界判断；二分插入把比较降到 O(log n)

整理扑克牌对应 →移动代替交换

摸到一张新牌,把比它大的牌依次往右挪一张让出空位再放下——不是反复两两交换

\text{while } a[j] > \text{key}:\; a[j+1]=a[j];\; j--;\; a[j+1]=\text{key}

6第 6 页 · 实现

性能分析

实现写完了，但写完 ≠ 会用。性能分析就是搞清：它到底多快、最慢多慢、什么时候用才划算。

时间复杂度

最优 O(n)（已排序），平均/最差 O(n²)（逆序最差）

空间复杂度

O(1) 原址，仅用一个临时变量存待插元素

稳定性

寻找插入位置遇 ≥ 即停，相等元素保持原相对次序

自适应与在线

逆序对越少越快；无需预知全部数据，可流式处理

典型应用

小规模（n<50）、近似有序、混合排序（如 Timsort 末段、Quicksort 小数组兜底）

整理已大致归位的书架对应 →插入排序性能

书越接近有序，插入移动越少；完全倒序时每本都要越过前面所有书

7第 7 页 · 性能分析

平均性能

上一页看到：已经有序的输入只要 O(n) 趟扫描，完全逆序则要 O(n²) 次交换。真实数据大多介于两者之间——那「中间地带」究竟有多贵？

平均的定义

假设输入是 n 个元素所有排列中均匀随机的一种

逆序对

满足 i<j 且 a[i]>a[j] 的元素对；插入排序每个逆序对恰好产生一次移动

期望逆序数

随机排列下逆序对期望为 n(n−1)/4，约一半的「对」是错位的

平均时间

比较/移动约 n²/4 次，仍属 Θ(n²)，但常数项约为最坏情形的一半

近有序的甜点

逆序对很少时（如 k 个），性能退化为 O(n+k·n)，趋近最佳情形

洗牌后一张张插回正确位置对应 →随机输入的插入排序

一副牌洗乱后，平均每张牌要穿越约一半的错位牌才能就位

\mathbb{E}[\text{inversions}] = \frac{n(n-1)}{4} \Rightarrow T_{\text{avg}} \approx \frac{n^2}{4}

8第 8 页 · 平均性能

逆序对

上一页我们说插入排序平均需要 O(n²) 次操作——但其实可以数清楚。答案藏在「逆序对」这个概念里。它是分析插入排序时最锋利的一把刻刀。

形式定义

满足 i<j 且 a[i]>a[j] 的下标对 (i,j)，衡量数组偏离有序的程度

与插入排序的关系

插入排序把元素向前挪的次数，正好等于数组中的逆序对数

极端情况

已排序数组为 0；完全逆序时达最大值 n(n−1)/2

平均数量

随机数组平均含 n(n−1)/4 个逆序对，精确对应 O(n²) 的平均代价

排队按高矮顺序站对应 →修复逆序对

前面高、后面矮就是「逆序」，调一次队形就消除一个

\sum_{i<j}\mathbb{1}[a_i>a_j] = \frac{n(n-1)}{4}

9第 9 页 · 逆序对

本节要点

✓插入排序体现「维护循环不变量」的算法思维
✓交换次数恰等于序列中的逆序对数
✓小规模、近有序、增量数据时仍是优选
✓平均与最坏同为O(n²)，天花板由策略决定
✓突破O(n²)需改变思路：分治、堆或随机化

延伸主题：希尔排序：间隔分组改进归并排序求逆序对数插入排序在工程中的实际使用

10第 10 页 · 本节要点

课后思考

先自己想，再看参考答案。每个问题都值得停留几分钟。

1为什么插入排序的交换次数与逆序对数一一对应？逆序对为零时会怎样？

参考答案每交换一次只消除当前这对逆序对，且不会产生新对；零逆序对意味着数组已有序，排序提前结束。

2O(n²) 在大数组上吃亏，但小规模或近乎有序时为何能击败快排？

参考答案小数组常数项小、缓存命中率高；近乎有序时内层循环很快 break，逆序对很少，两类场景都是它的优势。

3若允许用额外空间，能否把插入排序的最坏情况从 O(n²) 降到 O(n log n)？代价是什么？

参考答案可以——用平衡 BST 替线性查找插入位置，O(n log n)，代价是 O(n) 空间与树的常数，这已是另一个问题。

11第 11 页 · 课后思考