【排序】3.希尔排序法


希尔排序(直接插入排序的优化)

1.分组思想

上图中gap为5,说明要分成5组。
这5组分别用了五种颜色的线条连接起来了。
第1组:9、4
第2组:1、8
第3组:2、6
第4组:5、3
第5组:7、5
2.缩小增量的过程
前面gap为5的情况排序后会变成下面情况

按照gap把数据分成了两组。
当数据很大的时候,数据的间隔很大。
小的数据会往前方,大的数据会往后放。
gap会逐渐缩小,间隔也会逐渐缩小。
整体的数据会更加趋于有序,这个时候使用直接插入排序效率会更高。
gap为2的时候会排序成下面情况

此时分为了1组,再排序一次后变成下面情况

此时的数据即为有序的。
3.排序情况分析
3.1 排序五组数据的情况
-
gap为5,将数据分为5组,图中红色线画中的为第一组。定义一个 i 变量指向这一组的第二个数据,定义一个 j 变量指向 i - gap 的位置。

-
将 i 下标的值放到定义的 tmp 中,然后与 j下标 的值比较。
若 j 下标的值较大,将 j 下标的值放到 j + gap 的位置。

执行后:

-
j 变量向 j - gap 位置走,若这个位置的下标为负数。
则要将 tmp 的值放到 j + gap的位置。

j 变量此时在-5下标处,要将 tmp 的值放到 j + 5的位置。

这一组数据此时为有序了。
排序下一组数据,i++即可,j 变量依然是在 i - gap 的位置。
后面4组数据类似,不在演示。
最终排序结果是:

3.2 排序两组数据的情况
- 此时 gap 为2,数据此时分为了两组。第一组由红色线画出(4、2、5、8、5),第二组由蓝色线画出(1、3、9、6、7)。
i 变量指向这一组的第二个数据, j 变量指向 i - gap 的位置。

- 将 i 下标的值放到定义的 tmp 中,然后与 j下标 的值比较。
若 j 下标的值较大,将 j 下标的值放到 j + gap 的位置。

执行后:

- j 变量向 j - gap 位置走,若这个位置的下标为负数。
则要将 tmp 的值放到 j + gap的位置。

j 变量此时在-2下标处,要将 tmp 的值放到 j + 2的位置。

这一组数据中的 2 和 4 此时为有序了。
排序下一组数据,i++ 即可,j 变量依然是在 i - gap 的位置。
后面剩下的数据类似,不在演示。
最终排序结果是:

3.3 排序一组数据的情况
- i 变量指向第二个数据, j 变量指向 i - gap 的位置。

- 将 i 下标的值放到定义的 tmp 中,然后与 j下标 的值比较。
若 j 下标的值较大,将 j 下标的值放到 j + gap 的位置。

执行后:

- j 变量向 j - gap 位置走,若这个位置的下标为负数。
则要将 tmp 的值放到 j + gap的位置。

j 变量此时在-1下标处,要将 tmp 的值放到 j + 1的位置。

此时 前两个数据有序了,后面的数据排序过程类似。
排序下一组数据,i++ 即可,j 变量依然是在 i - gap 的位置。
最终结果是:

4.代码分析以及实现

1.间隔分组,通常为总长度的一半
2.组内排序
3.重新设置间隔分组,为前一组的一半
4.当gap= 1时,为直接插入排序。
void ShellSort(int *arr, int n)
{// 初始化间隔为数组的长度int gap = n; while (gap > 1){// 逐渐减小间隔,每次将间隔除以2gap /= 2;// 也可以使用这种方式来减小间隔,这是一种不同的策略// gap = gap / 3 + 1;// 遍历数组,每次跳过gap个元素,对每个子序列进行插入排序for (int i = 0; i < n - gap; i++){// 初始化j为当前元素的索引int j = i;// 保存当前子序列的元素,以便在排序过程中移动int tmp = arr[i + gap];// 将tmp插入到已排序的子序列中的正确位置while (j >= 0){// 如果tmp小于子序列中的元素,则将该元素向后移动一个间隔if (tmp < arr[j]){arr[j + gap] = arr[j];// 继续向前比较j -= gap;}else{// 如果tmp不小于子序列中的元素,则跳出循环break; }}// 当j为负数时,表示tmp已经找到了正确的位置,将其插入到子序列中arr[j + gap] = tmp;}}
}
执行结果:

5.性能分析





