当前位置: 首页 > news >正文

漫画:什么是希尔排序算法?

希尔排序(ShellSort)是以它的发明者Donald Shell名字命名的,希尔排序是插入排序的改进版,实现简单,对于中等规模数据的性能表现还不错

一、排序思想

前情回顾:漫画:什么是插入排序算法?(对插入排序不熟悉的强烈建议先阅读此文)

一天,一尘拿着扑克自己在那玩,刚被师傅看见了

image-20230212233900153

image-20230212234015914

image-20230212234029557

image-20230212234220722

数据有序程度越高,越高效(移动少)

image-20230212234235424

image-20230212234248201

image-20230212234315324

image-20230212235149102

image-20230212235213166

首先它把较大的数据集合分割成若干个小组(逻辑上分组),然后对每一个小组分别进行插入排序,此时,插入排序所作用的数据量比较小(每一个小组),插入的效率比较高

image-20230213173319545

**注意:**下面有颜色的是逻辑上的分组,并没有实际地进行分组操作,在数组中的位置还是原来的样子,只是将他们看成这么几个分组(逻辑上分组)

可以看出,他是按下标相隔距离为4分的组,也就是说把下标相差4的分到一组,比如这个例子中a[0]与a[4]是一组、a[1]与a[5]是一组…,这里的差值(距离)被称为增量

image-20230213173338588

每个分组进行插入排序后,各个分组就变成了有序的了(整体不一定有序)

image-20230213173357754

此时,整个数组变的部分有序了(有序程度可能不是很高)

image-20230213173412793

然后缩小增量为上个增量的一半:2,继续划分分组,此时,每个分组元素个数多了,但是,数组变的部分有序了,插入排序效率同样比较高

image-20230213173428248

同理对每个分组进行排序(插入排序),使其每个分组各自有序

image-20230213173442361image-20230213173457621

最后设置增量为上一个增量的一半:1,则整个数组被分为一组,此时,整个数组已经接近有序了,插入排序效率高

image-20230213173512254

同理,对这仅有的一组数据进行排序,排序完成

image-20230213173524661

image-20230213173538322

二、排序代码

image-20230213173551784

对于已经熟悉插入排序的一尘来说这并不是什么难事,很快,一尘写出了希尔排序的代码

image-20230213173613549

image-20230213173625610

image-20230213173640202

随后一尘写出了插入arr[i]到所在组正确位置的代码(insertI

insertI 和直接插入排序里的插入代码几乎完全一样

image-20230213173700084

image-20230213173713659

三、时间复杂度

接下来又是分析时间复杂度吧,一尘心里想

image-20230213173724390

image-20230213173735053

image-20230213173748345

希尔排序的复杂度和增量序列是相关的

{1,2,4,8,…}这种序列并不是很好的增量序列,使用这个增量序列的时间复杂度(最坏情形)是O(n^2)

Hibbard提出了另一个增量序列{1,3,7,…,2k-1},这种序列的时间复杂度(最坏情形)为O(n1.5)

Sedgewick提出了几种增量序列,其最坏情形运行时间为O(n^1.3),其中最好的一个序列是{1,5,19,41,109,…}

对不同增量的复杂度感性趣可以参考《数据结构与算法分析》一书或其他相关论文

image-20210425143358859

四、稳定性

image-20230213173811009

image-20230213173824488

image-20230213173855323

关于稳定性可看:冒泡排序

说完,一尘继续玩起了扑克

image-20230213173908600

更多排序算法文章

1. 漫画:什么是冒泡排序算法?

2. 漫画:什么是选择排序算法?

3. 漫画:什么是插入排序算法?

4. 漫画:什么是希尔排序算法?

5. 漫画:什么是归并排序算法?

6. 漫画:什么是快速排序算法?

7. 漫画:什么是堆排序算法?

8. 漫画:什么是基数排序算法?

9. 漫画:什么是外部排序?

10. 什么是计数排序?

11. 十大排序算法极简汇总篇

推荐阅读

下载破 2w+,在校生必看,《程序员内功修炼》第二版出炉

从双非到大厂,帅地写了一本原创PDF送给大家

一个帮你拿offer的校招网站

算法刷题路线(系统+全面)

作者简介:我是帅地,校招拿到过不少大厂offer,毕业去了腾讯研发岗,毕业半年整到人生第一个 100 万,目前专注于写大学规划 + 校招求职相关的内容,著有个人原创网站 PlayOffer。

http://www.lryc.cn/news/40612.html

相关文章:

  • 问卷工具选择要看哪些方面?
  • Qt之QPainter绘制多个矩形/圆形(含源码+注释)
  • 介绍两款红队常用的信息收集组合工具
  • 类ChatGPT国产大模型ChatGLM-6B,单卡即可运行
  • vue的diff算法?
  • C++ | 对比inline内联函数和宏的不同点
  • 面试官问 : ArrayList 不是线程安全的,为什么 ?(看完这篇,以后反问面试官)
  • Linux串口应用编程
  • java程序员学前端-HTML篇
  • 【云原生|Docker】03-docker的基础操作
  • vue2+高德地图web端开发使用
  • 01背包问题c++
  • ZYNQ硬件调试-------day2
  • JavaScript中Promise的简单使用及其原理
  • SpringBoot RabbitMQ 延时队列取消订单【SpringBoot系列14】
  • 【论文阅读 WWW‘23】Zero-shot Clarifying Question Generation for Conversational Search
  • ouc 网络安全实验 格式化字符串漏洞
  • PMSM矢量控制笔记(1.1)——电机的机械结构与运行原理
  • 2022年全国职业院校技能大赛(中职组)网络安全竞赛试题——中间人攻击渗透测试解析(详细)
  • MySQL必知必会 | 安全、维护、性能
  • MaaS Model as a Service 模型即服务
  • 【编程基础】027.C语言中函数在解题中的应用(三)
  • echart图表之highcharts
  • 关于.Net和Java的看法——我见过最牛的一个小实习生经历
  • 基于springboot+vue的“智慧食堂”程序设计实现【毕业论文,源码】
  • 学计算机选择什么编程语言好一些?
  • 持续集成 在 Linux 上搭建 Jenkins,自动构建接口测试
  • MySQL学习笔记(总结)
  • Android开发 Layout布局 ScrollView
  • 手撕数据结构与算法——树(三指针描述一棵树)