1、插入排序的基本思想
每一趟将一个待排序的记录，按照其关键字值得大小插入到已排序的部分文件中的适当位置上，直到全部插入完成。
2、插入排序的主要方法有
直接插入排序、希尔排序、折半插入排序
3、希尔排序的基本思想
希尔排序（shell sort）这个排序方法又称为缩小增量排序，是1959年D·L·Shell提出来的。该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。
4、希尔排序示例图
我们来看下希尔排序的图解步骤，在此我们选择增量gap = length / 2，缩小增量继续以gap = gap / 2的方式，这种增量选择我们可以用一个序列来表示，{n/2， (n/2)/2， …1}，称为增量序列。
5、希尔排序的核心代码
测试结果：
6、希尔排序算法的性能
时间复杂度
对希尔排序的时间复杂度分析很困难，在特定情况下可以准确的估算排序码的比较次数和元素移动的
次数，但要想弄清楚排序码比较次数和元素移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到，有几种接近的答案：O(nlog2为底n)或O(n^1.25)。
空间复杂度
由希尔排序算法可知，我们在排序过程中，需要一个增量元素，所以空间复杂度为 1 。
算法稳定性
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。