【排序算法】希尔排序
前言:学习希尔排序前最好先掌握插入排序,在进行;不会的可以点击——>【排序算法】插入排序-CSDN博客
一、希尔排序:
希尔排序,也称为缩小增量排序,是一种基于插入排序的快速改进算法。由Donald Shell于1959年提出。 它的基本思想是将待排序的元素按照一定的增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。希尔排序在一般用于处理大量数据!!
二、思路:
分成2个阶段:
1、预排序:这个阶段将待排序的数据分成gap组,对每组数据进行插入排序。
2、插入排序:gap==1时,也就是只有1组的情况,这个数组就变成有序数组了。
具体详情:
1、将一个小于n(元素个数的)的整数作为gap增量,所有距离为gap的元素作为一组数据(也就是我们说的将数组分成gap组)然后对每一组数据进行插入排序,排好后,取一个比第一增量小的整数(比原gap小的组数)重新将新的gap距离的元素作为一组数据,接着上述操作;重复这些操作
2、当gap不断细分到了gap==1即将所有元素分为一组时,进行插入排序,数据变成有序!
下面的动图,我觉的比较直观的了?当然没看懂也没关系,下面会有讲解

先分组,然后你会发现我们分了三组,我们以3个元素为一组分的,但是有的组元素个数未满三个,因为元素之间的距离和数组长度的差异,会有点不同,但是影响不大哈,值得注意的是距离差3,不是元素个数差3哈,个数是只差了2个元素,从图里也可以看出来

分为3个组:
第一组:8、7、5
第二组:9、2、4
第三组:1、3
对第一组进行插入排序
然后接下来是下标为0+gap+gap的位置来一次插入排序,该位置本来的元素是5,经过插入排序后,5到了这组数据的最前面;此时这一组的数据是不是变成有序了

