希尔排序,详细解析(附图解)
1.希尔排序思路
希尔排序是一种基于插入排序的算法,通过将原始数据分成若干个子序列,然后对子序列进行插入排序,逐渐减小子序列的间隔,最后对整个序列进行一次插入排序。
1.分组直接插入排序,目标接近有序-----------gap>1
2.直接插入排序,目标有序-----------------------gap=1
2.分组排序思路分析
假设固定gap=3,那么以下数组可以分为三组
每一组都使用用直接插入排序,使数据有序

最后三组都排完后数组变成了:0,2,1,4,3,6,5,7,8,此时的结果接近有序
此时只需要再调用一次插入排序,即可让整个数组变得有序。
下面我们来实现一下这个
2.1思路代码
void ShellSort(int* a, int n)
{int gap = 3;for (int j = 0; j < gap; j++){for (int i = j; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");}
}
在每一组排序后都打印一下来观察
2.2结果显示

3.gap的设定
当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
当我们不再固定gap而是让他变化时,如下图gap=gap/2;

3.1动图演示

一般现在认为gap=gap/3+1较为合适,我们以此来实现一下代码
3.2最终代码实现
这里省去了一层for循环,把原本一组一组交换变为了组之间交替交换,时间复杂度没有改变。
//升序
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){if (a[end] > a[end + gap]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}
4.时间复杂度
记忆:O(N^1.3)
比O(N*logN)大,比O(N^2)小
希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的希尔排序的时间复杂度都不固定


相关文章:
希尔排序,详细解析(附图解)
1.希尔排序思路 希尔排序是一种基于插入排序的算法,通过将原始数据分成若干个子序列,然后对子序列进行插入排序,逐渐减小子序列的间隔,最后对整个序列进行一次插入排序。 1.分组直接插入排序,目标接近有序--------…...
【C语言篇】编译和链接以及预处理介绍(下篇)
文章目录 前言#和###运算符##运算符 命名约定#undef命令⾏定义条件编译#if和#endif多个分支的条件编译判断是否被定义嵌套指令 头文件被包含头文件被包含的方式本地文件包含库文件的包含 嵌套文件包含 其他预处理指令 写在最后 前言 本篇接前一篇【C语言篇】编译和链接以及预处…...
利用Llama2 7b自己实现一套离线AI
前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家, 可以当故事来看,轻松学习。 离了 ChatGPT 本人简直寸步难行,今天 ChatGPT 大面积宕机,服务直到文章写作&am…...
Ciallo~(∠・ω・ )⌒☆第十七篇 Ubuntu基础使用 其一
Ubuntu是一种基于Linux的操作系统,它是开源的、免费的,并且具有广泛的用户群体。 基本文件操作:Ubuntu使用命令行工具来进行文件操作。以下是一些常用的命令: 切换到用户主目录: cd ~ 切换到上级目录: cd .…...
Linux-零拷贝技术
什么是零拷贝? 在传统的数据传输过程中,数据需要从磁盘读取到内核空间的缓冲区,然后再从内核空间拷贝到用户空间的应用程序缓冲区。如果需要将数据发送到网络,数据还需要再次从用户空间拷贝到内核空间的网络缓冲区。这个过程涉及…...
小区团购管理
TOC springboot254小区团购管理 第1章 绪论 1.1选题动因 当前的网络技术,软件技术等都具备成熟的理论基础,市场上也出现各种技术开发的软件,这些软件都被用于各个领域,包括生活和工作的领域。随着电脑和笔记本的广泛运用&…...
图像文本擦除无痕迹!复旦提出EAFormer:最新场景文本分割新SOTA!(ECCV`24)
文章链接:https://arxiv.org/pdf/2407.17020 git链接:https://hyangyu.github.io/EAFormer/ 亮点直击 为了在文本边缘区域实现更好的分割性能,本文提出了边缘感知Transformer(EAFormer),该方法明确预测文…...
Codeforces Round 966 (Div. 3)(A,B,C,D,E,F)
A. Primary Task 签到 void solve() {string s;cin>>s;bool bltrue;if(s.size()<2)blfalse;else{if(s.substr(0,2)"10"){if(s[2]0)blfalse;else if(s[2]1&&s.size()<3)blfalse; }else blfalse;}if(bl)cout<<"YES\n";else cout…...
【代码随想录算法训练营第42期 第六天 | LeetCode242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和】
代码随想录算法训练营第42期 第六天 | LeetCode242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和 一、242.有效的字母异位词 解题代码C: bool isAnagram(char* s, char* t) {int len1 strlen(s);int len2 strlen(t);int al[26] {0};int b…...
WebRTC音视频开发读书笔记(一)
一、基本概念 WebRTC(Web Real-Time Communication,网页即时通信)于2011年6月1日开源,并被纳入万维网联盟的W3C推荐标准,它通过简单API为浏览器和移动应用提供实时通信RTC功能。 1、特点 跨平台:可以在Web,Android、…...
llama3.1本地部署方式
llama3.1 资源消耗情况 Llama 3.1 - 405B、70B 和 8B 的多语言与长上下文能力解析  70B版本,FP1616K token需要的资源约为75G;FP16128K token需要的资源约为110G  1、ollama ollama工具部署及使用…...
相机光学(三十四)——色差仪颜色观察者视角
1.为什么会有观察者视角 颜色观察角度主要涉及到人眼观察物体时,视角的大小以及屏幕显示颜色的方向性对颜色感知的影响。 人眼观察物体的视角:在黑暗条件下,人眼主要依靠杆体细胞来分辨物体的轮廓,而杆体细胞分布在视网…...
思二勋:web3.0是打造应对复杂市场敏捷组织的关键
本文内容摘自思二勋所著的《分布式商业生态战略》一书。 数字化时代,需要企业具备敏捷应对变化的能力,以敏捷反应应对客户和市场的迅速变化。敏捷能力的建设需要触点网络、信息系统、IT 架构、业务流程等同时实现敏捷。尤其是在多变且复杂环境中,特别要求战略管理的敏捷性和…...
一文带你快速了解——HAProxy负载均衡
一、HAProxy简介 1.1、什么是Haproxy HAProxy是法国开发者 威利塔罗(Willy Tarreau)在2000年使用C语言开发的一个开源软件是一款具备高并发(万级以上)、高性能的TCP和HTTP负载均衡器支持基于cookie的持久性,自动故障切换,支持正则表达式及web状态统计。…...
【C++高阶】哈希—— 位图 | 布隆过滤器 | 哈希切分
✨ 人生如梦,朝露夕花,宛若泡影 🌏 📃个人主页:island1314 🔥个人专栏:C学习 ⛺️ 欢迎关注:👍点赞 👂&am…...
启发式算法之模拟退火算法
文章目录 1. 模拟退火算法概述1.1 算法起源与发展1.2 算法基本原理 2. 算法实现步骤2.1 初始化过程2.2 迭代与降温策略 3. 模拟退火算法的优化策略3.1 冷却进度表的设计3.2 参数调整与策略 4. 模拟退火算法的应用领域4.1 组合优化问题4.1.1 旅行商问题(TSPÿ…...
编码器汇总:光学编码器,霍尔编码器,磁性编码器,电容式编码器,单圈编码器,多圈编码器,增量式编码器,绝对值式编码器等
系列文章目录 1.元件基础 2.电路设计 3.PCB设计 4.元件焊接 5.板子调试 6.程序设计 7.算法学习 8.编写exe 9.检测标准 10.项目举例 11.职业规划 文章目录 前言一、光学编码器二、霍尔编码器三、磁性编码器四、电容式编码器五、单圈编码器六、多圈编码器七、增量式编码器八、…...
有哪些性价比高的蓝牙耳机可入?四款百万好评实力品牌推荐!
蓝牙耳机大家都再熟悉不过了,作为最常用的智能配件之一,谁还没有用过几款蓝牙耳机呢,但是选购蓝牙耳机上还是有一些需要注意的地方,市面上的吹风机可谓是五花八门。有哪些性价比高的蓝牙耳机可入?本人花了一些时间整理…...
MySQL数据库——表的CURD(Update)
3.Update 语法:update table_name set column expr 案例 将孙悟空的数学成绩变更为80 mysql> select name,math from result; ----------------- | name | math | ----------------- | 唐三藏 | 98 | | 孙悟空 | 78 | | 猪悟能 | 98 |…...
性能测试 —— linux服务器搭建JMeter+Grafana+Influxdb监控可视化平台!
前言 在当前激烈的市场竞争中,创新和效率成为企业发展的核心要素之一。在这种背景下,如何保证产品和服务的稳定性、可靠性以及高效性就显得尤为重要。 而在软件开发过程中,性能测试是一项不可或缺的环节,它可以有效的评估一个系…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...
二维FDTD算法仿真
二维FDTD算法仿真,并带完全匹配层,输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...
Java数组Arrays操作全攻略
Arrays类的概述 Java中的Arrays类位于java.util包中,提供了一系列静态方法用于操作数组(如排序、搜索、填充、比较等)。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序(sort) 对数组进行升序…...
用鸿蒙HarmonyOS5实现国际象棋小游戏的过程
下面是一个基于鸿蒙OS (HarmonyOS) 的国际象棋小游戏的完整实现代码,使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├── …...
PostgreSQL 对 IPv6 的支持情况
PostgreSQL 对 IPv6 的支持情况 PostgreSQL 全面支持 IPv6 网络协议,包括连接、存储和操作 IPv6 地址。以下是详细说明: 一、网络连接支持 1. 监听 IPv6 连接 在 postgresql.conf 中配置: listen_addresses 0.0.0.0,:: # 监听所有IPv4…...
codeforces C. Cool Partition
目录 题目简述: 思路: 总代码: https://codeforces.com/contest/2117/problem/C 题目简述: 给定一个整数数组,现要求你对数组进行分割,但需满足条件:前一个子数组中的值必须在后一个子数组中…...
qt 双缓冲案例对比
双缓冲 1.双缓冲原理 单缓冲:在paintEvent中直接绘制到屏幕,绘制过程被用户看到 双缓冲:先在redrawBuffer绘制到缓冲区,然后一次性显示完整结果 代码结构 单缓冲:所有绘制逻辑在paintEvent中 双缓冲:绘制…...
