一篇文章讲透排序算法之希尔排序

希尔排序是对插入排序的优化,如果你不了解插入排序的话,可以先阅读这篇文章:插入排序

目录

1.插入排序的问题

2.希尔排序的思路

3.希尔排序的实现

4.希尔排序的优化

5.希尔排序的时间复杂度


1.插入排序的问题

如果用插入排序对一个逆序有序的数组排序时,时间复杂度为O(n^2),此时效率最低。

如果用插入排序对一个顺序有序的数组排序时,时间复杂度为O(n),此时效率最高。

我们发现,被排序的对象越接近有序,插入排序的效率越高,这时希尔就有了一个想法:如果可以将数组变得接近有序后再用插入排序呢?

2.希尔排序的思路

希尔排序是对插入排序的优化,它的思路是先选定一个整数作为增量,这里我们以gap(间隔)表示,将间隔为gap的数据分为一组,这样就可以分出gap组以gap为公差的等差数列的数据组。之后将这些数据组排序(把每组数据排序),之后将gap缩小,继续分组并进行排序,重复上述动作,直到gap缩小至1,此时排完了之后刚好有序。

为了让数组更接近有序的排序称为预排序,而最后一次排序是直接插入排序,而由于前面的操作使数据变得接近有序,因此最后一次直接插入排序需要移动的数据很少,效率便很高了。

下面我们来实现希尔排序。

现在我们给定如下数组,并以3为gap,可将数组根据颜色分为3组以3为公差的等差数列。

之后我们对这三组数据进行插入排序

之后我们将间隔缩小, 以2为间隔,我们就可以分出两组以2为公差的等差数列。

这里也并不一定要只减少1,减少多少看我们想减少多少。

现在我们完成第二次排序

现在我们的数组已经非常接近有序,我们最后再以1为间隔,得到一组以1为间隔的等差数列,再完成最后一次排序,也就是直接插入排序,即可使得我们的数组有序。

3.希尔排序的实现

现在我们根据我们的思路来逐步实现希尔排序

第一步:以3为间隔,排序第一组绿色的

在已经学习了插入排序的基础上,我们来实现一下排序绿色

//代码中的n代表数组长度,后面的代码不再解释。
int gap = 3;
//n-gap后的数据为最后一组数据,而当i等于我们的前一组数据时
//排序的就是最后一组数据,因此结束条件为i<n-gap
for (int i = 0; i < n - gap; i += gap)
{int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;
}

第二步:进行第一次排序  

由于我们先前已经实现了排序绿色的,而排序蓝色的和排序黄色的不过是起始位置不同,因此我们再嵌套一层循环即可。

for (int j = 0; i < gap; j++)
{int gap = 3;//n-gap后的数据为最后一组数据,而当i等于我们的前一组数据时//排序的就是最后一组数据,因此结束条件为i<n-gapfor (int i = j; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}
}

现在我们已经完成了第一次排序,那么后面的排序我们控制gap即可

