【数据结构】插入排序——直接插入排序 和 希尔排序

直接插入排序 和 希尔排序

  • 一、直接插入排序
  • 二、直接插入排序的弊端
  • 三、希尔排序
    • (1)对插入排序的联想
    • (2)希尔排序的思路
  • 四、直接插入排序和希尔排序效率对比
      • 1>随机生成10000个数
      • 2>我们随机生成100000个数
      • 3>我们随机生成1000000个数
      • 4>希尔排序的时间复杂度

一、直接插入排序

我们要如何理解直接插入排序呢?

在这里插入图片描述

假设tmp之前的数都被我们拍好了,tmp就是我们要插入的数
让tmp之前的数与tmp进行对比,若比tmp大就将他们向后移动

在这里插入图片描述
当遇到比tmp小的数就将tmp插入到该数的后面
这样能保证tmp所在的位置:
前面是比tmp小的数
后面是比tmp大的数

当走完循环就可以完成排序

动图演示:
在这里插入图片描述

//插入排序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		//保存已经拍好序的前 i 个数的下标
		int end = i;

		//保存要插入的数,一会儿会被覆盖
		int tmp = a[i + 1];

		//单次循环
		while (end >= 0 && a[end] > tmp)
		{
			//若前一个数比 tmp 大则将该数填到后面,t--
			a[end + 1] = a[end--];
		}
		a[end + 1] = tmp;
	}
}

在这里插入图片描述
我们看到我们这里的循环条件是 i < n - 1
因为当 i 为倒数第二个数时
插入的数为倒数第一个数
在这里插入图片描述
代码运行:
在这里插入图片描述

二、直接插入排序的弊端

直接插入排序有什么弊端呢?

我们想如果我们要排一个升序
在这里插入图片描述

1>
数组中是升序排列的数:
那么我们每次进入循环都不需要额外进行移动
也就是不用进入循环,移到次数为 0
那么它的时间复杂度是O(N)

在这里插入图片描述

2>
数组中是降序排列的数:
那么我们每次进入循环都要进行移动
并且假设我们要将第 i 个数插入,移动次数为 i - 1
那么它的时间复杂度是O(N ^ 2)

所以直接插入排序的效率是很不稳定的

三、希尔排序

(1)对插入排序的联想

但是插入排序真的不可取吗?
插入排序在最好的情况时间复杂度时O(N)
但是插入排序的效率受到数组原顺序的影响很大
假如要拍一个升序,而最大的数在第一位
那么最大的这个数要移动的次数很多

那么我们想,如果我们可以让插入排序的时间复杂度接近O(N)
那它的效率一定非常高
所以我们想到:
如果我们可以让原来要移动很多次数的数移动的次数变少,就可以提高它的效率

(2)希尔排序的思路

如果我们想让原来要移动次数很多的数,它的移动次数变少
那么我们就要改变它的移动步子大小
我们把步子的这个大小叫gap
我们假设gap = 3
在这里插入图片描述
进行一次插入
在这里插入图片描述

将 end = i + gap 位置的数插入,使得和 i = 0 位置的数进行交换

最终效果:
在这里插入图片描述
我们发现最大的数原先需要 9 次才能移动到最后
但现在仅仅需要三次就到最后了
这样就使我们的排序效率提高
那我们下一次只要从 i = 1 的位置开始
一直到 i < gap
这样就把整个数组进行了初次排序

我们先来分析一次步子大小为 gap 的排序
下面是一次插入的代码:

//每次跳的步子大小
int gap;
for (int j = 0; j < gap; j++)
{
	//单次排序
	for (int i = j; i < n - gap; i += gap)
	{
		//保存拍好序的前面最后数的下标
		int end = i;

		//保存要插入数的值
		int tmp = a[i + gap];

		//循环
		while (end >= 0 && a[end] > tmp)
		{
			a[end + gap] = a[end];
			end -= gap;
		}
		a[end + gap] = tmp;
	}
}

先看内层:
单次排序开始
每次将 end = i + gap 处的数插入
与 i = 0 进行比较
随后再将 i += gap
相当于将 end = i + gap + gap 处的数插入

那么在什么时候截止呢?
这时我们要往外层看
我们又进行了一层循环
我们设 j = 0 就是第一次开始插入的位置
为了将整个数组都进行该处理
我们每次将 j++
当 j < gap 时就将 0 到 gap - 1 前的数都处理了
也将整个数组都进行了一次 gap 步的排序
如果不理解可以将上面图中 gap = 3 的情况带入理解

那么我们再反过来看 i 的停止条件
以 gap 等于 3 为例
当 i = 1 或者 i = 2 时
再后面 end = i + gap时,会超出范围
在这里插入图片描述

所以当 i < n - gap 时,就可以处理完全部的数

接下来看下面的图:

在这里插入图片描述
在这里插入图片描述
有没有发现什么,是不是当 gap = 1 时两边的代码就一样了

