数据结构与算法——希尔排序（引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列）-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构与算法——希尔排序（引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

引例

希尔增量序列

原始希尔排序

代码（C语言）

时间复杂度

更多增量序列

Hibbard增量序列

Sedgewick增量序列

希尔排序（by Donald Shell）

引例

给以下序列进行排序：

数据结构与算法——希尔排序（引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列）,数据结构,笔记,学习,排序算法,算法

先以5的间隔进行插入排序：

再以3的间隔进行插入排序：

最后再以1为间隔做插入排序，即常规插入排序，得到排序完成的序列：

希尔增量序列

定义增量序列
对每个进行“-间隔”排序（）

注意：“-间隔”有序的序列，在执行“-间隔”排序后，仍然是“-间隔”有序的。

原始希尔排序

$数据结构与算法——希尔排序（引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列）,数据结构,笔记,学习,排序算法,算法$

代码（C语言）

希尔排序在插入排序的基础上进行改进

void Shell_Sort(ElementType A[], int N)
{
    for(D = N / 2; D > 0; D /= 2 )  //原始希尔增量序列
    {
        for(P = D; P < N; P++)   //插入排序
        {
            Tmp = A[P];
            for(i = P; i >= D && A[i-D] > Tmp; i -= D)
                A[i] = A[i-D];
            A[i] = Tmp;
        }
    }
}

时间复杂度

最坏情况：

（表示上界，表示下界，即表示上界也表示下界，为正常值。）

原始希尔序列并不好用，我们举下面的例子：

可以发现，8、4、2间隔的插入排序并没有给序列成功排序，最后还是通过间隔1来完成排序的功能。

有结论：

增量元素不互质，则小增量可能根本不起作用。

更多增量序列

Hibbard增量序列

——相邻元素互质
最坏情况：
猜想：

Sedgewick增量序列

{ 1,5,19,41,109,...}—— $数据结构与算法——希尔排序（引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列）,数据结构,笔记,学习,排序算法,算法$ 或 $数据结构与算法——希尔排序（引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列）,数据结构,笔记,学习,排序算法,算法$
猜想：

void ShellSort( ElementType A[], int N )
{ /* 希尔排序 - 用Sedgewick增量序列 */
     int Si, D, P, i;
     ElementType Tmp;
     /* 这里只列出一小部分增量 */
     int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};
     
     for ( Si=0; Sedgewick[Si]>=N; Si++ ) 
         ; /* 初始的增量Sedgewick[Si]不能超过待排序列长度 */

     for ( D=Sedgewick[Si]; D>0; D=Sedgewick[++Si] )
         for ( P=D; P<N; P++ ) { /* 插入排序*/
             Tmp = A[P];
             for ( i=P; i>=D && A[i-D]>Tmp; i-=D )
                 A[i] = A[i-D];
             A[i] = Tmp;
         }
}

end

学习自：MOOC数据结构——陈越、何钦铭文章来源地址https://www.toymoban.com/news/detail-570323.html

到了这里，关于数据结构与算法——希尔排序（引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！