【数据结构--八大排序】之希尔排序

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 :阿然成长日记 👈点击可跳转
📆 个人专栏: 🔹数据结构与算法🔹C语言进阶
🚩 不能则学,不知则问,耻于问人,决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍
文章目录
- 一、希尔定义:
- 二、希尔排序原理
- 三、希尔排序原理图
- 1.gap为3:
- 2.gap为2:
- 3.gap为1:
- 四、细节剖析
- 第1步:`i=0`; a[tmp] > a[end]不做交换
- 第2步:`i=1`; a[tmp] > a[end]不做交换
- 第3步:`i=2`; a[tmp] < a[end]交换
- 第3步:`i=2`; a[tmp] > a[end] 不交换
- 第5步:`i=3`; a[tmp] > a[end]不交换
- 第6步:`i=3`; a[tmp] > a[end]不交换
- 停止
- 五、代码展示:
- 六、测试结果
- 七、 时间复杂度

一、希尔定义:
希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法,其也是一种特殊的插入排序,即将简单的插入排序进行改进后的一个更加高效的版本,也称 缩小增量排序
二、希尔排序原理
希尔排序的思路是,它通过将待排序的数组分割成多个子序列来进行排序。然后逐步缩小子序列的规模,最终进行一次插入排序,从而实现将整个数组排序的目的,当被排序的对象越接近有序时,插入排序的效率越高。希尔排序利用这一特点,通过将数组变得接近有序,从而提高插入排序的效率。
三、希尔排序原理图
gap值的计算公式:gap=n/3+1;
1.gap为3:

三组分别进行排序,将较小值换到左边。

是不是看起来就有序多了。继续缩小gap的值。
2.gap为2:

第一组:1,8,7
第二组:4,5,9
对两组进行排序:

看起来更加有序了。继续缩小gap的值。
3.gap为1:
当gap=1时,就相当于插入排序;

排序后:就是一个有序数组了。

插入排序
四、细节剖析
我们分析一下gap=2时的具体排序过程:
注:图中的 tmp>end 指的是 a[tmp] 和 a[end]
第1步:i=0; a[tmp] > a[end]不做交换

i++;
第2步:i=1; a[tmp] > a[end]不做交换

i++;
第3步:i=2; a[tmp] < a[end]交换

在这里就会有一些变化了,end在比较交换完后会执行语句 end -= gap ; 所以,end会继续向前移动gap个位置,再次进行比较交换。从而看起来像是0,2,4位置为一组。
第3步:</fonti=2; a[tmp] > a[end] 不交换

i++;
第5步:i=3; a[tmp] > a[end]不交换

第6步:i=3; a[tmp] > a[end]不交换

停止
i++;这里i的值为4,不满足执行条件 n - gap;退到外层循环,gap的值缩小为1;
五、代码展示:
//希尔排序
//从下标0开始,从0+gap步开始,进行插入排序,
//每次选择一个使用遍历向前寻找是否有比他小的记下位置,最后交换
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){//不符合就向后移动,已经保存到tmp中,不用担心被覆盖if (tmp < a[end]){a[end+gap] = a[end];end -=gap;}else{break;}}a[end + gap] = tmp;}}
}
六、测试结果

七、 时间复杂度

