插入类

直接插入排序

思路

1. 将数组划分为两个部分，前面一部分是有序、后面一部分是无序
2. 每趟将无序序列中的一个元素，插入到有序序列当中。插入过程中伴随着元素的移动

1. 【评价】时间主要浪费在交换上
2. 【适用】适合初始序列较有序的情况
3. 【最坏】\(O(n^2)\)整个序列是逆序的
4. 【最好】\(O(n)\)序列已经有序，需要比较n-1次，无需交换元素
5. 【平均\(】\)O(n^2)
6. 【空间】\(O(1)\)
7. 【稳定性】稳定

折半插入排序

直接插入法的优化，在有序序列中采用，折半查找的方法，来定位每次的插入位置

1. 【评价】比较次数与初始序列无光，每次都要折半，比较次数是一定的；而关键字移动次数与直接插入排序是一样的
2. 【适用】适合关键字较多的场景
3. 【最坏】\(O(n^2)\)
4. 【最好】\(O(nlog_2n)\)
5. 【平均】\(O(n^2)\)
6. 【空间】\(O(1)\)

希尔排序

希尔排序，又名缩小增量排序。

【优化】用增量来划分子序列，在每个子序列中进行插入排序

【增量选取规则】

1. 增量序列的最后一个值一定取1
2. 增量序列中的值应尽量没有除1之外的公因子

【时间复杂度】与增量选取有关

1. 每次将增量除以2并向下取整\(O(n^2)\)
2. 增量\(2^k+1\)、65、33、17、9、5、3、1，即\(O(n^{1.5})\)

【空间】\(O(1)\)

【稳定性】不稳定