所以我们接下来就要考虑 gap 的取值了
经过人们的研究,人们发现 gap 每次取 1 / 3 时效率最高
所以就有了下面的代码:

//希尔排序
void ShellSort(int* a, int n)
{
	int gap = n - 1;
	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[i + gap];

				//循环
				while (end >= 0 && a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				a[end + gap] = tmp;
			}
		}
	}
}

为什么我们要取 gap 时要 gap / 3 + 1
因为当 gap 等于 2 时,再除 3 会等于 0
那么这个 +1 就是为了使 gap 最终会等于 1
动图演示:
在这里插入图片描述

四、直接插入排序和希尔排序效率对比

1>随机生成10000个数

让直接插入排序和希尔排序进行比较:
在这里插入图片描述
在这里插入图片描述

2>我们随机生成100000个数

在这里插入图片描述

3>我们随机生成1000000个数

在这里插入图片描述
再往后的就不测了,插入排序跑不动了

4>希尔排序的时间复杂度

直接说结论希尔排序的时间时间复杂度为:
O(N ^ 1.3)

很抽象,这个我是不会算,当时听到也感觉惊为天人

在这里插入图片描述

但是我们可以探究一下
第一次 gap 我们的最大交换次数
(gap / 3) * 3 此时gap为n
gap / 3 为组数,而 *3是没组最大的交换次数

第二次 gap 我们的最大交换次数
(gap / 3 / 3)* 3 * 3
理应是这样的对吧?
可是要是真的是这样我们第一次不是白处理了嘛
第一次我们已经将要移动次数较多的数移动到后面了
那这个最大交换次数是不可能的
所以就会变得快

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

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

相关文章

基于Tkinter的深度学习图像处理界面开发(二)

现在很多搞算法的人&#xff0c;跑跑代码&#xff0c;比如训练和测试代码搞得飞溜&#xff0c;但想把算法代码打包成一个软件&#xff0c;比如给它包装一个界面&#xff0c;就不会了&#xff0c;有些人会推荐用qt做界面&#xff0c;但qt的上手难度还是比较高&#xff0c;如果我…

【设计模式】结构型模式(四):组合模式、享元模式

《设计模式之结构型模式》系列&#xff0c;共包含以下文章&#xff1a; 结构型模式&#xff08;一&#xff09;&#xff1a;适配器模式、装饰器模式结构型模式&#xff08;二&#xff09;&#xff1a;代理模式结构型模式&#xff08;三&#xff09;&#xff1a;桥接模式、外观…

Scala 中 set 的实战应用 :图书管理系统

1. 创建书籍集合 首先&#xff0c;我们创建一个可变的书籍集合&#xff0c;用于存储图书馆中的书籍信息。在Scala中&#xff0c;mutable.Set可以用来创建一个可变的集合。 val books mutable.Set("朝花惜拾", "活着") 2. 添加书籍 我们可以使用操作符…

Flink安装和Flink CDC实现数据同步

一&#xff0c;Flink 和Flink CDC 1&#xff0c; Flink Apache Flink是一个框架和分布式处理引擎&#xff0c;用于对无界和有界数据流进行有状态计算。 中文文档 Apache Flink Documentation | Apache Flink 官方文档 &#xff1a;https://flink.apache.org Flink 中文社区…

有什么初学算法的书籍推荐?

对于初学算法的读者&#xff0c;以下是一些值得推荐的书籍&#xff1a; 1、算法超简单&#xff1a;趣味游戏带你轻松入门与实践 作者&#xff1a;童晶 著 推荐理由&#xff1a;本书把趣味游戏应用于算法教学&#xff0c;提升读者的学习兴趣&#xff0c;并通过可视化的图解和动…

【数据结构】堆和二叉树(2)

文章目录 前言一、建堆和堆排序1.堆排序 二、二叉树链式结构的实现1.二叉树的遍历 三、链式二叉树的功能函数1.二叉树结点个数2.二叉树叶子结点个数3.二叉树的高度4.二叉树第k层结点个数5. 二叉树查找值为x的结点6.二叉树销毁 总结 前言 接着上一篇博客&#xff0c;我们继续分…

Ubuntu24.04网络异常与应对方案记录

PS: 参加过408改卷的ZJU ghsongzju.edu.cn 开启嘲讽: 你们知道408有多简单吗&#xff0c;操作系统真实水平自己知道就行&#xff5e;&#xff5e; Requested credits of master in UWSC30&#xff0c;in ZJU24&#xff0c;domestic master is too simple dmesg dmesg 是一个用…

就是这个样的粗爆,手搓一个计算器:弧长计算器

作为程序员&#xff0c;没有合适的工具&#xff0c;就得手搓一个&#xff0c;PC端&#xff0c;移动端均可适用。废话不多说&#xff0c;直接上代码。 HTML: <div class"calculator"><label for"radius">圆的半径 (r)&#xff1a;</label&…

ServletContext介绍

