数据结构进阶篇 之 【插入排序】详细讲解(直接插入排序,希尔排序)

在这里插入图片描述
千万不要因为一件事不会做而失去信心,你又不是只有这一件事不会,你还有很多呢

一、插入排序

1.直接插入排序 InsertSort

1.1 基本思想

1.2 实现原理

1.3 代码实现

1.4 直接插入排序的特性总结

2.希尔排序 ShellSort

2.1 基本思想

2.2 实现原理

2.3 代码实现

2.4希尔排序的特性总结

二、完结撒❀

–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–

一、插入排序

1.直接插入排序

1.1 基本思想

直接插入排序是一种简单的插入排序法,其基本思想是:

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列

实际中我们玩扑克牌时,开始出牌前我们总先把牌都按照大小排列一边,这就用了插入排序的思想
在这里插入图片描述

1.2 实现原理

下面以数组实现升序为例

总体是按照·数组下标由小到大进行排序

对一个数组arr进行排序从第一个位置下标为0开始,与下标为1进行比较:

如果arr[0]>arr[1],将arr[0]后移至arr[1]的位置,再将arr[1]插入arr[0]的位置就完成了排序,再继续向后读取排序即可。
如果arr[0]<arr[1],即为升序,继续向后读取排序即可。

当插入到第i(i>=0)个元素时,前面的arr[0],arr[1]…arr[i-1]都已经排好序,此时将arr[i]对应数值与arr[i-1],arr[i-2]…对应的数值依次进行排序比较,大于arr[i]的数值依次向后移动一个数据位置大小(假设arr[i-1]大于arr[i],就将arr[i-1]后移止arr[i]的位置),arr[i]继续向前进行比较,直到遇到比arr[i]小的数时,将arr[i]插入到其前面位置即可

按照数组下标顺序,以此执行上面操作,直到将数组中最后一个数据排完为止,即可实现升序。

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

1.3 代码实现

//时间复杂度
//最坏情况O(N^2),逆序
//最好情况O(N)
void InsertSort(int* a, int n)
{
	assert(a);

	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];

		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

1.4 直接插入排序的特性总结

1. 元素集合越接近有序,直接插入排序算法的时间效率越高

2. 时间复杂度:O(N^2)

4. 空间复杂度:O(1),它是一种稳定的排序算法

5. 稳定性:稳定

2.希尔排序 ShellSort

2.1 基本思想

希尔排序法又称缩小增量法。希尔排序法的基本思想是:

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

在这里插入图片描述

2.2 实现原理

希尔排序相当于是对直接插入排序进行了优化
直接插入排序就相当于把gap直接当作1进行插入排序,而希尔排序不同

希尔排序分为预排序和最终排序两部进行且开始gap等于数组数据个数n,gap减小到1之前所进行的排序都为预排序,只有最后gap=1时的排序为最终排序

希尔排序之所以快是预排序在起作用,预排序的目标是让整体数组接近有序,而总体预排序消耗的时间又很少,其对最终排序的使用时间有很大增益效果

注意:这里以gap /= 2为例,进行动态图解
动态图解:
在这里插入图片描述

2.3 代码实现

注意:这里代码是以gap = gap/3+1为例,时间复杂度为O(N^1.3)。(具体说明在特性里面)

//希尔排序 时间复杂度O(N^1.3)
//欲排序 目标接近有序
void ShellSort(int* a, int n)
{
	assert(a);

	int gap = n;
	while (gap > 1)
	{
		gap  = gap/3 + 1;
		for (int j = 0; j < gap; j++)
		{
			for (int i = j; i < n - gap; i += gap)
			{
				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;
				}
			}
		}
	}
}

2.4希尔排序的特性总结

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。

3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在一些树中给出的希尔排序的时间复杂度都不固定:

在这里插入图片描述
《数据结构-用面相对象方法与C++描述》— 殷人昆

在这里插入图片描述

因为咱们的gap是按照Knuth提出的方式取值的,而且Knuth进行了大量的试验统计,我们暂时就按照:O(N^1.3)来算。

