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

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

在这里插入图片描述

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 :阿然成长日记 👈点击可跳转
📆 个人专栏: 🔹数据结构与算法🔹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;}}
}

六、测试结果

在这里插入图片描述

七、 时间复杂度

在这里插入图片描述

相关文章:

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

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …...

Linux中生成so库的文件引用另一个so库问题的解决

文章目录 一、问题介绍二、问题解决 一、问题介绍 由于项目需求&#xff0c;需要将一个“编译时引用了另一个动态链接库”的文件&#xff08;名为main.c&#xff09;&#xff0c;再编译成一个动态链接库。 简要说明一下&#xff0c;即原本的项目代码里&#xff0c;包含main.c…...

EDI是连接原始电子商务和现代电子商务的纽带

EDI是连接原始电子商务和现代电子商务的纽带。 EDI&#xff08;Electronic Data Interchange&#xff0c;电子数据交换&#xff09;是一种电子通信技术&#xff0c;用于在不同组织之间以结构化和标准化的方式交换业务文档和数据。EDI使企业能够更有效地与供应商、客户和合作伙…...

星宿UI2.4资源付费变现小程序源码 支持流量主

第一个小程序为星宿小程序 目前是最新版2.0 搭建星宿需要&#xff1a;备用域名 服务器 微信小程序账号 功能&#xff1a;文章展示 文章分类 资源链接下载 轮播图 直接下载附件功能 很多 很适合做资源类分享 源码下载&#xff1a;https://download.csdn.net/download/m0_6604…...

代码随想录训练营二刷第四十六天 | 完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ

代码随想录训练营二刷第四十六天 | 518. 零钱兑换 II 377. 组合总和 Ⅳ 一、518. 零钱兑换 II 题目链接&#xff1a;https://leetcode.cn/problems/coin-change-ii/ 思路&#xff1a;完全背包求组合数&#xff0c;递推公式dp[j]dp[j-nums[i]]。 求组合数&#xff0c;物品在外…...

python安装第三方模块方法

正常情况下安装python第三方模块没啥说的&#xff0c;但是由于python安装模块默认是在外网下载安装&#xff0c;牵扯外网网速问题&#xff0c;所以可以配置下使用国内某镜像源来下载模块 python -m pip install xxxxxxxxxxx 和 pip install xxxxxxxxxx 的命令都可下载安装第三…...

广西小贷公司设立及小贷牌照申请政策要求

关于广西小额贷款公司设立及小贷牌照申请&#xff0c;依据《关于小额贷款公司试点的指导意见》&#xff08;银监发〔2008〕23号&#xff09;&#xff1b;《广西壮族自治区小额贷款公司管理办法》&#xff08;桂政发〔2009〕71号&#xff09;&#xff1b;《广西壮族自治区人民政…...

PyTorch应用实战二:实现卷积神经网络进行图像分类

文章目录 实验环境MNIST数据集1.网络结构2.程序实现2.1 导入相关库2.2 构建卷积神经网络模型2.3 加载MNIST数据集2.4 训练模型 附&#xff1a;系列文章 实验环境 python3.6 pytorch1.8.0 import torch print(torch.__version__)1.8.0MNIST数据集 MNIST数字数据集是一组手写…...

面试系列 - Java常见算法(二)

目录 一、排序算法 1、插入排序&#xff08;Insertion Sort&#xff09; 2、归并排序&#xff08;Merge Sort&#xff09; 二、图形算法 1、最短路径算法&#xff08;Dijkstra算法、Floyd-Warshall算法&#xff09; Dijkstra算法 Floyd-Warshall算法 2、最小生成树算法&…...

Cortex-A9 架构

一、Cortex-A 处理器运行模式 Cortex-A9处理器有 9中处理模式&#xff0c;如下表所示&#xff1a; 九种运行模式 在上表中&#xff0c;除了User(USR)用户模式以外&#xff0c;其它8种运行模式都是特权模式&#xff0c;在特权模式下&#xff0c;程序可以访问所有的系统资源。这…...

【C语言】循环结构程序设计(第二部分 -- 习题讲解)

前言:昨天我们学习了C语言中循环结构程序设计&#xff0c;并分析了循环结构的特点和实现方法&#xff0c;有了初步编写循环程序的能力&#xff0c;那么今天我们通过一些例子来进一步掌握循环程序的编写和应用。 &#x1f496; 博主CSDN主页:卫卫卫的个人主页 &#x1f49e; &am…...

UGUI交互组件Toggle

一.Toggle对象的构造 Toggle和Button类似&#xff0c;是交互组件的一种 如果所示&#xff0c;通过菜单创建了两个Toggle&#xff0c;Toggle2中更换了背景和标记资源 对象说明Toggle含有Toggle组件的对象Background开关背景Checkmark开关选中标记Label名称文本 二.Toggle组件属…...

