【排序算法】希尔排序

请添加图片描述

文章目录

  • 📝希尔排序( 缩小增量排序 )
  • 🌠分组思想
  • 🌠缩小增量的过程
  • 🌠 排序步骤
    • 🌉希尔排序的特性总结:
  • 🚩总结


📝希尔排序( 缩小增量排序 )

希尔排序是一种经典的排序算法,它通过多次插入排序的方式,以及逐步缩小增量的策略,实现对数据的高效排序,希尔排序法又称缩小增量法。

🌠分组思想

希尔排序的核心思想在于将待排序的数据分成若干组,对每一组数据进行插入排序。这样做的好处是,一方面可以减少数据的比较次数和移动次数,另一方面可以利用已经部分有序的性质,加速排序的过程。初始时,数据被分成的组数由一个称为增量的值决定。

🌠缩小增量的过程

希尔排序的另一个关键点是逐步缩小增量的过程。初始时,增量的值通常为数组长度的一半。随着排序的进行,增量逐步减小,直到增量为1,完成最后一次排序。这样的设计可以使得排序过程更加高效,因为随着增量的减小,每次排序所需要的数据交换次数会逐渐减少。

🌠 排序步骤

希尔排序的排序步骤可以分为以下几个阶段:

分组排序:初始时,根据设定的增量将数据分成若干组,对每组数据进行插入排序,使得每组数据都部分有序。
逐步缩小增量:在每一轮排序后,逐步减小增量的值,重新分组并进行插入排序,直到增量为1。
最后一次排序:当增量为1时,整个数组被视为一组,对整个数组进行插入排序,使得整个数组有序。

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

代码实现:

