排序算法--希尔排序

前提：

         排序算法——直接插入排序-CSDN博客

        希尔排序(Shell Sort)是插入排序的一种。是直接插入排序算法的Plus版。该方法又称缩小增量排序，是D.L.Shell于1959年提出。要想学好希尔排序，直接插入排序一定要学好，没学过的，建议一定要先学一学直接插入排序再学希尔

希尔排序算法分析：

        我们在学习了直接插入排序后，知道直接插入排序的时间复杂度为O(n^2),最好的情况下为O(n),即当序列越接近有序，效率越高。就此，希尔大佬提出的思想是这样的：

       我们选定一个整数为增量，将待排序的所有数据按该增量等序分组，然后对每一组进行排序。排好序后，增量减小，继续分组排序，重复上述动作，每次排序让数组接近有序的过程叫做预排序，直到增量缩小为1时，这次排序就是直接插入排序，因为此时基本有序，所以这次的直接插入排序效率极高。

       举个例子：假设这个整数gap=3：

 1、整组数据会被分为间距为3的几组，

2、分别对每个分组进行插入排序：

因此这次预排序排完后的序列是这样的：

这样这次预排序后，每组都变得有序，且大的基本放到了后面

3、一次预排后gap-1=2；

4、gap=1，直接插入排序：

 代码的实现  

这里我们先理解单趟排序：

底层的逻辑实际上就是直接插入排序，但是与直接插入排序算法不同的一点是：其i每次的变化量是gap而不是1。并且，结束条件也应该是最短组的最后一个数，否则有很大的可能要越界。

如果理解了单趟排序，多趟排序就很简单了：

因为单趟排序是排了一组的数据，这里就是控制将所有组进行排序。

那么这次gap=3的排序就结束了。但是我们的最终目标是达到完全有序。所以gap需要逐次减少直到gap=1；

关于希尔排序增量的取值：

      我们一直假设gap=3，这是因为上面的举例是10个数，这时是合适的。但是如果有10000个数呢？如果是100000000000个数呢？我们的gap到底定为多少合适呢？

      从上面的过程来看，如果gap越大，能够将大的数更加快速地挪动到后面，gap越小，挪动的更加频繁，但是更有序。

     增量gap的取法有各种方案。最初shell提出取gap=n/2，后来Knuth提出取gap=n/3+1.目的都是为了最终呢够让gap=1.所以我们的最终代码应该是：

希尔排序的时间复杂度： 

       希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定。