4.稳定性:不稳定。

二、完结撒❀

如果以上内容对你有帮助不妨点赞支持一下,以后还会分享更多编程知识,我们一起进步。
最后我想讲的是,据说点赞的都能找到漂亮女朋友❤
在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

视觉Transformer和Swin Transformer

视觉Transformer概述 ViT的基本结构&#xff1a; ①输入图片首先被切分为固定尺寸的切片&#xff1b; ②对展平的切片进行线性映射&#xff08;通过矩阵乘法对维度进行变换&#xff09;&#xff1b; ③为了保留切片的位置信息&#xff0c;在切片送入Transformer编码器之前&…

基于vue实现动态table

1、代码 <div style"height: 600px; overflow: scroll;"> <!-- height: 600px; overflow: scroll;作用是超出页面可以滑动 --><div ng-repeat"row in entity.procedureList"><cb-title title"工序{{row.procedireLocation}}&quo…

【保姆级讲解下MySQL中的drop、truncate和delete的区别】

&#x1f308;个人主页:程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…

【面试八股总结】传输控制协议TCP(三)

参考资料 &#xff1a;小林Coding、阿秀、代码随想录 一、TCP拥塞控制⭐ 1. 慢启动 – Slow Start 慢启动是指TCP连接刚建立&#xff0c;一点一点地提速&#xff0c;试探一下网络的承受能力&#xff0c;以免直接扰乱了网络通道的秩序。 慢启动算法&#xff1a; 初始拥塞窗口…

OpenCV项目实战-深度学习去阴影-图像去阴影

往期热门博客项目回顾&#xff1a; 计算机视觉项目大集合 改进的yolo目标检测-测距测速 路径规划算法 图像去雨去雾目标检测测距项目 交通标志识别项目 yolo系列-重磅yolov9界面-最新的yolo 姿态识别-3d姿态识别 深度学习小白学习路线 //正文开始&#xff01; 图…

NoSQL(非关系型数据库)之Redis的简介与安装

一、简介 1.1 关系型数据库与非关系型数据库 1.1.1 概念 1.1.2 区别 1.2 非关系型数据库产生背景 1.3 redis 简介 1.4 redis 优点 1.5 redis 快的原因 二、安装 2.1 关闭核心防护 2.2 安装相关依赖 2.3 解压软件包并进行编译安装 2.4 设置 Redis 服务所需相关配置文…

聚道云软件连接器:助力企业财务效率提升的成功案例

客户介绍 某公司是一家实力雄厚的综合性企业&#xff0c;自成立以来&#xff0c;公司始终秉持着创新、务实、高效的经营理念&#xff0c;深耕多个领域&#xff0c;不断拓展业务版图&#xff0c;逐渐发展成为业界翘楚。公司经营范围广泛&#xff0c;涵盖了科技研发、生产制造、…

【保姆级讲解下Docker容器】

&#x1f308;个人主页:程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…

数据分析:品牌如何借势小红书热点?

导语 近期&#xff0c;一碗麻辣烫&#xff0c;让甘肃天水成为了不少人旅行计划单上的榜首&#xff0c;各地食客心甘情愿地排队5、6个小时&#xff0c;赶赴一场“麻辣烫之约”。千瓜数据&#xff0c;近30天浏览量破500W&#xff0c;且增势迅猛。 图 | 千瓜数据 去有人的地方 &…

YOLOv8全网独家改进: 小目标 | 注意力 |卷积和注意力融合模块(CAFMAttention) | 2024年4月最新成果

💡💡💡本文独家改进:卷积和注意力融合模块(CAFMAttention),增强对全局和局部特征的提取能力,2024年最新的改进思路 💡💡💡创新点:卷积和注意力巧妙设计 💡💡💡如何跟YOLOv8结合:1)放在backbone后增强对全局和局部特征的提取能力;2)放在detect前面,增…

从《布瓦尔与佩库歇》实践中学习社会科学概论