亲,您的假期余额已经严重不足了......

引言 大家好&#xff0c;我是亿元程序员&#xff0c;一位有着8年游戏行业经验的主程。 转眼八天长假已经接近尾声了&#xff0c;今天来总结一下大家的假期&#xff0c;聊一聊假期关于学习的看法&#xff0c;并预估一下大家节后大家上班时的样子。 1.放假前一天 即将迎来八天…...

【软件测试】自动化测试selenium(一)

文章目录 一. 什么是自动化测试二. Selenium的介绍1. Selenium是什么2. Selenium的特点3. Selenium的工作原理4. SeleniumJava的环境搭建 一. 什么是自动化测试 自动化测试是指使用软件工具或脚本来执行测试任务的过程&#xff0c;以替代人工进行重复性、繁琐或耗时的测试活动…...

Nginx实现动静分离

一、概述 1、什么是动静分离 动静分离是让动态网站里的动态网页根据一定规则把不变的资源和经常变的资源区分开来&#xff0c;动静资源做好了拆分以后&#xff0c;我们就可以根据静态资源的特点将其做缓存操作&#xff0c;这就是网站静态化处理的核心思路。 动静分离简单的概…...

【算法题】309. 买卖股票的最佳时机含冷冻期

题目&#xff1a; 给定一个整数数组prices&#xff0c;其中第 prices[i] 表示第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下&#xff0c;你可以尽可能地完成更多的交易&#xff08;多次买卖一支股票&#xff09;: 卖出股票后&#xff0c;你无法在…...

1951-2011年长序列高时空分辨率月尺度温度和降水数据集

简介 长序列高时空分辨率月尺度温度和降水数据集&#xff0c;基于中国及周边国家共1153个气温站点和1202个降水站点数据&#xff0c;利用ANUSPLIN软件插值&#xff0c;重建了1951−2011年中国月值气温和降水量的高空间分辨率0.025&#xff08;~2.5km&#xff09;格点数据集&am…...

十天学完基础数据结构-第六天(树(Tree))

树的基本概念 树是一种层次性的数据结构&#xff0c;它由节点组成&#xff0c;这些节点按照层次关系相互连接。树具有以下基本概念&#xff1a; 根节点&#xff1a;树的顶部节点&#xff0c;没有父节点。 子节点&#xff1a;树中每个节点可以有零个或多个子节点。 叶节点&am…...

RobotFramework流程控制(最新版本)

文章目录 一 分支流程1. 关键字&#xff1a;Run Keyword If2. 关键字&#xff1a;IF/ELSE3. 嵌套IF/ELSE4. 关键字&#xff1a;Set Variable If 二 循环流程1. 普通FOR循环2. 嵌套FOR循环3. 退出循环4. 其它常用循环 一 分支流程 1. 关键字&#xff1a;Run Keyword If Run Key…...

win11 好用的 快捷方式 --chatGPT

gpt: Windows 11引入了许多新的功能和改进&#xff0c;同时也包括一些实用的快捷方式和功能。以下是一些Windows 11中的常用快捷方式&#xff1a; 1. **Win D**&#xff1a;最小化或还原所有打开的窗口&#xff0c;显示桌面。 2. **Win E**&#xff1a;打开文件资源管理器…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...

门静脉高压——表现

一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构&#xff1a;由肠系膜上静脉和脾静脉汇合构成&#xff0c;是肝脏血液供应的主要来源。淤血后果&#xff1a;门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血&#xff0c;引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...

Canal环境搭建并实现和ES数据同步

作者&#xff1a;田超凡 日期&#xff1a;2025年6月7日 Canal安装&#xff0c;启动端口11111、8082&#xff1a; 安装canal-deployer服务端&#xff1a; https://github.com/alibaba/canal/releases/1.1.7/canal.deployer-1.1.7.tar.gz cd /opt/homebrew/etc mkdir canal…...

表单设计器拖拽对象时添加属性

背景&#xff1a;因为项目需要。自写设计器。遇到的坑在此记录 使用的拖拽组件时vuedraggable。下面放上局部示例截图。 坑1。draggable标签在拖拽时可以获取到被拖拽的对象属性定义 要使用 :clone, 而不是clone。我想应该是因为draggable标签比较特。另外在使用**:clone时要将…...

第22节 Node.js JXcore 打包

Node.js是一个开放源代码、跨平台的、用于服务器端和网络应用的运行环境。 JXcore是一个支持多线程的 Node.js 发行版本&#xff0c;基本不需要对你现有的代码做任何改动就可以直接线程安全地以多线程运行。 本文主要介绍JXcore的打包功能。 JXcore 安装 下载JXcore安装包&a…...