相关文章:
【排序】3.希尔排序法
希尔排序(直接插入排序的优化) 1.分组思想 上图中gap为5,说明要分成5组。 这5组分别用了五种颜色的线条连接起来了。 第1组:9、4 第2组:1、8 第3组:2、6 第4组:5、3 第5组:7、5 2.缩…...
商品详情数据API接口概述(json数据格式返回参考)
商品详情数据API接口是指一种编程接口(API,Application Programming Interface),它允许开发者或系统以编程方式获取商品的详细信息。这些信息包括但不限于SKU的详细信息、商品图片、商品属性、价格、库存状态、用户评价等。当调用…...
Jmeter简介
基础介绍 Jmeter录制脚本的原始是配置一个HTTP代理,然后浏览器通过这个代理访问测试页面从而完成脚本录制。 一、下载安装 jmeter本身不需要安装,需要配置环境变量JDK,然后打开bin文件夹中的jmeter.vbs即可。建议jdk 1.7及以上版本。 基本祖…...
网页前端开发之HTML入门篇:标题标签 heading
标题标签 heading <h1>-<h6>是HTML的标题标签,其标签内容会呈现六个不同级别的字号, <h1>字号最大,<h6>字号最小。 示例 <html><body><h1>一级标题</h1><h2>二级标题</h2>&l…...
医院信息化与智能化系统(3)
医院信息化与智能化系统(3) 这里只描述对应过程,和可能遇到的问题及解决办法以及对应的参考链接,并不会直接每一步详细配置 如果你想通过文字描述或代码画流程图,可以试试PlantUML,告诉GPT你的文件结构,让他给你对应的…...
数据结构(线性表)
1线性表的定义与操作 1.1线性表的定义 线性表是一种基础的数据结构,其主要特点是:数据元素之间存在一种线性关系(一对一)。线性表的每一个数据元素都有一个唯一的前驱和后继,除了第一个元素没有前驱,最后…...
ArcGIS Pro SDK (十八)栅格
ArcGIS Pro SDK (十八)栅格 环境:Visual Studio 2022 + .NET6 + ArcGIS Pro SDK 3.0 栅格 1 在文件夹中打开栅格数据集 // 使用文件夹路径创建 FileSystemConnectionPath 对象。 FileSystemConnectionPath connectionPath = new FileSystemConnectionPath(new System...
c++ 对象作用域
在 C 中,对象的作用域(scope)指的是对象的生命周期以及对象在程序中可以访问的范围。作用域影响对象的创建、使用和销毁,主要有以下几种类型: 1. 局部作用域(Local Scope) 局部作用域的对象是…...
【无标题】海尔AI英语面试
1.自我介绍 Good morning. I am delighted to have this English interview. My name is fu guilin. I graduated from CDUT with a degree in Information engineering. During my university years, I have laid a solid foundation in my professional knowledge. I posses…...
软件设计模式------概述
一:简述 目的:为了可重用代码,代码更容易被他人理解,提高代码的可靠性。 定义:是一套被反复使用,多数人知晓,经过分类编目的,代码设计经验的总结。 (通俗来说…...
刷题/学习网站推荐
前言: 最近没怎么学习,荒芜生活,学不进去,太累了,就喜欢翻翻网站有没有好用的东西分享给大家,正好看到一些刷题的网站(其实也是学习的网站吧),相比学程序的很多都是力扣…...
OQE-OPTICAL AND QUANTUM ELECTRONICS
文章目录 一、征稿简介二、重要信息三、服务简述四、投稿须知五、联系咨询 一、征稿简介 二、重要信息 期刊官网:https://ais.cn/u/3eEJNv 三、服务简述 四、投稿须知 1.在线投稿:由艾思科蓝支持在线投稿,请将文章全文投稿至艾思科蓝投稿系…...
在 Spring MVC 应用程序中使用 WebMvcTest 注释有什么用处?
大家好,我是锋哥。今天分享关于【在 Spring MVC 应用程序中使用 WebMvcTest 注释有什么用处?】面试题?希望对大家有帮助; 在 Spring MVC 应用程序中使用 WebMvcTest 注释有什么用处? 1000道 互联网大厂Java工程师 精选…...
Chromium html<textarea>c++接口定义
<textarea>:文本区域元素 <textarea> HTML 元素是一个多行纯文本编辑控件,适用于允许用户输入大量自由格式文本的场景。 例子: <!DOCTYPE html> <html> <head> <meta charset"utf-8"> &l…...
OpenCV高级图形用户界面(13)选择图像中的一个矩形区域的函数selectROI()的使用
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 允许用户在给定的图像上选择一个感兴趣区域(ROI)。 该功能创建一个窗口,并允许用户使用鼠标来选择一个 ROI。…...
《计算机视觉》—— 基于dlib库的人检检测
文章目录 一、dlib库的安装1. 通过PyCharm的Settings安装2. 通过Anaconda安装(适用于Windows等操作系统)3. 通过命令行安装4.懒人安装 二、基于dlib库的人检测1.对图像进行人脸检测2.打开电脑摄像头,检测人脸 一、dlib库的安装 在PyCharm中&…...
分布式数据库安全可靠测评名录之平凯数据库(TiDB企业版)
作者: 数据源的TiDB学习之路 原文来源: https://tidb.net/blog/d052ee0b 2024 年 9 月 30 日,中国信息安全测评中心公布安全可靠测评结果公告(2024年第2号),其中包含 6 款集中式数据库和 11 款分布式数据…...
动态规划之打家劫舍
大纲 题目思路第一步:确定下标含义第二步:确定递推公式第二步:dp数组如何初始化第三步:确定遍历顺序第四步:举例推导dp数组 总结 最近有人询问我 LeetCode 「打家劫舍」系列问题(英文版叫 House Robber&…...
嵌入式入门学习——8基于Protues仿真Arduino+SSD1306液晶显示数字时钟
0 系列文章入口 嵌入式入门学习——0快速入门,Let‘s Do It! SSD1306 1 Protues查找SSD1306器件并放置在画布,画好电气连接(这里VCC和GND画反了,后面仿真出错我才看见,要是现实硬件估计就烧毁了…...
盘点现代浏览器的各种神奇能力,功能令人惊讶
盘点现代浏览器的各种神奇能力,功能令人惊讶😮 浏览器的进化 一个运行在浏览器里面的操作系统。一个炫酷的量子纠缠网页。内嵌在浏览器里面的AI大模型。 随着web技术的迅猛发展,现代浏览器已经不仅仅是一个浏览网页的工具了。它的功能早已进…...
如何快速解决Hackintosh配置难题:OpCore-Simplify终极解决方案指南
如何快速解决Hackintosh配置难题:OpCore-Simplify终极解决方案指南 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 还在为复杂的OpenCore …...
基于SpringBoot + Vue的基于线性回归的音乐推荐系统(爬虫 + 可视化大屏)
文章目录前言一、详细操作演示视频二、具体实现截图三、技术栈1.前端-Vue.js2.后端-SpringBoot3.数据库-MySQL4.系统架构-B/S四、系统测试1.系统测试概述2.系统功能测试3.系统测试结论五、项目代码参考六、数据库代码参考七、项目论文示例结语前言 💛博主介绍&#…...
C++ 与 推理流水线:基于 C++ 协程实现预处理、模型计算与后处理的高并发异步编排架构
尊敬的各位技术同行,大家好。今天,我们聚焦一个在现代人工智能应用中至关重要的议题:如何构建高性能、高并发的推理流水线。随着深度学习模型在各行各业的广泛部署,将这些模型高效地集成到生产系统中,实现低延迟、高吞…...
gpu算力与图形处理
核心本质 图形处理(Graphics):GPU 天生本职工作 —— 画画面、渲染 3D、光栅化、纹理、着色、显示输出。GPU 算力(Compute / GPGPU):利用 GPU 超多小核心 做通用并行计算 —— AI、科学计算、挖矿、渲染、仿…...
Qwen2.5-7B-Instruct法律科技:合同审查要点+修改建议+合规风险等级评估
Qwen2.5-7B-Instruct法律科技:合同审查要点修改建议合规风险等级评估 1. 项目简介:智能法律助手的技术底座 Qwen2.5-7B-Instruct是阿里通义千问推出的旗舰级大模型,专门针对专业级文本交互场景深度优化。相比轻量版的1.5B和3B版本ÿ…...
Axure RP本地化技术指南:从英文界面到全中文工作流
Axure RP本地化技术指南:从英文界面到全中文工作流 【免费下载链接】axure-cn Chinese language file for Axure RP. Axure RP 简体中文语言包。支持 Axure 11、10、9。不定期更新。 项目地址: https://gitcode.com/gh_mirrors/ax/axure-cn 诊断界面本地化痛…...
气象、水文、区域气候--从零搭建 WRF 实验室:Linux 编译 + Python 绘图 + 下垫面改造一站式技术
做气象、水文、气候、环境、地理遥感等领域的科研人,是不是都逃不过这些噩梦:编译地狱:Linux 环境下 NetCDF、MPI、WRF 编译报错满天飞,compile.log里的 Error 看不懂,卡了一周连第一步都跑不通环境混乱:Fo…...
2026年五款新手热门电钢琴横向评测~电钢琴深度对比与选择建议
不少钢琴学习者熬过初期的热情期后,都会陷入一个怪圈,就是在练琴时长明明在增加,可实际演奏的声音却机械又僵硬,完全没了灵动质感。从核心逻辑来看,电钢琴从来不是单纯的电子产品,而是高精度传感系统与声学…...
青蓝送水小程序开发(现成案例)
以下为现成的送水类小程序开发案例及关键功能模块,可结合业务需求调整:核心功能模块用户端:水品分类展示、在线下单、配送地址管理、订单跟踪、在线支付、会员积分系统配送端:订单接收、配送路线规划、状态更新、异常反馈管理后台…...
新手福音:用快马AI生成你的第一个简易网页网盘项目
作为一个刚接触编程的新手,想要快速上手一个实际项目确实容易感到无从下手。最近我在学习网页开发时,尝试用InsCode(快马)平台做了一个简易网页网盘,整个过程意外地顺利。这个项目虽然功能简单,但涵盖了前端开发的几个核心概念&am…...
