7.2.3 插入排序之希尔排序

直接插入排序算法适用于基本有序的排序表和数据量不大的排序。基于这两点，1959年D.L.Shell提出了希尔排序，又称为缩小增量排序。

希尔排序的基本思想是：先将待排序表分割成若干个形如L[i,i+d,i+2d,...i+kd]的特殊子表，分别进行直接插入排序，当整个表中已呈“基本有序”时，在对全体记录进行一次直接插入排序。希尔排序的排序过程如下：

先取一个小于n的步长的d1,把表中全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组内，在各组中记性直接插入排序；

然后取第二个步长d2<d1，重复上述过程，直到所取到的dt=1，即所有记录已放在同一组中，再进行直接插入排序，由于此时已经具有较好的局部有序性，故可以很快就得到最终结果。到目前为止，尚未求得一个最好的增量序列，希尔提出的方法是d1=n/2,di+1=[di/2]向下取整，并且最后一个增量等于1.

void ShellSort(ElemType A[],int n){
//对顺序表作希尔插入排序，本算法和直接插入排序相比，作了如下修改：
1、前后记录位置的增量是dk,不是1
2、r[0]只是暂存单元，不是哨兵，当j<0插入位置已到
     for(dk=len/2;dk>=1;dk=dk/2)
         for(i=dk+1;i<=n;i++)
             if(A[i].key<A[i-dk].key){//需将A[i]插入有序增量子表
                   A[0]=A[i];//暂存在A[0]
                   for(j=i-dk;j>0&&A[0].key;j-=dk){
                       A[j+dk]=A[j];//记录后移，查找插入的位置
                   A[j+dk]=A[0];//插入
                   }//if
             }
}

希尔排序算法性能分析： 空间效率：只需要常数个辅助单元，因而空间复杂度为O(1).

时间效率：由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。当n在某个特定范围时，希尔排序的时间复杂度约为O(n^1.3)。在最坏情况下希尔排序的时间复杂度为O(N^2).

稳定性：当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因此，希尔排序是一个不稳定的排序方法。例如，表L{3,2,2}，经过一趟排序后，L{2,2,3}，最终排序序列也是L{2,2,3},显然，2与2的相对次序已经发生了变化。

使用性：希尔排序适用于当线性表为顺序存储的情况。