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

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

现在的问题是,如何使得记录变得有序,这个也是我们求的最后结果。希尔排序是一种很好的选择,它的原理是使得记录大体上有序,虽然不是所有都有序,但是大体上有序也是很加快排序速度的。希尔排序(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,这样才能保证排序一定正确。

下面给一个完整的例子

希尔插入排序实例
 1 // TestShellInserSort.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include "stdio.h"
 6 
 7 //数据
 8 #define MAXSIZE 20
 9 typedef int KeyType;
10 typedef int InfoType;
11 int DLTA[]={3,2,1};
12 typedef struct{
13     KeyType key;            //关键字项
14     InfoType otherinfo;        //其他数据项
15 }RedType;                    //记录类型
16 typedef struct{
17     RedType r[MAXSIZE+1];    //r[0]闲置或用作哨兵单元
18     int length;                //顺序表长度
19 }SqList;                    //顺序表类型
20 
21 
22 bool LT(int x,int y){
23     if(x<y)
24         return true;
25     else
26         return false;
27 }
28 //希尔排序算法
29 void ShellInsert(SqList &L,int dk){
30     //对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入相比,作了以下修改
31     //    1.前后记录位置的增量是dk,而不是1;
32     //    2.r[0]只是暂存单元,不是哨兵。当j<=0时,插入位置已找到。
33     for(int i=dk+1;i<=L.length;i++){
34         if(LT(L.r[i].key,L.r[i-dk].key)){    //需要将L.r[i]插入有序增量子表
35             L.r[0]=L.r[i];                    //暂存L.r[0]
36             int j=i-dk;
37             for(;j>0&&LT(L.r[0].key,L.r[j].key);j-=dk){
38                 L.r[j+dk]=L.r[j];            //记录后裔,查找插入位置
39             }        
40             L.r[j+dk]=L.r[0];                //插入
41         }
42     }
43 }
44 
45 //调用算法
46 void ShellSort(SqList &L,int dlta[],int t){
47     //按照增量序列dlta[0...t-1]对顺序表L作希尔排序
48     for(int k=0;k<t;++k){
49         ShellInsert(L,dlta[k]);        //一趟增量为dlta[k]的插入排序
50     }
51 }
52 
53 int _tmain(int argc, _TCHAR* argv[])
54 {
55     SqList L;
56     scanf("%d",&L.length);
57     for(int i=1;i<=L.length;i++){
58         scanf("%d",&L.r[i].key);
59     }
60     ShellSort(L,DLTA,3);
61     for(int i=1;i<=L.length;i++){
62         printf("%d\t",L.r[i].key);
63     }
64     return 0;
65 }

效率

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

 

相关资料
内部排序——直接插入排序
 
参考资料

 

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

 

原文地址:https://www.cnblogs.com/rond/p/2453272.html