for (int gap = 3; gap > 0; gap--)
{for (int j = 0; i < gap; j++){for (int i = j; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

这时我们发现我们的代码达到了惊人的四层循环...这段代码未免有些过于恐怖...

那我们有没有什么办法优化这段代码呢? 

4.希尔排序的优化

这时有一位大佬给出了这么一个解决方法:

我们不再一次比较一个数据组,

而是先比较第一个数据组的第一个数据和第二个数据,

然后比较第二个数据组的第一个数据和第二个数据,

之后比较第三个数据组的第一个数据和第二个数据,

然后比较第二个数据组的第二个数据和第三个数据,

这么一直比较下去,就可以完成我们第一次预排序的效果。

如下图所示,相同颜色的线表示比较的数据。

代码如下所示: 

int gap = 3
for (int i = 0; i < n - gap; i++)
{int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;
}

现在我们已经完成了第一趟的排序,接下来我们控制gap即可。

int gap = 3;
while (gap > 0)
{for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}gap--;
}

现在这段代码看起来就舒服多了。但是我们的gap就一定每次都减1吗?

我们之前说过,预排序是为了让数组更加有序,我们只要能够让数组更加有序就可以了,没有必要每次让gap减1,gap太大了反而会有一些副作用。

这时有一位大佬写了这么一个希尔排序: 

int gap = n;
while (gap > 0)
{gap /= 2;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}
}

这里的第一趟循环以二分之数组长度为间隔,后续的循环每次都除以2。

到了最后一次循环之时,gap要么等于2,要么等于3;而它们除2都等于1。这样就保证了最后一次循环是直接插入排序,可谓是相当完美了。

现在我们将其封装在函数体内,完成最终版的希尔排序

void InsertSort(int* a, int n)
{int gap = n;while (gap > 0){gap /= 2;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

5.希尔排序的时间复杂度

我们发现我们最终版的希尔排序也拥有三层循环,于是乎我们大家就对希尔排序的效率产生了疑问.但是利用我们现有数学能力无法计算出希尔排序的时间复杂度,只能给出一个大致范围

下面给出严蔚敏教授数据结构书中的相关论述:

在这里也可以给大家大概画一下图,由于每次排序都会对后续的排序产生影响,因此我们后续的排序移动的数据会越来越少,因此效率还是比较高的。 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/331139.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

单片机设计注意事项

1.电源线可以30mil走线&#xff0c;信号线可以6mil走线 2.LDO推荐 SGM2019-3.3,RT9013,RT9193,1117-3.3V。 3.单片机VCC要充分滤波后再供电&#xff0c;可以接0.1uf的电容 4.晶振附件不要走其他元件&#xff0c;且放置完单片机后就放置晶振&#xff0c;晶振靠近X1,X2。

SpringBoot高级原理详解

文章目录 1 SpringBoot自动化配置原理01-SpringBoot2高级-starter依赖管理机制02-SpringBoot2高级-自动化配置初体验03-SpringBoot2高级-底层原理-Configuration配置注解04-SpringBoot2高级-底层原理-Import注解使用105-SpringBoot2高级-底层原理-Import注解使用206-SpringBoot…

微信小程序上线必备:SSL证书申请以及安装

一、认识ssl证书 1、ssl证书是什么&#xff1f; SSL证书&#xff0c;全称Secure Socket Layer Certificate&#xff0c;是一种数字证书&#xff0c;它遵循SSL&#xff08;现在通常指TLS&#xff0c;Transport Layer Security&#xff09;协议标准&#xff0c;用于在客户端&…

打造AI虚拟伴侣 - 优化方案

第一部分:框架优化概述 1、精确定位: 构建一个高度灵活且用户友好的平台,旨在通过无缝集成多种大型语言模型(LLMs)后端,为用户创造沉浸式的角色交互体验。不仅适配电脑端,还特别优化移动端体验,满足二次元AI虚拟伴侣市场的特定需求。 2、核心功能强化: 增强后端兼容…

k8s——Pod详解

一、Pod基础概念 1.1 Pod定义 Pod是kubernetes中最小的资源管理组件&#xff0c;Pod也是最小化运行容器化应用的资源对象。一个Pod代表着集群中运行的一个进程。kubernetes中其他大多数组件都是围绕着Pod来进行支撑和扩展Pod功能的&#xff0c;例如&#xff0c;用于管理Pod运行…

华为云服务培训

一、存储类服务实践 是什么&#xff1a; 云硬盘( Elastic Volume Service )是一种为 ECS&#xff08;弹性云服务器&#xff09;、BMS&#xff08;裸金属服务器&#xff09; 等计算服务提供持久性存储的服务。 作用&#xff1a; 它通过数据冗余和缓存加速等多项技术&#xf…

【C++高阶(一)】继承

目录 一、继承的概念 1.继承的基本概念 2.继承的定义和语法 3.继承基类成员访问方式的变化 ​编辑 4.总结 二、基类和派生类对象赋值转换 三、继承中的作用域 四、派生类的默认成员函数 1.派生类中的默认构造函数 2.派生类中的拷贝构造函数 3.派生类中的移动构造函数…

[国产大模型简单使用介绍] 开源与免费API

个人博客:Sekyoro的博客小屋 个人网站:Proanimer的个人网站 随着大模型技术蓬勃发展和开源社区越来越活跃,国内的大模型也如雨后春笋一般.这时,一些就会问了,有了llama3,Mistral还有Gemma等等,国外大厂接连发力,一些开源社区也会有一些不错的模型,国内怎么比?对一个人使用,oll…

02.爬虫---HTTP基本原理

02.HTTP基本原理 1.URI 和 URL 的区别2.HTTP 和 HTTPS 的区别3.请求过程 1.URI 和 URL 的区别 URL&#xff08;Uniform Resource Locator&#xff09;即-统一资源定位符 URL是用来定位和访问互联网上资源的独特标识&#xff0c;它包括了资源的位置&#xff08;如IP地址或域名&a…

node.js —— 解读http模块

目录 http模块&#xff1a; http模块的引入&#xff1a; 创建web服务器的基本步骤&#xff1a; web服务器的一些基本属性&#xff1a; 上述知识汇总案例&#xff1a; http模块&#xff1a; http模块的引入&#xff1a; const http require (http) 创建web服务器的基本步骤…

记录docker ps查找指定容器的几个命令

1.docker ps | grep registry 查询包含registry的容器 2.docker ps | grep -E "reigistry\s" 开启正则匹配模式&#xff0c;匹配registry后面为空格的容器&#xff0c;若是匹配一整行可以这样写docker ps | grep -E "^([0-9a-f]{12})\sregistry\s.*" 这…

第八节 条件装配案例讲解

一、条件装配的作用是什么 条件装配是 Spring 框架中一个强大的特性&#xff0c;使得开发者能够创建更加灵活和可维护的应用程序。在 Spring Boot 中&#xff0c;这个特性被大量用于自动配置&#xff0c;极大地简化了基于 Spring 的应用开发。 二、条件装配注解 <dependen…

Android-自定义三角形评分控件

效果图 序言 在移动应用开发中&#xff0c;显示数据的方式多种多样&#xff0c;直观的图形展示常常能带给用户更好的体验。本文将介绍如何使用Flutter创建一个自定义三角形纬度评分控件&#xff0c;该控件可以通过动画展示评分的变化&#xff0c;让应用界面更加生动。 实现思…

Vue3实战easypan(六):回收站+设置

一、回收站 src/views/recycle/Recycle.vue <template><!-- 上方两个按钮 --><div class"top"><el-button type"success" :disabled"selectFileIdList.length 0" click"revertBatch"><span class"ic…

[保姆式教程]使用目标检测模型YOLO V8 OBB进行旋转目标的检测:训练自己的数据集(基于卫星和无人机的农业大棚数据集)

最近需要做基于卫星和无人机的农业大棚的旋转目标检测&#xff0c;基于YOLO V8 OBB的原因是因为尝试的第二个模型就是YOLO V8&#xff0c;后面会基于YOLO V9模型做农业大棚的旋转目标检测。YOLO V9目前还不能进行旋转目标的检测&#xff0c;需要修改代码 PS:欢迎大家分享农业大…

Plotly库利用滑块创建数据可视化

使用了Plotly库来创建一个数据可视化图表&#xff0c;并使用滑块来控制显示哪些数据 import plotly.graph_objects as go from plotly.subplots import make_subplots# 示例数据 x [1, 2, 3, 4, 5] y1 [1, 2, 3, 4, 5] y2 [5, 4, 3, 2, 1] y3 [2, 3, 1, 5, 4]# 创建子图 f…

12306技术内幕

公司内部做的一次技术分享 文章目录 12306的成就12306系统特点12306系统难点解决思路产品角度技术角度余票库存的表如何设计&#xff1f; 抢票软件推荐巨人的肩膀 对于未公开的技术部分&#xff0c;只能结合已公开的信息&#xff0c;去做大胆的猜想。 本文提到的一些解决方案&…

【车载开发系列】Autosar中的VFB

【车载开发系列】Autosar中的VFB # 【车载开发系列】Autosar中的VFB 【车载开发系列】Autosar中的VFB一. 什么是VFB二. VFB的优点与缺点1&#xff09;VFB的缺点2&#xff09;VFB的好处 三. RTE与VFB之间关系四. 总线架构模式 一. 什么是VFB Virtual Functional Bus。它就是虚拟…

Python函数、类和方法

大家好&#xff0c;当涉及到编写可维护、可扩展且易于测试的代码时&#xff0c;Python提供了一些强大的工具和概念&#xff0c;其中包括函数、类和方法。这些是Python编程中的核心要素&#xff0c;可以帮助我们构建高效的测试框架和可靠的测试用例。 本文将探讨Python中的函数、…

Vue3实战笔记(43)—Vue3组合式API下封装可复用ECharts图表组件

文章目录 前言一、封装echart图标钩子二、使用步骤总结 前言 接上文&#xff0c;已经安装好了ECharts&#xff0c;开始封装组件方便使用。 一、封装echart图标钩子 首先应用我们之前学习的钩子方式&#xff0c;在hooks目录下创建一个名为 useECharts.js 的文件&#xff0c;用…