希尔排序法特点

·一次移动，移动位置较大，跳跃式地接近排序后的最终位置

·最后一次只需要少量移动

·增量序列必须递减的，最后一个必须是1

·增量序列应该是互质的

1.4希尔排序算法

主程序：

子函数：

上面代码中i=0处存储了哨兵，所以真正的序列是从1开始的，因此i是从增量+1开始的。

在希尔排序的理解时，我们倾向于对于每一个分组，逐组进行处理，但在代码实现中，我们可以不用这么按部就班地处理完一组再调转回来处理下一组（这样还得加个for循环去处理分组）。比如[5,4,3,2,1,0] ，首次增量设gap=length/2=3,则为3组[5,2] [4,1] [3,0]，实现时不用循环按组处理，我们可以从第gap个元素开始，逐个跨组处理。同时，在插入数据时，可以采用元素交换法寻找最终位置，也可以采用数组元素移动法寻觅。

在写代码时，我们从下标为第一个增量值处开始，进行跨组处理，而不是一组一组处理，如果要一组一组处理，则需要额外增加一个for循环，这样增加了算法的复杂度。例如，初始序列如下（无哨兵，故初始序列的下标从0开始，则i=增量）：

若取增量为4，则分组结果为：{5，1，2}、{3，6}、{7，4}，{9，8}按照理解希尔排序的思路，我们应该先将{5，1，2}排好序后，再排{3，6}……但是这样做我们需要给整个程序加一个用于分组处理的for循环，增加了算法复杂度。因此我们这样考虑：从下标4处开始，减一个增量，先将这2个数排好序，然后继续往后跨组移动排序，接下来下标为5，那么我们减一个增量，继续排序……这样我们一直进行到整个序列的最后一个元素，此时我们就已经将所有的数排好序了。那么此时或许有一个疑问，这样做每次只交换了2个数，可是对于分组中有大于3个数的组，程序是怎么解决的呢？

比如说{5，1，2}，第一次时我们对5和1进行了排序，接下来我们跨组依次往后排序，此时到了2这个元素，那么我们用2减去增量，又到了5那个位置，将这2个数排好序，然后我们利用for循环再继续减增量，对这2个数再继续排序，，一直到减增量后的值小于0为终止条件，说明此时2以及2之前的5和1，这3个数已经彻底排好了序，如果说序列再足够长，等到有一个数减去增量后又等于2，那么再利用for循环对这4个数再依次进行排序。

程序如下：

1.5希尔排序算法分析

希尔排序算法效率增量序列的取值有关：

·Hibbard增量序列

·