数据结构_排序_直接插入+希尔排序

github地址：
https://github.com/arkulo56/thought/blob/master/software/dataStruct/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E6%8E%92%E5%BA%8F_%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%2B%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F.md

数据结构_排序_直接插入排序+希尔排序

其实主要是为了讲述希尔排序，不过插入排序是希尔排序的基础，因此先来讲直接插入排序。

一、直接插入排序

1、原理

下标	0	1	2	3	4	5	6	7	8
--	tmp	2	5	7	3	6	8	4	1

假设数组为A，i为当前元素下标，则A[i]为当前元素的值

1. 从下标i=2开始循环，与自己之前的元素比较大小（默认自己之前的序列已经是有序（升序））
2. A[i] > A[i-1]，则不需要和i-2,i-3...等比较了，因为i-1已经是前面这些元素中最大的了
3. A[i] < A[i-1]，那就循环继续和i-2,i-3...比较，直到A[i] > A[i-?]的时候，跳出循环

所有这些操作，其实都是在一个数组中进行位置的交换，下面来看看代码：

<img src="https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/sort_haxi_1.png" width="600" />

<img src="https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/sort_haxi_2.png" width="600" />

直接插入排序时间复杂度为O(n^2)，在 数据基本有序＋记录数较少 的情况下会有较好的表现

二、优化 直接插入排序 至 希尔排序

当年D.L.Shell(希尔排序的发明者)苦想怎么才能让待排序的数据基本有序＋记录数少，结果脑洞大开，决定把数据多次(分组＋组内插入排序)，那这样每次分组就是实现记录数少的目标，多次分组那就可以慢慢实现整个数据集基本有序

结果弄着弄着就给整出一个时间复杂度更低的排序算法，嘿嘿～

1、多次分组=>基本有序？如何实现？很重要！

<img src="https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/sort_haxi.png" width="400" />

看到上图，相信各位就能体会那句“多次分组就可以慢慢实现整个数据集基本有序”了！

请思考！如果就分组一次，那组内有序后，还要组与组之间有序，否则不能做到整个数据集基本有序！！（所以应该多次跳跃式分组）

三、希尔排序

根据以上的理论，相信大家都明白希尔排序的原理了，我们现在来看看代码：

<img src="https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/sort_haxi_3.png" width="600" />

“增量”到底设置成多少？到目前为止，貌似没有什么特别好的办法，各位就先采用已经有的代码的模式吧