// 预排序  -- 目标:接近有序  gap > 1
// 插入排序  -- 目标:有序    gap == 1
// O(N^1.3)
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){//gap /= 2;gap = gap/3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

图解三趟:
在这里插入图片描述
在这里插入图片描述

🌉希尔排序的特性总结:

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就
    会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。

时间复杂度分析: O(N^1.3),相比于普通的插入排序有较大的优化。
空间复杂度分析:的空间复杂度为 O(1),即不需要额外的存储空间。
排序稳定性分析:不稳定,即在排序过程中相等元素的相对位置可能发生变化。


🚩总结

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

时间复杂度 O(N^1.3)
空间复杂度的空间复杂度为 O(1)
排序稳定性:不稳定,即在排序过程中相等元素的相对位置可能发生变化。
请添加图片描述

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

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

相关文章

Java复习第十三天学习笔记(HTML),附有道云笔记链接

【有道云笔记】十三 3.29 HTML https://note.youdao.com/s/Ru3zoNqM 一、基本标签 HTML:超文本标记语言 定义页面结构 CSS&#xff1a;层叠样式表 页面显示的样式、排版 BootStrap JS: JavaScript 界面交互(动态交互、逻辑) JQuery <!DOCTYPE html> <html> &l…

体育馆场地预约系统项目管理

1 前言 体育馆作为提供体育活动设施的重要场所&#xff0c;其使用和管理效率对于满足公众需求、提高体育活动质量具有重要意义。然而&#xff0c;传统体育馆场地预约方式仍然存在流程繁琐、效率低下等问题&#xff0c;已无法满足现代社会的需求。旨在提高体育馆的预约和管理效率…

WebGIS开发

1.准备工作 高德开发API注册账号&#xff0c;创建项目拿到key和密钥 高德key 2.通过JS API引入高德API <html><head><meta charset"utf-8" /><meta http-equiv"X-UA-Compatible" content"IEedge" /><metaname&quo…

人工智能 框架 paddlepaddle 飞桨 使用指南 使用例子 线性回归模型demo 1

安装过程&使用指南&线性回归模型 使用例子 本来预想 是安装 到 conda 版本的 11.7的 但是电脑没有gpu 所以 安装过程稍有变动,下面简单讲下 conda create -n paddle_env117 python=3.9 由于想安装11.7版本 py 是3.9 所以虚拟环境名称也是 paddle_env117 activa…

HTTP 与 HTTPS 的区别

基本概念 HTTP&#xff08;HyperText Transfer Protocol&#xff1a;超文本传输协议&#xff09;是一种应用层协议&#xff0c;主要用于在网络上进行信息的传递&#xff0c;特别是用于Web浏览器和服务器之间的通信。 它使用明文方式发送数据&#xff0c;这意味着传输的内容可…

C++中的STL简介与string类

目录 STL简介 STL的版本 STL的六大组件 string类 标准库中的string类 string类的常用接口 string类对象对容量的操作 size()函数与length()函数 capacity()函数 capacity的扩容方式 reserve()函数 resize()函数 string类对象的操作 push_back()函数 append()函数 operator()函数…

LLM推理入门指南②:深入解析KV缓存

在本系列文章《LLM推理入门指南①&#xff1a;文本生成的初始化与解码阶段》中&#xff0c;作者对Transformer解码器的文本生成算法进行了高层次概述&#xff0c;着重介绍了两个阶段&#xff1a;单步初始化阶段&#xff0c;即提示的处理阶段&#xff0c;和逐个生成补全词元的多…

【Go】六、函数

文章目录 1、函数的定义2、内存分析3、注意点4、函数数据类型5、自定义数据类型&#xff08;起别名&#xff09;6、支持对返回值命名 1、函数的定义 语法&#xff1a; func 函数名&#xff08;形参列表)&#xff08;返回值类型列表&#xff09;{执行语句..return 返回值列…

HarmonyOS实战开发-Stage模型下Ability的创建和使用

介绍 本篇Codelab基于Stage模型&#xff0c;对Ability的创建和使用进行讲解。首先在课程中我们将带领大家使用DevEco Studio创建一个Stage模型Ability&#xff0c;并使用UIAbilityContext启动另一个Ability&#xff0c;然后借助Want&#xff0c;在Ability之间传递参数&#xf…

.Net 知识杂记

记录平日中琐碎的.net 知识点。不定期更新 目标框架名称(TFM) 我们创建C#应用程序时&#xff0c;在项目的工程文件(*.csproj)中都有targetFramework标签&#xff0c;以表示项目使用的目标框架 各种版本的TFM .NET Framework .NET Standard .NET5 及更高版本 UMP等 参考文档&a…

云主机8核16G配置租用优惠价格1198元1年、4688元三年

京东云8核16G租用优惠价格1198元1年、4688元三年&#xff0c;配置为8C16G-270G SSD系统盘-5M带宽-500G月流量&#xff0c;华北-北京地域。京东云8核16G服务器活动页面 atengyun.com/go/jd 京东云8核16G租用优惠价格 京东云&#xff1a;轻量云主机CPU内存&#xff1a;8C16G公网带…

从TCP/IP协议到socket编程详解

​ 我的所有学习笔记&#xff1a;https://github.com/Dusongg/StudyNotes⭐⭐⭐ ​ 文章目录 1 网络基础知识1.1 查看网络信息1.2 认识端口号1.3 UDP1.4 TCP1.4.1 确认应答机制1.4.2 TCP三次握手/四次挥手为什么是三次握手为什么是四次挥手listen 的第二个参数 backlog—— 全…

【MySQL探索之旅】MySQL数据表的增删查改——约束

&#x1f4da;博客主页&#xff1a;爱敲代码的小杨. ✨专栏&#xff1a;《Java SE语法》 | 《数据结构与算法》 | 《C生万物》 《MySQL探索之旅》 |《Web世界探险家》 ❤️感谢大家点赞&#x1f44d;&#x1f3fb;收藏⭐评论✍&#x1f3fb;&#xff0c;您的三连就是我持续更…

A Little Is Enough: Circumventing Defenses For Distributed Learning

联邦学习的攻击方法&#xff1a;LIE 简单的总结&#xff0c;只是为了能快速想起来这个方法。 无目标攻击 例如总共50个客户端&#xff0c;有24个恶意客户端&#xff0c;那么这个时候&#xff0c;他需要拉拢2个良性客户端 计算 50 − 24 − 2 50 − 24 0.923 \frac{50-24-2}{…

主干网络篇 | YOLOv8更换主干网络之EfficientNet

前言:Hello大家好,我是小哥谈。EfficientNet是一种高效的卷积神经网络架构,由Mingxing Tan和Quoc V. Le在2019年提出,其设计思想是在不增加计算复杂度的情况下提高模型的准确性。它引入了一个称为"复合系数"的概念,该系数用于同时缩放网络的深度、宽度和分辨率。…

Qt 图形视图 /图形视图框架坐标系统的设计理念和使用方法

文章目录 概述Qt 坐标系统图形视图的渲染过程Item图形项坐标系Scene场景坐标系View视图坐标系map坐标映射场景坐标转项坐标视图坐标转图形项坐标图形项之间的坐标转换 其他 概述 The Graphics View Coordinate System 图形视图坐标系统是Qt图形视图框架的重要组成部分&#xf…

自定义类型:【联合体和枚举】

一.联合体 1.联合体类型的声明 联合体像结构体一样&#xff0c;也是有一个或者多个成员组成&#xff0c;当然也可以不同的类型。但不同的是&#xff0c;比编译器只为最大的成员分配足够的内存空间&#xff0c;所有成员共用同一块内存空间。所以联合体也叫做&#xff1a;共用体…

[Linux初阶]which-find-grep-wc-管道符命令

目录 一.which 二.find a.-name b.-size 三.grep 四.wc 五.管道符(|) 五.总结 一.which 语法格式: which [命令] Linux中的一个个命令,本体上就是一个个的二进制可执行程序(相当于windows中的.exe文件). 在Linux中,一切皆文件. which命令:用于查看指定命令的可执行…

centos 7 安装磐维(PanWeiDB)数据库(单机)

前置环境准备 文件系统环境要求 文件系统环境所要求的扇区必须为512bytes&#xff0c;查看方法如下&#xff1a; [rootdevops-core-highapp3-b-32 ~]#df -h /apps/ [rootdevops-core-highapp3-b-32 ~]#ll /dev/mapper/vg--docker-lvapp [rootdevops-core-highapp3-b-32 ~]#f…

C++命名空间详解

背景 大型程序往往会使用多个独立开发的库&#xff0c;这些库又会定义大量的全局名字&#xff0c;如类、函数和模板等。当应用程序用到多个供应商提供的库时&#xff0c;不可避免地会发生某些名字相互冲突的情况。 多个库将名字放置在全局命名空间中将引发命名空间污染。 传…