数据结构与算法——希尔排序(引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列)

简介: 数据结构与算法——希尔排序(引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列)

希尔排序(by Donald Shell)

引例

给以下序列进行排序:

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

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

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

希尔增量序列

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

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

原始希尔排序

代码(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,...}——
  • 猜想:
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



目录
相关文章
|
13天前
|
算法 安全 大数据
揭秘!Python堆与优先队列:数据结构的秘密武器,让你的代码秒变高效战士!
【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue提供堆与优先队列功能,助你提升算法效率。堆用于快速找大数据集的第K大元素,如示例所示,时间复杂度O(n log k)。PriorityQueue在多线程中智能调度任务,如模拟下载管理器,按优先级处理任务。掌握这些工具,让代码运行更高效!
32 1
|
1月前
|
算法 搜索推荐
数据结构算法--6 希尔排序和计数排序
**希尔排序**是插入排序的改进版,通过分组插入来提高效率。它逐步减少元素间的间隔(增量序列),每次对每个间隔内的元素进行插入排序,最终增量为1时进行最后一次直接插入排序,实现整体接近有序到完全有序的过程。例如,对数组`5, 7, 4, 6, 3, 1, 2, 9, 8`,先以间隔`d=4`排序,然后`d=2`,最后`d=1`,完成排序。计数排序则适用于0到100的数值,通过统计每个数出现次数,创建对应计数数组,再根据计数重建有序数组,时间复杂度为`O(n)`。
|
17天前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
184 1
|
5天前
|
算法 计算机视觉 开发者
燃爆全场!Python并查集:数据结构界的网红,让你的代码炫酷无比!
【7月更文挑战第16天】并查集,Python中的效率明星,处理不相交集合合并与查询。用于社交网络分析、图像处理、图论算法等领域。优雅实现结合路径压缩和按秩合并
8 1
|
11天前
|
机器学习/深度学习 数据采集 算法
Python实现Prophet时间序列数据建模与异常值检测(Prophet算法)项目实战
Python实现Prophet时间序列数据建模与异常值检测(Prophet算法)项目实战
|
29天前
|
存储 JavaScript 前端开发
JavaScript中的数组是核心数据结构,用于存储和操作序列数据
【6月更文挑战第22天】JavaScript中的数组是核心数据结构,用于存储和操作序列数据。创建数组可以使用字面量`[]`或`new Array()`。访问元素通过索引,如`myArray[0]`,修改同样如此。常见方法包括:`push()`添加元素至末尾,`pop()`移除末尾元素,`shift()`移除首元素,`unshift()`添加到开头,`join()`连接为字符串,`slice()`提取子数组,`splice()`进行删除、替换,`indexOf()`查找元素位置,`sort()`排序数组。还有其他如`reverse()`、`concat()`等方法。
112 2
|
1月前
|
存储 算法
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
|
1月前
|
机器学习/深度学习 人工智能 算法
【机器学习】Q-Learning算法:在序列决策问题中的实践与探索
【机器学习】Q-Learning算法:在序列决策问题中的实践与探索
37 0
【机器学习】Q-Learning算法:在序列决策问题中的实践与探索
|
1月前
|
搜索推荐 算法
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
|
13天前
|
存储 算法 安全
解锁Python高级数据结构新姿势:堆与优先队列的实战演练,让你的代码更优雅!
【7月更文挑战第8天】Python的`heapq`模块和`queue.PriorityQueue`提供堆与优先队列功能,用于高效数据管理。堆是完全二叉树,`heapq`实现最小堆,常用于任务调度,如按优先级执行任务。当需要线程安全且更复杂操作时,`queue.PriorityQueue`成为优选,例如在管理网络请求时按优先级处理。这两个数据结构能提升代码效率和可读性。