希尔排序(C语言)

一、步骤:

希尔排序的基本思想:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为gap的记录分在同一组内,并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到gap = 1时,所有记录在统一组内排好序

希尔排序是在直接插入排序的基础上演变的

1.先选定一个小于n的整数gap作为间隔(一般gap = n / 3 + 1),然后将所有距离为gap的元素分在同一组,并对每一组的元素进行直接插入排序。它将一组数组分为了gap组,一组中每个元素的间隔为gap。
2.当gap的大小减到1时,就相当于整个序列被分到一组,进行一次直接插入排序,排序完成。

图片讲解

将上述同一颜色相连的数分为一组,一共分了gap组,一组中每个元素的间隔为gap,对同一组中的元素进行插入排序。黑色组排序结果如图:

然后红色组进行排序:

最后绿色组进行排序,即gap = 3时,最终结果:

当gap = 3这组数据排序结束后,gap会缩小,直到gap = 1时,就是插入排序。

二、代码

代码1:

void ShellSort(int* arr, int n)
{int gap = n; // 先创立一个变量gapwhile (gap > 1){gap = gap / 3 + 1; // gap减小的规律可以是任意的,但最后一次一定要等于1。在这里后面要加1是为了保证最后一次gap = 1如果这里的gap = gap / 2,则最后一次gap一定等于1for (int i = 0; i < n - gap; i++) // i < n - gap为避免越界访问{int end = i;  // 循环内与直接插入排序一样int tmp = arr[end + gap]; // 直接插入排序的tmp为arr[end + 1],这里变成arr[end + gap]while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

代码2 :

这里的代码比上面的更容易理解,这里的代码跟符合上面的图片讲解

void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int j = 0; j < gap; j++) // 将整个数组分为了gap组{for (int i = j; i < n - gap; i += gap) // 每一组的元素进行直接插入排序{int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/469562.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

自动驾驶为什么需要时间同步?高精度时间同步如何实现?

自动驾驶作为汽车与物联网技术、人工智能等高新技术融合的产物&#xff0c;具有新颖性、复杂性和巨大的挑战性。自动驾驶需要实时传输、处理海量数据&#xff0c;并实时做出决策&#xff0c;这不仅要求有通畅网络通信环境、强大的数据算力&#xff0c;更要求时间同步的超低时延…

【信号处理】基于联合图像表示的深度学习卷积神经网络

Combined Signal Representations for Modulation Classification Using Deep Learning: Ambiguity Function, Constellation Diagram, and Eye Diagram 信号表示 Ambiguity Function(AF) 模糊函数描述了信号的两个维度(dimensions):延迟(delay)和多普勒(Doppler)。 …

C++20 概念与约束(1)—— SFINAE

●《C20 概念与约束&#xff08;1&#xff09;—— SFINAE》 《C20 概念与约束&#xff08;2&#xff09;—— 初识概念与约束》 《C20 概念与约束&#xff08;3&#xff09;—— 约束的进阶用法》 1、从模板说起 众所周知&#xff0c;C在使用模板时&#xff0c;如果有多…

[极客大挑战 2019]PHP 1

[极客大挑战 2019]PHP 1 审题 猜测备份在www.zip中&#xff0c;输入下载文件。 知识点 反序列化 解题 查看代码 看到index.php中包含了class.php,直接看class.php中的代码 查看条件 当usernameadmin&#xff0c;password100时输出flag 构造反序列化 输入select中&#…

Kubebot:一款Google云平台下的Slackbot安全测试工具

Kubebot 今天给大家介绍的是一款名叫Kubebot的安全测试Slackbot&#xff0c;该工具基于Google 云平台搭建&#xff0c;并且提供了Kubernetes后端。 项目架构 数据流 1.API请求由Slackbot发起&#xff0c;发送至API服务器&#xff0c;API服务器以Kubernetes(K8s)集群中的Docke…

Kubernetes的基本构建块和最小可调度单元pod-0

文章目录 一&#xff0c;什么是pod1.1pod在k8s中使用方法&#xff08;1&#xff09;使用方法一&#xff08;2&#xff09;使用方法二 1.2pod中容器的进程1.3pod的网络隔离管理&#xff08;1&#xff09;pause容器的作用 1.4 Pod分类&#xff1a;&#xff08;1&#xff09;自主式…

Redis安装(Windows环境)

目录 1.下载2.双击安装后配置环境变量3.启动服务4.设置Windows服务5.启动客户端6.常用的Redis服务命令7.使用图形化界面工具查看Redis内部数据情况类似Navicat 连接数据库 1.下载 1.点击github下载地址 2.上方资源链接下载安装 2.双击安装后配置环境变量 3.启动服务 上图虽然…