文章目录 1、ServletContext对象介绍1_方法介绍2_用例分析 2、ServletContainerInitializer1_整体结构2_工作原理3_使用案例 3、Spring案例源码分析1_注册DispatcherServlet2_注册配置类3_SpringServletContainerInitializer 4_总结 ServletContext 表示上下文对象&#xff0c;…

【论文复现】MSA+抑郁症模型总结(三)

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀MSA抑郁症模型 热门研究领域&#xff1a;情感计算的横向发展1. 概述2. 论文地址3. 研究背景4. 主要贡献5. 模型结构和代码6. 数据集介绍7. 性…

使用 Umami 部署博客分析工具

Umami 简介 Umami 是一款开源且注重隐私的网站分析工具&#xff0c;可替代 Google Analytics。它提供网站流量和用户行为等见解&#xff0c;但不使用 Cookie 或收集个人数据&#xff0c;符合隐私法规。Umami 轻巧易用&#xff0c;可自行托管。 如果你有自己的博客&#xff0c;…

JAVA笔记 | ResponseBodyEmitter等异步流式接口快速学习

先简单记录下简单使用跟测试&#xff0c;后续再补充具体&#xff0c;最近有用到&#xff0c;简单来说就是后端(服务端)编写个发射器&#xff0c;实现一次请求&#xff0c;一直向前端客户端发射数据&#xff0c;直到发射器执行完毕&#xff0c;模拟ai一句一句回复的效果 Respon…

在IntelliJ IDEA中创建带子模块的SpringBoot工程

前言 在项目开发中&#xff0c;一个工程往往有若干子工程或模块&#xff0c;所以主工程一般是一个容器&#xff0c;本文介绍在IntelliJ IDEA中创建带多模块的SpringBoot工程的详细步骤。 1、首先打开IntellJ IDEA&#xff08;以下简称IDEA&#xff09;,创建一个新项目。假定新…

【LeetCode】每日一题 2024_11_9 设计相邻元素求和服务(构造,哈希)

前言 每天和你一起刷 LeetCode 每日一题~ LeetCode 启动&#xff01; 题目&#xff1a;设计相邻元素求和服务 近几天不知道力扣发什么疯&#xff0c;每日一题出的太抽象了&#xff0c;我题解是写不了一点了 . . . 今天稍微正常了些&#xff0c;就又来更新了~ 代码与解题思路…

如何搭建企业内部知识库?:打造专属智能体,为企业提供高效智能的知识管理

在当今数据爆炸的时代&#xff0c;虽然AI强大&#xff0c;但常规的AI工具或搜索引擎在面对复杂、专业领域的问题时&#xff0c;可能给出模棱两可的回应&#xff0c;无法满足企业精细化的需求。这就是为什么&#xff0c;企业需要一个专属的AI知识库 —— 它不仅能存储你的数据&a…

胶囊网络、MobileNet、坐标注意力机制的应用

文章目录 摘要Abstract1.胶囊网络1.1 动态路由 2.坐标注意力机制3.MobileNet3.1 深度卷积3.2 逐点卷积3.3 深度可分离卷积3.3.1 深度可分离卷积与标准卷积的对比3.3.2 卷积操作的代码实现3.3.2.1 函数原型3.3.2.2 标准卷积3.3.2.3 分组卷积3.3.2.4 深度可分离卷积 3.4 MobileNe…

一个开源、免费(MIT License)、功能强大、可扩展的电动汽车充电控制器和家庭能源管理系统(带私活源码)

项目介绍 evcc是一个开源、免费&#xff08;MIT License&#xff09;、功能强大、可扩展的电动汽车充电控制器和家庭能源管理系统&#xff0c;支持广泛的设备和品牌&#xff0c;提供简单的用户界面和强大的功能。 功能特点 用户界面&#xff1a;简单且清晰的用户界面。 充电器…

Pr 视频过渡:沉浸式视频

效果面板/视频过渡/沉浸式视频 Video Transitions/Immersive Video Adobe Premiere Pro 的视频过渡效果中&#xff0c;沉浸式视频 Immersive Video效果组主要用于 VR 视频剪辑之间的过渡。 自动 VR 属性 Auto VR Properties是所有 VR 视频过渡效果的通用选项。 默认勾选&#x…

[OpenGL]使用OpenGL实现硬阴影效果

一、简介 本文介绍了如何使用OpenGL实现硬阴影效果&#xff0c;并在最后给出了全部的代码。本文基于[OpenGL]渲染Shadow Map&#xff0c;实现硬阴影的流程如下&#xff1a; 首先&#xff0c;以光源为视角&#xff0c;渲染场景的深度图&#xff0c;将light space中的深度图存储…

成都睿明智科技有限公司抖音电商服务效果如何?

在这个短视频风起云涌的时代&#xff0c;抖音电商以其独特的魅力&#xff0c;成为了众多商家竞相追逐的新蓝海。而在这片波澜壮阔的商海中&#xff0c;成都睿明智科技有限公司犹如一艘稳健的航船&#xff0c;引领着无数企业驶向成功的彼岸。今天&#xff0c;就让我们一起揭开成…