当每组都进行完插入排序后,我们可以发现小的数几乎靠近左边,大的数几乎靠近右边。大致粗略有点顺序了
然后将gap==1,进行一次整体的插入排序;因为数据比较少 所以这里gap的分化次数也比较少
三、时间复杂度:(有点难证明,记住即可)
O(N^1.3)
四、实现:
先考虑一组的实现哈。发现了没?其实和插入排序实现很相似,如果gap==1就是插入排序了。
对每一组都要进行插入;发现了么,先写底层逻辑真的很清晰;我们会顺畅很多
但是我不想要三层循环嵌套,可以修改一下,之前是一组一组的进行,就是说排好一组在进行另一组。现在我直接交错进行,先第一组的第一个元素,然后第二组的第一个元素,然后第三组的第一个元素,再是第一组的第二个元素……
下标到最后一组倒数第二个元素的位置即可,因为我们是将end的下一个元素抽出来,注意不要越界访问
最后要完成gap的变化,gap不是一直不变的,会不断地变小,直到gap==1;也就是第二个阶段:对整个数组进行插入排序,所以gap是个变值
整体代码:
void ShellSort(int* a, int n)
{int gap = n;//gap的组数越大,数据可以更快的跳到后面,小的更快跳到前面,但是越不接近有序;反之,gap越接近有序while (gap > 1){//巧妙的用的除法,/2 /3 /4都行,但是有人证明了/3更好,还要加1,因为gap小于3的话gap/3==0//最后一次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] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}
gap的选取:
gap刚开始时从每组3个数据开始进行分组插入排序,然后gap=gap/3+1不断地分化组数(分的组数在减少,但是相反的每组数据个数在增加)加一个 1 是为了保证最后一次满足gap==1,因为gap/3 gap小于3时得到的商只能是0;并不是只能gap/3,也可以gap/2等等,但是目前gap/3+1是时间复杂度被验证过了的
分组组数的特点:
gap越大,每一组的数据间隔越大(中间隔的元素个数多),插入一次的幅度更大,大的数据能够更快的跳到后面,小的数据也能更快的跳到前面,但是越远离有序
gep越小,每组数据间隔越小(中间隔的元素个数少),此时数据跳到后面也就越慢,小的数据跳到前面也越慢;但是越接近有序,即gap==1时就是有序的
感 谢 观 看
相关文章:
【排序算法】希尔排序
前言:学习希尔排序前最好先掌握插入排序,在进行;不会的可以点击——>【排序算法】插入排序-CSDN博客 一、希尔排序: 希尔排序,也称为缩小增量排序,是一种基于插入排序的快速改进算法。由Donald Shell于1…...
数学建模--LaTex插入表格详细介绍
目录 1.插入普通的边线表格 3.三线表的插入和空格说明 3.基于复杂情况下表格的插入 1.插入普通的边线表格 (1)像这个右边的生成的这个比较普通的表格,我们是使用下面的代码实现的: (2)和插入一个一个图片…...
未来已来:Flutter引领的安卓与跨平台开发奇幻之旅
引言 随着移动开发技术的飞速发展,跨平台开发框架如Flutter正逐渐改变着传统的安卓和iOS开发格局。作为一名资深的安卓开发工程师,我深刻感受到了Flutter带来的变革和机遇。今天,我想与大家分享Flutter在跨平台开发中的奇幻之旅,…...
如何将Windows PC变成Wi-Fi热点?这里提供详细步骤
序言 Windows 10和Windows 11都有内置功能,可以将你的笔记本电脑(或台式机)变成无线热点,允许其他设备连接到它并共享你的互联网连接。以下是操作指南。 由于Windows中隐藏的虚拟Wi-Fi适配器功能,你甚至可以在连接到另一个Wi-Fi网络或无线路由器时创建Wi-Fi热点,通过另…...
报错:Cannot invoke “springfox.documentation.service.ParameterType.getIn()“
文章目录 前言一、报错分析二、解决办法修改代码 总结 前言 遇到报错:Cannot invoke "springfox.documentation.service.ParameterType.getIn()" because the return value of "springfox.documentation.service.RequestParameter.getIn()" is …...
一个生动的例子——通过ERC20接口访问Tether合约
生动的例子 USDT:符合ERC20标准的美元稳定币,Tether合约获得测试网上Tether合约地址通过自己写的ERC20接口访问这个合约 Tether合约地址:0xdAC17F958D2ee523a2206206994597C13D831ec7 IERC20.sol // SPDX-License-Identifier: GPL-3.0pra…...
新媒体时代,LCD电子价签赋予零售场景新活力
近年来,全球企业迅速掀起了数字化转型的浪潮,加速了新零售科技的发展与应用。在实体零售门店中,商品货架显示逐渐趋向智能化和多样化。然而,在信息传播日益碎片化和视频化的时代,零售门店如何更有效地吸引消费者的注意…...
芋道源码 / yudao-cloud:前端技术架构探索与实践
摘要: 随着企业信息化建设的深入,后台管理系统在企业运营中扮演着至关重要的角色。本文将以芋道源码的yudao-cloud项目为例,深入探讨其前端技术架构的设计思路、关键技术与实现细节,并分享在开发过程中遇到的挑战与解决方案。 一、…...
2024 angstromCTF re 部分wp
Guess the Flag 附件拖入ida 比较简单,就一个异或 switcher 附件拖入ida 明文flag Polyomino 附件拖入ida 需要输入九个数,然后进入处理和判断,如果满足条件则进入输出flag部分,flag和输入有关,所以要理解需要满足什么…...
STL库--priority_queue
目录 priority_queue定义 prority_queue容器内元素的访问 priority_queue()常用函数实例解析 priority_queue内元素优先级的设置 priority_queue的常见用途 priority_queue又称为优先队列,其底层是用堆来进行实现的。在优先队列中,队首元素一定是当…...
网络编程 —— Http使用httpClient实现页面爬虫
先去找类型的a标签 取出图片所在网址 取出https://desk.3gbizhi.com/deskMV/438.html 搭建Form界面 Http类 public static HttpClient Client { get; } static Http() {HttpClientHandler handler new HttpClientHandler();//处理消息对象//ServerCertificateCustomValidat…...
【本地运行chatgpt-web】启动前端项目和service服务端项目,也是使用nodejs进行开发的。两个都运行成功才可以使用!
1,启动web界面 https://github.com/Chanzhaoyu/chatgpt-web#node https://nodejs.org/en/download/package-manager # 使用nvm 安装最新的 20 版本。 curl -o- https://raw.githubusercontent.com/nvm-sh/nvm/v0.39.7/install.sh | bash source /root/.bashrc n…...
TOGAF企业架构章节(核心)知识点(一)
TOGAF标准9.2一共有 6 部分: 第一部分(简介):企业架构的关键概念,特别是 TOGAF 方法进行了概要介绍第二部分(架构开发方法): TOGAF 框架的核心部分。描述了 TOGAF 架构开发方法&…...
手摸手教你uniapp原生插件开发
行有余力,心无恐惧 这篇技术文章写了得有两三个礼拜,虽然最近各种事情,工作上的生活上的,但是感觉还是有很多时间被浪费.还记得几年前曾经有一段时间7点多起床运动,然后工作学习,看书提升认知.现在我都要佩服那会儿的自己.如果想回到那种状态,我觉得需要有三个重要的条件. 其…...
C++进程间通信 消息队列
C进程间通信 消息队列 消息队列概述消息队列代码示例1. 创建和发送消息的程序(sender.cpp)2. 接收消息的程序(receiver.cpp) 代码解释运行步骤运行结果 消息队列概述 消息队列是一种进程间通信机制,允许一个或多个进程…...
mysql中InnoDB的统计数据
大家好。我们知道,mysql中存在许多的统计数据,比如通过SHOW TABLE STATUS 可以看到关于表的统计数据,通过SHOW INDEX可以看到关于索引的统计数据,那么这些统计数据是怎么来的呢?它们是以什么方式收集的呢?今…...
P459 包装类Wrapper
包装类的分类 1)针对八种基本数据类型相应的引用类型——包装类。 2)有了类的特点,就可以调用类中的方法。 Boolean包装类 Character包装类 其余六种Number类型的包装类 包装类和基本数据类型的相互转换 public class Integer01 {publi…...
Kong网关的负载均衡
安装java环境 查询 java安装包 196 yum list java* 安装java8197 yum install -y java-1.8.0-openjdk.x86_64 检验java8是否安装成功。198 java -version2个tomcat准备 另外一个tomcat区别在于:配置文件。conf/server.xml 启动tomcat [rootlocalhost bin]# ./…...
这是一个逗号
还不太能是句号,随想录这两个月算是给我一个学算法的开头,感慨还是挺多的,但是语文功底很差,就接着写流水账吧。 高考前想报计算机,但是那年是先报志愿后考试,家里人劝我选择更稳一点的985,又说…...
oracle tree
select * from "Test"; INSERT INTO "Test" ("id", "name", "pid") VALUES (01, 中国, 00); INSERT INTO "Test" ("id", "name", "pid") VALUES (01.01, 福建, 01); INSERT INTO…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...
rknn toolkit2搭建和推理
安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 ,不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源(最常用) conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...




