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

【排序】3.希尔排序法

在这里插入图片描述


pic_ea1faa34.png

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

在这里插入图片描述

1.分组思想

pic_0dfb86e6.png
上图中gap为5,说明要分成5组。
这5组分别用了五种颜色的线条连接起来了。

第1组:9、4
第2组:1、8
第3组:2、6
第4组:5、3
第5组:7、5

2.缩小增量的过程

前面gap为5的情况排序后会变成下面情况

pic_f23d22c9.png
按照gap把数据分成了两组。

当数据很大的时候,数据的间隔很大。
小的数据会往前方,大的数据会往后放。

gap会逐渐缩小,间隔也会逐渐缩小。

整体的数据会更加趋于有序,这个时候使用直接插入排序效率会更高。

gap为2的时候会排序成下面情况
pic_0447dcb5.png
此时分为了1组,再排序一次后变成下面情况
pic_b3e009ae.png
此时的数据即为有序的。

3.排序情况分析

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

  2. i 下标的值放到定义的 tmp 中,然后与 j下标 的值比较。
    j 下标的值较大,将 j 下标的值放到 j + gap 的位置。
    pic_a2d5c2ab.png
    执行后
    pic_c8c66b53.png

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

    pic_309fd82e.png
    j 变量此时在-5下标处,要将 tmp 的值放到 j + 5的位置。
    pic_6efd9088.png
    这一组数据此时为有序了。
    排序下一组数据,i++即可,j 变量依然是在 i - gap 的位置。
    后面4组数据类似,不在演示

    最终排序结果是:
    pic_39f25156.png

3.2 排序两组数据的情况
  1. 此时 gap 为2,数据此时分为了两组。第一组由红色线画出(4、2、5、8、5),第二组由蓝色线画出(1、3、9、6、7)。
    i 变量指向这一组的第二个数据, j 变量指向 i - gap 的位置。
    pic_79aba18f.png
  2. 将 i 下标的值放到定义的 tmp 中,然后与 j下标 的值比较。
    若 j 下标的值较大,将 j 下标的值放到 j + gap 的位置。
    pic_a1827bdf.png
    执行后:
    pic_c7dc2b21.png
  3. j 变量向 j - gap 位置走,若这个位置的下标为负数。
    则要将 tmp 的值放到 j + gap的位置。
    pic_77e9e055.png
    j 变量此时在-2下标处,要将 tmp 的值放到 j + 2的位置。
    pic_24b5d29e.png
    这一组数据中的 2 和 4 此时为有序了。
    排序下一组数据,i++ 即可,j 变量依然是在 i - gap 的位置。
    后面剩下的数据类似,不在演示。
    最终排序结果是:
    pic_e322a32c.png
3.3 排序一组数据的情况
  1. i 变量指向第二个数据, j 变量指向 i - gap 的位置。
    pic_5d8552c1.png
  2. 将 i 下标的值放到定义的 tmp 中,然后与 j下标 的值比较。
    若 j 下标的值较大,将 j 下标的值放到 j + gap 的位置。
    pic_b717516f.png
    执行后:
    pic_d4882821.png
  3. j 变量向 j - gap 位置走,若这个位置的下标为负数。
    则要将 tmp 的值放到 j + gap的位置。
    pic_86700dd5.png
    j 变量此时在-1下标处,要将 tmp 的值放到 j + 1的位置。
    pic_15bdda6e.png
    此时 前两个数据有序了,后面的数据排序过程类似。
    排序下一组数据,i++ 即可,j 变量依然是在 i - gap 的位置。
    最终结果是:
    pic_846996a2.png

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.性能分析

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

pic_90b88cc9.png

相关文章:

【排序】3.希尔排序法

希尔排序&#xff08;直接插入排序的优化&#xff09; 1.分组思想 上图中gap为5&#xff0c;说明要分成5组。 这5组分别用了五种颜色的线条连接起来了。 第1组&#xff1a;9、4 第2组&#xff1a;1、8 第3组&#xff1a;2、6 第4组&#xff1a;5、3 第5组&#xff1a;7、5 2.缩…...

商品详情数据API接口概述(json数据格式返回参考)

商品详情数据API接口是指一种编程接口&#xff08;API&#xff0c;Application Programming Interface&#xff09;&#xff0c;它允许开发者或系统以编程方式获取商品的详细信息。这些信息包括但不限于SKU的详细信息、商品图片、商品属性、价格、库存状态、用户评价等。当调用…...

Jmeter简介

基础介绍 Jmeter录制脚本的原始是配置一个HTTP代理&#xff0c;然后浏览器通过这个代理访问测试页面从而完成脚本录制。 一、下载安装 jmeter本身不需要安装&#xff0c;需要配置环境变量JDK&#xff0c;然后打开bin文件夹中的jmeter.vbs即可。建议jdk 1.7及以上版本。 基本祖…...

网页前端开发之HTML入门篇:标题标签 heading

标题标签 heading <h1>-<h6>是HTML的标题标签&#xff0c;其标签内容会呈现六个不同级别的字号&#xff0c; <h1>字号最大&#xff0c;<h6>字号最小。 示例 <html><body><h1>一级标题</h1><h2>二级标题</h2>&l…...

医院信息化与智能化系统(3)

医院信息化与智能化系统(3) 这里只描述对应过程&#xff0c;和可能遇到的问题及解决办法以及对应的参考链接&#xff0c;并不会直接每一步详细配置 如果你想通过文字描述或代码画流程图&#xff0c;可以试试PlantUML&#xff0c;告诉GPT你的文件结构&#xff0c;让他给你对应的…...

