希尔排序,详细解析(附图解)
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监控可视化平台!
前言 在当前激烈的市场竞争中,创新和效率成为企业发展的核心要素之一。在这种背景下,如何保证产品和服务的稳定性、可靠性以及高效性就显得尤为重要。 而在软件开发过程中,性能测试是一项不可或缺的环节,它可以有效的评估一个系…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent
安全大模型训练计划:基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标:为安全大模型创建高质量、去偏、符合伦理的训练数据集,涵盖安全相关任务(如有害内容检测、隐私保护、道德推理等)。 1.1 数据收集 描…...
git: early EOF
macOS报错: Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...
鸿蒙(HarmonyOS5)实现跳一跳小游戏
下面我将介绍如何使用鸿蒙的ArkUI框架,实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...
热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁
赛门铁克威胁猎手团队最新报告披露,数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据,严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能,但SEMR…...
