数据结构----插入排序
一、基本思想
插入排序的核心思想：把数组分为「有序区」和「无序区」。初始状态：
第 1 个元素天然为有序区；
后面所有元素为无序区。
每一趟排序：从无序区取出第一个元素，向前扫描有序区，按照大小顺序，插入到有序区的合适位置；重复操作，直到整个数组全部转为有序区。特点：逐个插入、逐步有序，稳定排序、就地排序。
二、直接插入排序
1. 算法原理
数组下标从 i = 1 开始（默认 a [0] 有序）；
暂存当前待插入元素 temp = a[i]；
从有序区末尾 j = i-1 向前遍历；
若 a[j] > temp，向后移位腾出空位；
直到找到比 temp 小的位置，将 temp 插入；
i++，进入下一趟。
2. 完整代码
void InsertSort(int a[], int n){int i, j, temp;for(i = 1; i < n; i++){temp = a[i]; // 待插入元素// 向前移位for(j = i - 1; j >= 0 && a[j] > temp; j--){a[j + 1] = a[j];}a[j + 1] = temp; // 插入正确位置}}
3. 性能分析
最好情况（数组已有序）：O(n)
最坏 / 平均情况：O(n 2 )
空间复杂度：O(1) 原地排序
稳定性：稳定（相等元素不交换相对位置）
三、折半插入排序（二分插入排序）
1. 改进思路
直接插入排序中，向前查找插入位置是顺序查找效率低；利用有序区已有序，改用折半查找快速定位插入点，减少比较次数。 仅减少比较次数，元素移动次数不变。
2. 核心流程
折半查找，快速确定待插入位置 low；
将插入位置后所有元素统一后移；
放入待插入元素。
3. 性能
比较次数：O(nlog 2 n)
移动次数：仍为 O(n 2 )
整体时间复杂度：O(n 2)稳定、原地排序
四、希尔排序（缩小增量插入排序）
1. 改进思想
直接插入在数据逆序、乱序时效率极差；希尔排序：分组 + 远距离插入先取较大增量，将数组分组，组内直接插入排序；逐步缩小增量，直至增量为 1，退化为普通插入排序。
2. 原理
设定增量 d，按下标间隔 d 分组；每组内部做直接插入排序；不断缩小 d，重复分组排序；d=1 整体有序。
3. 关键性质
时间复杂度：约 O(n 1.3 )
稳定性：不稳定（远距离交换会打乱相等元素顺序）
属于插入类排序，是直接插入的优化版本
五、插入排序共同特点总结
算法逻辑简单，易于理解、代码短；
适合数据量小、基本接近有序的序列；
直接插入、折半插入：稳定；希尔排序：不稳定；
都是就地排序，额外空间仅常数级；
数据越有序，插入排序越快。