数据结构(线性表)

1线性表的定义与操作 1.1线性表的定义 线性表是一种基础的数据结构&#xff0c;其主要特点是&#xff1a;数据元素之间存在一种线性关系&#xff08;一对一&#xff09;。线性表的每一个数据元素都有一个唯一的前驱和后继&#xff0c;除了第一个元素没有前驱&#xff0c;最后…...

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 中&#xff0c;对象的作用域&#xff08;scope&#xff09;指的是对象的生命周期以及对象在程序中可以访问的范围。作用域影响对象的创建、使用和销毁&#xff0c;主要有以下几种类型&#xff1a; 1. 局部作用域&#xff08;Local Scope&#xff09; 局部作用域的对象是…...

【无标题】海尔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…...

软件设计模式------概述

一&#xff1a;简述 目的&#xff1a;为了可重用代码&#xff0c;代码更容易被他人理解&#xff0c;提高代码的可靠性。 定义&#xff1a;是一套被反复使用&#xff0c;多数人知晓&#xff0c;经过分类编目的&#xff0c;代码设计经验的总结。 &#xff08;通俗来说&#xf…...

刷题/学习网站推荐

前言&#xff1a; 最近没怎么学习&#xff0c;荒芜生活&#xff0c;学不进去&#xff0c;太累了&#xff0c;就喜欢翻翻网站有没有好用的东西分享给大家&#xff0c;正好看到一些刷题的网站&#xff08;其实也是学习的网站吧&#xff09;&#xff0c;相比学程序的很多都是力扣…...

OQE-OPTICAL AND QUANTUM ELECTRONICS

文章目录 一、征稿简介二、重要信息三、服务简述四、投稿须知五、联系咨询 一、征稿简介 二、重要信息 期刊官网&#xff1a;https://ais.cn/u/3eEJNv 三、服务简述 四、投稿须知 1.在线投稿&#xff1a;由艾思科蓝支持在线投稿&#xff0c;请将文章全文投稿至艾思科蓝投稿系…...

在 Spring MVC 应用程序中使用 WebMvcTest 注释有什么用处?

大家好&#xff0c;我是锋哥。今天分享关于【在 Spring MVC 应用程序中使用 WebMvcTest 注释有什么用处&#xff1f;】面试题&#xff1f;希望对大家有帮助&#xff1b; 在 Spring MVC 应用程序中使用 WebMvcTest 注释有什么用处&#xff1f; 1000道 互联网大厂Java工程师 精选…...

Chromium html<textarea>c++接口定义

<textarea>&#xff1a;文本区域元素 <textarea> HTML 元素是一个多行纯文本编辑控件&#xff0c;适用于允许用户输入大量自由格式文本的场景。 例子&#xff1a; <!DOCTYPE html> <html> <head> <meta charset"utf-8"> &l…...

OpenCV高级图形用户界面(13)选择图像中的一个矩形区域的函数selectROI()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 允许用户在给定的图像上选择一个感兴趣区域&#xff08;ROI&#xff09;。 该功能创建一个窗口&#xff0c;并允许用户使用鼠标来选择一个 ROI。…...

《计算机视觉》—— 基于dlib库的人检检测

文章目录 一、dlib库的安装1. 通过PyCharm的Settings安装2. 通过Anaconda安装&#xff08;适用于Windows等操作系统&#xff09;3. 通过命令行安装4.懒人安装 二、基于dlib库的人检测1.对图像进行人脸检测2.打开电脑摄像头&#xff0c;检测人脸 一、dlib库的安装 在PyCharm中&…...

分布式数据库安全可靠测评名录之平凯数据库(TiDB企业版)

作者&#xff1a; 数据源的TiDB学习之路 原文来源&#xff1a; https://tidb.net/blog/d052ee0b 2024 年 9 月 30 日&#xff0c;中国信息安全测评中心公布安全可靠测评结果公告&#xff08;2024年第2号&#xff09;&#xff0c;其中包含 6 款集中式数据库和 11 款分布式数据…...

动态规划之打家劫舍

大纲 题目思路第一步&#xff1a;确定下标含义第二步&#xff1a;确定递推公式第二步&#xff1a;dp数组如何初始化第三步&#xff1a;确定遍历顺序第四步&#xff1a;举例推导dp数组 总结 最近有人询问我 LeetCode 「打家劫舍」系列问题&#xff08;英文版叫 House Robber&…...

嵌入式入门学习——8基于Protues仿真Arduino+SSD1306液晶显示数字时钟

0 系列文章入口 嵌入式入门学习——0快速入门&#xff0c;Let‘s Do It&#xff01; SSD1306 1 Protues查找SSD1306器件并放置在画布&#xff0c;画好电气连接&#xff08;这里VCC和GND画反了&#xff0c;后面仿真出错我才看见&#xff0c;要是现实硬件估计就烧毁了&#xf…...

盘点现代浏览器的各种神奇能力,功能令人惊讶

盘点现代浏览器的各种神奇能力&#xff0c;功能令人惊讶&#x1f62e; 浏览器的进化 一个运行在浏览器里面的操作系统。一个炫酷的量子纠缠网页。内嵌在浏览器里面的AI大模型。 随着web技术的迅猛发展&#xff0c;现代浏览器已经不仅仅是一个浏览网页的工具了。它的功能早已进…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...