说明：本篇文章借用勇哥的分析
一、直接插入排序
1、原理
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| -- | tmp | 2 | 5 | 7 | 3 | 6 | 8 | 4 | 1 |
假设数组为A，i为当前元素下标，则A[i]为当前元素的值
- 从下标i=2开始循环，与自己之前的元素比较大小（默认自己之前的序列已经是有序（升序））
- A[i] > A[i-1]，则不需要和i-2,i-3...等比较了，因为i-1已经是前面这些元素中最大的了
- A[i] < A[i-1]，那就循环继续和i-2,i-3...比较，直到A[i] > A[i-?]的时候，跳出循环
所有这些操作，其实都是在一个数组中进行位置的交换，下面来看看代码：
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-insert-1.png" width="558" />
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-insert-2.png" width="558" />
直接插入排序时间复杂度为O(n^2)，在
数据基本有序＋记录数较少的情况下会有较好的表现；
基本有序指： 如果是升序，小的关键字基本在前面，大的基本在后面，不大不小的在中间，像{2,1,3,6,4,7,5,8,9}代表基本有序，而{1,5,9,3,7,8,2,4,6} 9在第三位，2在倒数第三位就不是基本有序了；
二、优化 直接插入排序 至 希尔排序
当年D.L.Shell(希尔排序的发明者)苦想怎么才能让待排序的数据
基本有序＋记录数少，结果脑洞大开，决定把数据多次(分组＋组内插入排序)，那这样每次分组就是实现记录数少的目标，多次分组那就可以慢慢实现整个数据集基本有序
结果弄着弄着就给整出一个时间复杂度更低的排序算法，嘿嘿～
1、多次分组=>基本有序？如何实现？很重要！
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-xier-1.png" width="400" />
看到上图，相信各位就能体会那句“多次分组就可以慢慢实现整个数据集基本有序”了！
请思考！如果就分组一次，那组内有序后，还要
组与组之间有序，否则不能做到整个数据集基本有序！！（所以应该多次跳跃式分组）
三、希尔排序
- 根据以上的理论，相信大家都明白希尔排序的原理了，我们现在来看看代码：
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-xier-2.png" width="558" />
- 增量序列的最后一个增量值必须是1，也就是increment=1执行完毕后退出循环，也就是说当increment=1的时候是最后一次循环，与直接插入排序等效；
- “增量”到底设置成多少？到目前为止，貌似没有什么特别好的办法，各位就先采用已经有的代码的模式吧，也就是
increment = increment/3+1; - 希尔排序的时间复杂度为 O(n^2/3) < 直接插入排序的O(n^2);
以上两种排序算法的具体代码实现，点击查看...
