(63)王道数据结构-希尔排序

基本概念

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

基本思想

先将待排序表分割成若干形如L[i, i+d, i+2d,…, i+kd]的“特殊”子表，分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

排序过程

先取一个小于n的步长d1，把表中的全部记录分成d1组，所有距离为d1的倍数的记录放在同一组中，在各组中进行直接插入排序；然后取第二个步长d2<d1，重复上述过程，直到所取到的dt=1，即所有记录已放在同一组中，再进行直接插入排序，由于此时已经具有较好的局部有序性，故可以很快得到最终结果。

代码逻辑

void ShellSort(ElemType A[], int n) {
//对顺序表做希尔插入排序，本算法和直接插入排序相比，做了以下修改：
//1.前后记录位置的增量是dk，不是1
//2.A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    for(dk=n/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<A[j].key; j-=dk) {
                    A[j+dk]=A[j]; //记录后移，查找插入的位置
                }
                A[j+dk]=A[0]; //插入
             }
        }    
    }
}

性能分析

空间复杂度

仅使用了常数个辅助单元，因而空间复杂度为O(1)。

时间复杂度

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

稳定性

当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。