说说算法那些事-希尔排序

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，希尔排序法又称缩小增量法。查看完整代码

1、算法思想：通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。在希尔排序中，增量序列gap的取法必须满足：最后一个步长必须是 1。各组内的排序通常采用直接插入法。由于开始时i的取值较大，每组内记录数较少，所以排序比较快。随着不断增大，每组内的记录数逐步增多，但由于已经按排好序，因此排序速度也比较快

2、算法步骤：(1)、确定增量gas的大小，建议步长选择为N/2并且对步长取半直到步长达到1，此时会把待排序数列分成若干组

(2)、对每个组进行直接插入排序，重复(1) (2)操作，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。

3、图解：

初始时，6个元素数组，在第一趟排序中，我们不妨设 gap1 = N / 2 = 3，即相隔距离为 3 的元素组成一组，可以分为 3组。接下来，按照直接插入排序的方法对每个组进行排序。

在第二趟排序中，再次把 gap 缩小一半，即gap2= gap / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。

4.算法分析：

时间复杂度：平均时间复杂度为O(NlogN)。

空间复杂度：空间复杂度显然为O(1)，仅仅需要一个交换变量。

稳定性：是一种不稳定的排序算法。