从《布瓦尔与佩库歇》实践中学习社会科学概论 前情提要《布瓦尔与佩库歇》实践笔记云藏山鹰社会科学概论报告核心--信息形数身知™意合™意气实体过程意气实体过程宇宙学诠释™ 社会科学概论花间流风版导读&#xff0c;马斯克风格演讲[ 一尚韬竹团队供稿&#xff1b;] 内容展开…

带合并行、分组表头和分组表格导出excel

目录 一、实现思路 二、实现 1.引入js 2.数据处理。 ​3.合并行&#xff0c;根据vxe-table的span-method方法做合并行和列 4.点击导出按钮&#xff0c;调用导出方法 vue项目里面的一个需求&#xff0c;需要导出一个excel表格&#xff0c;数据源是后端返回的json&#xff…

寻找适合您的舒适防静电鞋:从安全到舒适的选择指南

在工作环境中&#xff0c;我们时常面临着各种各样的安全隐患&#xff0c;其中静电可能是其中之一。静电不仅会给我们带来不便&#xff0c;还可能引发严重的安全问题&#xff0c;甚至导致火灾或爆炸。因此&#xff0c;选择适合的防静电鞋成为了我们十分关注的话题。 舒适性与安…

获取用户位置数据,IP定位离线库助您洞悉消费者需求

获取用户位置数据是现代互联网应用中非常重要的一环。通过获取用户的位置数据&#xff0c;可以了解用户所在的地理位置&#xff0c;从而更好地为用户提供个性化的服务和推荐。而IP归属地离线库就是一种非常有用的工具&#xff0c;可以帮助企业准确地获取用户的位置信息。 IP归…

WebKit揭秘:从内部结构到应用程序开发

文章目录 WebKit结构简介核心模块其他组件多进程架构&#xff08;WebKit2&#xff09; Wekbit做了什么&#xff1f;应用程序如何利用 Webkit WebKit结构简介 WebKit是一个开源的浏览器引擎&#xff0c;它由多个模块组成&#xff0c;这些模块协同工作以提供Web内容的渲染和交互…

电商技术揭秘四:电商平台的物流管理系统

文章目录 引言一、物流管理系统的功能与架构1.1 物流管理系统在电商平台中的作用概述保障订单的及时配送优化库存管理控制运营成本提升客户服务水平支持数据驱动的决策应对市场变化 1.2 订单处理功能分析自动化处理流程订单分配与履行错误检测与处理机制实时订单状态更新订单数…

Hi3861 OpenHarmony嵌入式应用入门--鸿蒙开发环境搭建

目录 简介 准备材料 安装开发环境 配置开发工具和sdk 新建工程 代码编译 简介 本篇将进行hi3861开发环境的搭建&#xff0c;并能够编译默认工程。 准备材料 华为集成开发环境工具DevEco Device Tool 华为集成开发环境IDE DevEco Device Tool下载 | HarmonyOS设备开发 …

C语言 练习题

目录 1.统计二进制中1的个数 方法1 方法2 方法3 2.求两个数二进制中不同位的个数 方法1 方法2 3.打印整数二进制的奇数位和偶数位 4.用“ * ”组成的X形图案 5.根据年份和月份判断天数 6.结语 1.统计二进制中1的个数 【题目内容】 写一个函数返回参数二进制中 1 的个…

C++语言学习(三)——内联函数、auto、for循环、nullptr

1. 内联函数 &#xff08;1&#xff09;概念 以inline修饰的函数叫做内联函数&#xff0c;编译时C编译器会在调用内联函数的地方展开&#xff0c;没有函数调 用建立栈帧的开销&#xff0c;内联函数提升程序运行的效率。 内联函数是一种编译器指令&#xff0c;用于告诉编译器…

开源AGV调度系统OpenTCS中的任务分派器(dispatcher)详解

OpenTCS中的任务分派器dispatcher详解 1. 引言2. 任务分派器(dispatcher)2.1 默认的停车位置选择2.2 可选停车位置属性2.3 默认的充电位置选择2.4 即时运输订单分配 3. 默认任务分派器的配置项4. 参考资料与源码 1. 引言 openTCS是一项著名的开源运输控制系统&#xff0c;我在…