介绍
直接插入排序，简称 插入排序，是简单直观的排序算法，核心思路是把数组分成 已排序段 和 未排序段，依次将 未排序段的元素 插入到 已排序段的合适位置，最终让整个数组有序。
例
以数组 [2, 5, 8, 3, 6, 9, 1, 4, 7] 为例（长度是 9），执行插入排序
第 1 轮
- 已排序序列：
2，即：数组第一个元素 - 未排序序列：
5,8,3,6,9,1,4,7
执行内层循环，将 未排序的首元素 5，与 已排序序列 的 元素逐一比较，因为5>2，所以应该将 5 插入到 2 的后面，由于原本顺序就是这样，所以不交换位置
本轮结果：[2, 5, 8, 3, 6, 9, 1, 4, 7]
- 已排序序列：
2,5 - 未排序序列：
8,3,6,9,1,4,7
第 2 轮
- 已排序序列：
2,5 - 未排序序列：
8,3,6,9,1,4,7
执行内层循环，比较 未排序的首元素 8，与 已排序序 的 元素逐一比较
- 与 已排序序列最后1个元素
5比较，因为8>5，所以应该将8插入到5的后面，由于原本顺序就是这样，所以不交换位置
本轮结果：[2,5,8,3,6,9,1,4,7]
- 已排序序列：
2,5,8 - 未排序序列：
3,6,9,1,4,7
第 3 轮
- 已排序序列：
2,5,8 - 未排序序列：
3,6,9,1,4,7
执行内层循环，将 未排序的首元素 3，与 已排序序列 的 元素逐一比较：
- 与 已排序序列最后1个元素
8比较，因为8>3，所以将8往后移动，数组变为[2,5,8,8,6,9,1,4,7] - 与 已排序序列倒数第2个元素
5比较，因为5>3，所以将5往后移动，数组变为[2,5,5,8,6,9,1,4,7] - 与 已排序序列第1个元素
2比较，因为2<3，所以将3插入到2的后面，数组变为[2,3,5,8,6,9,1,4,7]
本轮结果：[2,3,5,8,6,9,1,4,7]
- 已排序序列：
2,3,5,8 - 未排序序列：
6,9,1,4,7
第 4 轮
- 已排序序列：
2,3,5,8 - 未排序序列：
6,9,1,4,7
执行内层循环，将 未排序的首元素 6，与 已排序序列 的 元素逐一比较：
- 与 已排序序列最后1个元素
8比较，因为8>6，所以将8往后移动，数组变为[2,3,5,8,8,9,1,4,7] - 与 已排序序列倒数第2个元素
5比较，因为5<6，所以将6插入到5的后面，数组变为[2,3,5,6,8,9,1,4,7]
本轮结果：[2,3,5,6,8,9,1,4,7]
- 已排序序列：
2,3,5,6,8 - 未排序序列：
9,1,4,7
第 5 轮
过程同上
本轮结果：[2,3,5,6,8,9,1,4,7]
- 已排序区间：
2,3,5,6,8,9 - 未排序区间：
1,4,7
第 6 轮
此时序列：[2,3,5,6,8,9,1,4,7]
- 已排序区间：
2,3,5,6,8,9 - 未排序区间：
1,4,7
执行内层循环，将 未排序的首元素 1，与 已排序序列 的 元素逐一比较：
- 与 已排序序列最后1个元素
9比较，因为9>1，所以将9往后移动，数组变为[2,3,5,6,8,9,9,4,7] - 与 已排序序列倒数第2个元素
8比较，因为8>1，所以将8往后移动，数组变为[2,3,5,6,8,8,9,4,7] - …
- 与 已排序序列第1个元素
2比较，因为2>1，所以将2往后移动，数组变为[2,2,5,6,8,9,1,4,7] - 已遍历完 已排序序列，将
1插入到索引0的空位
本轮结果：[1,2,3,5,6,8,9,4,7]
- 已排序区间：
1,2,3,5,6,8,9 - 未排序区间：
4,7
第 7 轮
过程同上
本轮结果：[1,2,3,4,5,6,8,9,7]
- 已排序区间：
1,2,3,4,5,6,8,9 - 未排序区间：
7
第 8 轮
- 已排序区间：
1,2,3,4,5,6,8,9 - 未排序区间：
7
执行内层循环，将 未排序的首元素 7，与 已排序序列 的 元素逐一比较：
- 与 已排序序列最后1个元素
9比较，因为9>7，所以将9往后移动，数组变为[1,2,3,4,5,6,8,9,9] - 与 已排序序列倒数第2个元素
8比较，因为8>7，所以将8往后移动，数组变为[1,2,3,4,5,6,8,8,9] - 与 已排序序列倒数第3个元素
6比较，因为6<7，所以将7插入到6的后面，数组变为[1,2,3,4,5,6,7,8,9]
本轮结果：[1,2,3,4,5,6,7,8,9]
- 已排序区间：
1,2,3,4,5,6,7,8,9 - 未排序区间：空
最终结果
原数组 [2,5,8,3,6,9,1,4,7] 经过 8 轮 排序后，得到升序有序数组：[1, 2, 3, 4, 5, 6, 7, 8, 9]
时间复杂度
最好
有序时，每轮只需遍历一次，是 O(n)
最坏
全部逆序，按上面例子执行，是 O(n^2)
n 个元素，全部逆序，执行过程：
- 第1轮：循环 n-1 次
- 第2轮：循环 n-2 次
- …
- 第n-2轮：循环 2 次
- 第n-1轮：循环 1 次
规律： (n-1)+(n-2)+(n-3)+...+2+1 = n*(n-1)/2
大O表示法：O(n^2)
平均
O(n^2)
空间复杂度
O(1)
是否稳定性
稳定
应用场景
适用基本有序的情况
此时时间复杂度：O(n)
缺点
效率低
适用场景
适合 小规模数据 排序，或 基本有序的大数据（此时接近 O(n) 效率），是工业界中大规模排序的「子步骤」（比如快速排序的优化：数据量小时切换为直接插入排序）。
题
现需要对一个基本有序的数组进行排序。此时最适宜采用的算法为（）排序算法，时间复杂度为（）。
A、插入
B、快速
C、归并
D、堆
A、O(n)
B、O(nlgn)
C、O(n2)
D、O(n²lgn)
答案
A
A
参考：
https://blog.csdn.net/qq_43238568/article/details/130786315