希尔排序（及其与直接插入排序的区别）

作者：繁依Fanyi0 | 2024-07-04 12:46:57

踩

希尔排序与直接排序的异同

希尔排序基本思想
基本思想：
　先取一个小于n的整数d₁作为第一个增量，把文件的全部记录分成d₁个组。所有距离为d_l的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d₂<d₁重复上述的分组和排序，直至所取的增量d_t=1(d_t<d_t-l<…<d₂<d₁)，即所有记录放在同一组中进行直接插入排序为止。
　该方法实质上是一种分组插入方法。

Shell排序的算法实现

 1 void ShellSort(ElemType A,int n)
 2 {
 3     int i,j,dk;
 4     for(dk=n/2;dk>=1;dk=dk/2)//控制步长变化，每次步长缩小为原来的1/2,直到1
 5     {
 6         for(i=dk+1;i<n;i++)//前dk个默认为dk组的已序
 7         {
 8             if(A[i].key<A[i-dk].key)
 9             {
10                 A[0]=A[i];//暂存A[i]，这里不是监视哨;
11                 for(j=i-dk;j>0&&A[0].key<A[j].key;j-=dk)//选寻找插入点
12                     A[j+dk]=A[j];//记录后移
13                 A[j]=A[0];
14             }
15         }
16     }
17 }

与直接插入排序比较，希尔排序的改进如下：

1、增加了一个for语句，用于控制步长变化。

2、不设置监视哨，故在寻找插入点的for语句中增加j>0来防止访问越界。

其实，假如去掉这些改进，我们去掉外层的for,然后把dk替换成1，是否发现算法变成了没有设监视哨的直接插入排序？

 1 void InsertSort(SeqList R，int n)
 2 {
 3     int i,j;
 4     for(i=2;i<=n;i++)
 5     {
 6         if(R[i].key<R[i-1].key)
 7         {
 8             R[0]=R[i];
 9             for(j=i-1;R[0].key<R[j].key;--j)
10                 R[j+1]=R[j];
11         }
12     }
13     R[j]=R[0];
14 }

看看直接插入排序

性能分析：

1、空间复杂度O(1)。

2、时间复杂度：由于希尔排序的时间复杂度依赖于增量序列的函数。当n在某个特定的范围时，希尔的时间复杂度约为O(n^1.3)，最坏的情况下希尔排序的时间复杂度为O(n^2);

到目前为止，尚未得出一个最好的增量方法序列，希尔提出的方法是d[1]=n/2,d[t]=d[t-1]/2,其中，增量取整数。

稳定性：不稳定

转载于:https://www.cnblogs.com/houjun/p/4868355.html

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/786902