windows下qt5.12.11使用ODBC远程连接mysql数据库

1、下载并安装mysql驱动,下载地址:https://dev.mysql.com/downloads/ 2、配置ODBC数据源,打开64位的ODBC数据源配置工具:

【AI写作宝-注册安全分析报告-无验证方式导致安全隐患】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 1. 暴力破解密码&#xff0c;造成用户信息泄露 2. 短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉 3. 带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造…

GFPS技术原理(四)GATT特征值

Fast Pair服务 fast pair 服务的UUID 是0xFE2C&#xff0c;然后它又包含多个特征值&#xff0c;下面一一分析&#xff1a; Model ID UUID是0x1233&#xff0c;设备在谷歌云注册的时候会分配一个24 bit的ID。 Key-based Pairing UUID是0x1234&#xff0c;这个是用来做DH密钥…

3.2 软件需求:面对过程分析模型

面对过程分析模型 1. 需求分析的模型概述1.1 面对过程分析模型-结构化分析方法1.2 结构化分析的过程 2. 功能模型&#xff1a;数据流图初步2.1 加工2.2 外部实体&#xff08;数据源点/终点&#xff09;2.3 数据流2.4 数据存储2.5 注意事项 3. 功能模型&#xff1a;数据流图进阶…

ExecStart=/usr/bin/mongod --config /etc/mongod.conf (code=exited, status=2)

mongodb 开启验证后出现这个问题 邪门的问题 居然是格式问题 要用两个空格表示缩进 而不是tab

数据分析——学习框架

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…

YOLOV8应用|排球垫球计数|附带全部数据集与源码(见文末百度云盘链接)

项目简介: 该项目旨在利用YOLOv8算法实现排球垫球动作的自动识别与计数。YOLOv8作为计算机视觉领域的先进目标检测算法,具备高精度和实时性的特点,非常适合用于体育训练和测试中的自动化计数。项目将排球垫球视频作为输入,通过YOLOv8算法检测视频中的排球及垫球动作,自动…

今天给在家介绍一篇基于jsp的旅游网站设计与实现

项目描述 临近学期结束&#xff0c;还是毕业设计&#xff0c;你还在做java程序网络编程&#xff0c;期末作业&#xff0c;老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。这里根据疫情当下&#xff0c;你想解决的问…

CAN总线数据帧格式详细介绍

目录 1. CAN总线数据帧格式 2. 数据帧 2.1 帧起始 2.2 仲裁段 2.3 控制段 2.4 数据段 2.5 CRC 段 2.6 ACK段 2.7 帧结束 2.8 总结 3. 遥控帧 4. 错误帧 4.1 错误标志 4.1.1 主动错误标志 4.1.2 被动错误标志 4.2 错误界定符 5. 过载帧 6. …

Java面试要点02 - 自动装箱与拆箱的原理与性能解析

本文目录 一、引言二、自动装箱与拆箱的底层原理2.1 编译器的处理机制2.2 字节码层面的分析2.3 缓存机制的实现 三、性能影响的深度分析3.1 内存开销分析3.2 CPU开销分析 四、实际应用中的常见陷阱4.1 空指针异常陷阱4.2 包装类型的比较陷阱 五、最佳实践与优化建议5.1 性能优化…

速通LoRA:《LoRA: Low-Rank Adaptation of Large Language Models》全文解读

文章目录 总览AbstractIntroductionProblem StatementAren’t Existing Solutions Good Enough?Our MethodLow-Rank-Parametrized Update MatricesApplying LoRA to Transformer 何为高斯随机初始化Empirical ExperimentsBaselinesRoBERTa base/largeDeBERTa XXLGPT-2 medium/…

【Java学习】电脑基础操作和编程环境配置

CMD 在Windows中用命令行的方式操作计算机。 打开CMD Win R输入CMD按下回车键 Win E 进入我的电脑 常用的CMD命令 盘符名称冒号 说明&#xff1a;盘符切换 举例&#xff1a;E:回车&#xff0c;表示切换到E盘 dir 说明&#xff1a;查看当前路径下的内容 cd目录 说明&a…

索引【MySQL】

文章目录 聚簇索引 VS 非聚簇索引索引MySQL与磁盘交互的基本单位主键索引索引操作唯一索引的创建普通索引的创建复合索引 索引创建原则 聚簇索引 VS 非聚簇索引 MyISAM存储引擎 - 主键索引结构 MyISAM存储引擎同样采用B树作为索引的基本数据结构 与InnoDB存储引擎的B树不同的…