相关文章:
【数据结构--八大排序】之希尔排序
💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃个人主页 :阿然成长日记 …...
Linux中生成so库的文件引用另一个so库问题的解决
文章目录 一、问题介绍二、问题解决 一、问题介绍 由于项目需求,需要将一个“编译时引用了另一个动态链接库”的文件(名为main.c),再编译成一个动态链接库。 简要说明一下,即原本的项目代码里,包含main.c…...
EDI是连接原始电子商务和现代电子商务的纽带
EDI是连接原始电子商务和现代电子商务的纽带。 EDI(Electronic Data Interchange,电子数据交换)是一种电子通信技术,用于在不同组织之间以结构化和标准化的方式交换业务文档和数据。EDI使企业能够更有效地与供应商、客户和合作伙…...
星宿UI2.4资源付费变现小程序源码 支持流量主
第一个小程序为星宿小程序 目前是最新版2.0 搭建星宿需要:备用域名 服务器 微信小程序账号 功能:文章展示 文章分类 资源链接下载 轮播图 直接下载附件功能 很多 很适合做资源类分享 源码下载:https://download.csdn.net/download/m0_6604…...
代码随想录训练营二刷第四十六天 | 完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ
代码随想录训练营二刷第四十六天 | 518. 零钱兑换 II 377. 组合总和 Ⅳ 一、518. 零钱兑换 II 题目链接:https://leetcode.cn/problems/coin-change-ii/ 思路:完全背包求组合数,递推公式dp[j]dp[j-nums[i]]。 求组合数,物品在外…...
python安装第三方模块方法
正常情况下安装python第三方模块没啥说的,但是由于python安装模块默认是在外网下载安装,牵扯外网网速问题,所以可以配置下使用国内某镜像源来下载模块 python -m pip install xxxxxxxxxxx 和 pip install xxxxxxxxxx 的命令都可下载安装第三…...
广西小贷公司设立及小贷牌照申请政策要求
关于广西小额贷款公司设立及小贷牌照申请,依据《关于小额贷款公司试点的指导意见》(银监发〔2008〕23号);《广西壮族自治区小额贷款公司管理办法》(桂政发〔2009〕71号);《广西壮族自治区人民政…...
PyTorch应用实战二:实现卷积神经网络进行图像分类
文章目录 实验环境MNIST数据集1.网络结构2.程序实现2.1 导入相关库2.2 构建卷积神经网络模型2.3 加载MNIST数据集2.4 训练模型 附:系列文章 实验环境 python3.6 pytorch1.8.0 import torch print(torch.__version__)1.8.0MNIST数据集 MNIST数字数据集是一组手写…...
面试系列 - Java常见算法(二)
目录 一、排序算法 1、插入排序(Insertion Sort) 2、归并排序(Merge Sort) 二、图形算法 1、最短路径算法(Dijkstra算法、Floyd-Warshall算法) Dijkstra算法 Floyd-Warshall算法 2、最小生成树算法&…...
Cortex-A9 架构
一、Cortex-A 处理器运行模式 Cortex-A9处理器有 9中处理模式,如下表所示: 九种运行模式 在上表中,除了User(USR)用户模式以外,其它8种运行模式都是特权模式,在特权模式下,程序可以访问所有的系统资源。这…...
【C语言】循环结构程序设计(第二部分 -- 习题讲解)
前言:昨天我们学习了C语言中循环结构程序设计,并分析了循环结构的特点和实现方法,有了初步编写循环程序的能力,那么今天我们通过一些例子来进一步掌握循环程序的编写和应用。 💖 博主CSDN主页:卫卫卫的个人主页 💞 &am…...
UGUI交互组件Toggle
一.Toggle对象的构造 Toggle和Button类似,是交互组件的一种 如果所示,通过菜单创建了两个Toggle,Toggle2中更换了背景和标记资源 对象说明Toggle含有Toggle组件的对象Background开关背景Checkmark开关选中标记Label名称文本 二.Toggle组件属…...
亲,您的假期余额已经严重不足了......
引言 大家好,我是亿元程序员,一位有着8年游戏行业经验的主程。 转眼八天长假已经接近尾声了,今天来总结一下大家的假期,聊一聊假期关于学习的看法,并预估一下大家节后大家上班时的样子。 1.放假前一天 即将迎来八天…...
【软件测试】自动化测试selenium(一)
文章目录 一. 什么是自动化测试二. Selenium的介绍1. Selenium是什么2. Selenium的特点3. Selenium的工作原理4. SeleniumJava的环境搭建 一. 什么是自动化测试 自动化测试是指使用软件工具或脚本来执行测试任务的过程,以替代人工进行重复性、繁琐或耗时的测试活动…...
Nginx实现动静分离
一、概述 1、什么是动静分离 动静分离是让动态网站里的动态网页根据一定规则把不变的资源和经常变的资源区分开来,动静资源做好了拆分以后,我们就可以根据静态资源的特点将其做缓存操作,这就是网站静态化处理的核心思路。 动静分离简单的概…...
【算法题】309. 买卖股票的最佳时机含冷冻期
题目: 给定一个整数数组prices,其中第 prices[i] 表示第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): 卖出股票后,你无法在…...
1951-2011年长序列高时空分辨率月尺度温度和降水数据集
简介 长序列高时空分辨率月尺度温度和降水数据集,基于中国及周边国家共1153个气温站点和1202个降水站点数据,利用ANUSPLIN软件插值,重建了1951−2011年中国月值气温和降水量的高空间分辨率0.025(~2.5km)格点数据集&am…...
十天学完基础数据结构-第六天(树(Tree))
树的基本概念 树是一种层次性的数据结构,它由节点组成,这些节点按照层次关系相互连接。树具有以下基本概念: 根节点:树的顶部节点,没有父节点。 子节点:树中每个节点可以有零个或多个子节点。 叶节点&am…...
RobotFramework流程控制(最新版本)
文章目录 一 分支流程1. 关键字:Run Keyword If2. 关键字:IF/ELSE3. 嵌套IF/ELSE4. 关键字:Set Variable If 二 循环流程1. 普通FOR循环2. 嵌套FOR循环3. 退出循环4. 其它常用循环 一 分支流程 1. 关键字:Run Keyword If Run Key…...
win11 好用的 快捷方式 --chatGPT
gpt: Windows 11引入了许多新的功能和改进,同时也包括一些实用的快捷方式和功能。以下是一些Windows 11中的常用快捷方式: 1. **Win D**:最小化或还原所有打开的窗口,显示桌面。 2. **Win E**:打开文件资源管理器…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
