内部排序——希尔插入排序

直接插入排序在时间复杂度上优势不明显。达到O(n²)的水平了，所以需要想办法降低时间复杂度是很有必要的。当记录的排序就是所求的排序时，时间复杂度会大幅下降，为O(n)。这是最理想的状态，当顺序刚好是逆序的时候，时间复杂度最大为O(n²)。所以记录越是有序，时间复杂度越低。这个和快速排序不同，大家都知道快速排序在有序的情况下效果是很差的吧。

现在的问题是，如何使得记录变得有序，这个也是我们求的最后结果。希尔排序是一种很好的选择，它的原理是使得记录大体上有序，虽然不是所有都有序，但是大体上有序也是很加快排序速度的。希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。插入排序的增量是1，而希尔是一个数组决定的。

希尔排序基本思想：

　　先取一个小于n的整数dt作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

所以希尔插入排序和直接插入排序的区别就是增量的区别。

希尔排序的算法如下

//希尔排序算法
void ShellInsert(SqList &L,int dk){
    //对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入相比，作了以下修改
    //    1.前后记录位置的增量是dk，而不是1；
    //    2.r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到。
    for(int i=dk+1;i<=L.length;i++){
        if(LT(L.r[i].key,L.r[i-dk].key)){    //需要将L.r[i]插入有序增量子表
            L.r[0]=L.r[i];                    //暂存L.r[0]
            int j=i-dk;
            for(;j>0&&LT(L.r[0].key,L.r[j].key);j-=dk){
                L.r[j+dk]=L.r[j];            //记录后裔，查找插入位置
            }        
            L.r[j+dk]=L.r[0];                //插入
        }
    }
}

因为希尔排序每次都不是完整的排序，所以需要调用一个调用希尔排序算法的函数，如下

//调用算法
void ShellSort(SqList &L,int dlta[],int t){
    //按照增量序列dlta[0...t-1]对顺序表L作希尔排序
    for(int k=0;k<t;++k){
        ShellInsert(L,dlta[k]);        //一趟增量为dlta[k]的插入排序
    }
}

至于dlta[]和t，这决定于你的数据量，不过最后一个dlta[]数组的值，一定要是1，这样才能保证排序一定正确。

下面给一个完整的例子。

希尔插入排序实例

效率

希尔排序在数据量多的时候，对比直接插入排序才能体现它的价值，实验证明，希尔插入排序的时间复杂度大约为O(n^3/2).

[1] 严蔚敏 吴伟民 《数据结构(C语言版)》 北京：清华大学出版社，1997.4

本文转自 Ron Ngai 博客园博客，原文链接：http://www.cnblogs.com/rond/archive/2012/04/18/2453272.html  ，如需转载请自行联系原作者