八大排序(四)--------直接插入排序
本专栏内容为:八大排序汇总 通过本专栏的深入学习,你可以了解并掌握八大排序以及相关的排序算法。
💓博主csdn个人主页:小小unicorn
⏩专栏分类:八大排序汇总
🚚代码仓库:小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

前言:
扑克牌是我们几乎每个人都可能玩过的游戏。最基本的扑克玩法都是一边摸牌,一边理牌。假如我们拿到了这样一手牌,如下图所示。啊,似乎是同花顺呀,别急,我们得理一理顺序才知道是否是真的同花顺。请问,如果是你,应该如何理牌呢?

应该说,哪怕你是第一次玩扑克牌,只要认识这些数字,理牌的方法都是不用教的。将3和4移动到5的左侧,再将2移动到最左侧,顺序就算是理好了。这里,我们的理牌方法,就是直接插入排序法。
直接插入排序
- 直接插入排序算法
- 直接插入排序复杂度分析
直接插入排序算法
直接插入排序(Straight insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。
顾名思义,从名称上也可以知道它是一种插入排序的方法。我们来看直接插入排序法的代码。
注意:排序用到的结构与函数在第一部分:排序的基本概念与分类。我们已经实现。详情请点击:八大排序(一)--------排序的基本概念与分类
void Insertsort(SqList * L)/* 对顺序表L作直接插入排序 */
{int i, j;for (i = 2; i <= L->length; i++){if (L->r[i] < L->r[i - 1])/* 需将L->r[i]插入有序子表 */{L->r[0] = L->r[i];/* 设置哨兵 */for (j = i - 1; L->r[j] > L->r[0]; j--){L->r[j + 1] = L->r[j]; /*记录后移 */}L->r[j + 1] = L->r[0];/* 插入到正确位置 */}}
}
(1)程序开始运行,此时我们传入的SqList参数的值length=6,r[6]={0,5,3,4,6,2},其中r[0]=0将用于后面起到哨兵的作用。
(2)第4~13行就是排序的主循环。i从2开始的意思是我们假设r[1]=5已经放好位置,后面的牌其实就是插入到它的左侧还是右侧的问题。
(3)第6行,此时i2,L.r[i]=3比L.r[i-1]-5要小,因此执行第8~11行的操作。第8行,我们将L.r[0]赋值为L.[i]=3的目的是为了起到第9行和第10行的循环终止的判断依据。如下图所示。图中下方的虚线箭头,就是第10行,L.r[j+1]=L.r[j] 的过程,将5右移一位。

(4)此时,第10行就是在移动完成后,空出了空位,然后第11 行L.r[j+1]=L.r[0],将哨兵的3赋值给-0时的L.r[j+1],也就是说,将扑克牌3放置到L.r[I]的位置,如下图所示。

(5)继续循环,第6行,因为此时i=3,L.r[i]=4比L.r[i-1]=5要小,因此执行第8~11行的操作,将5再右移一位,将4放置到当前5所在的位置,如下图所示。

(6)再次循环,此时i4。因为L.r[i]=6比L.r[i-1]=5要大,于是第8~11行代码不执行,此时前三张牌的位置没有变化,如下图所示。

(7)再次循环,此时i=5,因为L.r[i]=2比L.r[i-1]=6要小,因此执行第8~11行的操作。由于6、5、4、3都比2大,它们都将右移一位,将2放置到当前3所在的位置。如下图所示。此时我们的排序也就完成了。

直接插入排序复杂度分析
我们来分析一下这个算法,从空间上来看,它只需要一个记录的辅助空间,因此关键是看它的时间复杂度。
当最好的情况,也就是要排序的表本身就是有序的,比如纸牌拿到后就是{2,3,4,5,6},那么我们比较次数,其实就是代码第6行每个L.r[i]与L.r[i-1]的比较,共比较了(n-1)即( ∑ i = 2 n i \sum_{i=2}^n i ∑i=2ni)次,由于每次都是L.r[i]>L.r[i-1],因此没有移动的记录,时间复杂度为O(n)
当最坏的情况,即待排序表是逆序的情况,比如{6,5,4,3,2),此时需要比较 ∑ i = 2 n = 2 + 3 + . . . + n = ( n + 2 ) ( n − 1 ) / 2 \sum_{i=2}^n =2+3+...+n=(n+2)(n-1)/2 ∑i=2n=2+3+...+n=(n+2)(n−1)/2次,而记录的移动次数也达到最大值 ∑ i = 2 n ( i + 1 ) = ( n + 4 ) ( n − 1 ) / 2 \sum_{i=2}^n (i+1)=(n+4)(n-1)/2 ∑i=2n(i+1)=(n+4)(n−1)/2次。
如果排序记录是随机的,那么根据概率相同的原则,平均比较和移动次数约为n2/4次。因此,我们得出直接插入排序法的时间复杂度为O(n2)。从这里也看出,同样的O(n2)时间复杂度,直接插入排序法比冒泡和简单选择排序的性能要好一些。
相关文章:
八大排序(四)--------直接插入排序
本专栏内容为:八大排序汇总 通过本专栏的深入学习,你可以了解并掌握八大排序以及相关的排序算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:八大排序汇总 🚚代码仓库:小小unicorn的代码仓库…...
MYSQL--存储引擎和日志管理
存储引擎: 一、存储引擎概念: MySQL中的数据用各种不同的技术存储在文件中,每一种技术都使用不同的存储机制、索引技巧、锁定水平并最终提供不同的功能和能力,这些不同的技术以及配套的功能在MySQL中称为存储引擎。存储引擎是My…...
VUE之更换背景颜色
1. 确定需求 在实现之前,首先需要明确需求,即用户可以通过某种方式更改页面背景颜色,所以我们需要提供一个可操作的控件来实现此功能。 2. 创建Vue组件 为了实现页面背景颜色更换功能,我们可以创建一个Vue组件。下面是一个简单…...
大型集团借力泛微搭建语言汇率时区统一、业务协同的国际化OA系统
国际化、全球化集团,业务遍布全世界,下属公司众多,集团对管理方式和企业文化塑造有着很高的要求。不少大型集团以数字化方式助力全球统一办公,深化企业统一管理。 面对大型集团全球化的管理诉求,数字化办公系统作为集…...
Quartz 建表语句SQL文件
SQL文件在jar里面,github下载 https://github.com/quartz-scheduler/quartz/releases/tag/v2.3.2 解压,sql文件路径:quartz-core\src\main\resources\org\quartz\impl\jdbcjobstore tables_mysql_innodb.sql # # In your Quartz propertie…...
nginx SseEmitter 长连接
1、问题还原: 在做openai机器人时,后台使用 SseEmitterEventSource 实现流式获取数据,前端通过 EventSourcePolyfill 函数接收后端的数据,在页面流式输出到页面,做成逐字打稿的效果。本地测试后,可以正常获…...
若依cloud -【 100 ~ 】
100 分布式日志介绍 | RuoYi 分布式日志就相当于把日志存储在不同的设备上面。比如若依项目中有ruoyi-modules-file、ruoyi-modules-gen、ruoyi-modules-job、ruoyi-modules-system四个应用,每个应用都部署在单独的一台机器里边,应用对应的日志的也单独存…...
VPN协议是如何工作的
VPN,全名 Virtual Private Network,虚拟专用网,就是利用开放的公众网络,建立专用数据传输通道,将远程的分支机构、移动办公人员等连接起来。 VPN 通过隧道技术在公众网络上仿真一条点到点的专线,是通过利用…...
c++::作用域符解析
1)当存在具有相同名称的局部变量时,要访问全局变量 2)在类之外定义函数。 class A { } void A::func(){ }A a;a.func();3)访问一个类的静态变量 class A { static int b; } A::b; 4) 如果两个命名空间中都存在一个具有相同名称的类…...
【电源专题】什么是充电芯片的Shipping Mode(船运模式)
现在越来越多电子产品小型化,手持化,这样就需要电池来为产品供电。但电池供电造成的另一个难题就是产品的续航能力的强与弱。 如果想提升续航能力,有一种方法是提高电池容量。如果电池体积没有变化的情况下,可能使用了新型材料、高级技术来增加电池容量,但这势必会增加电池…...
WebGL笔记: 2D和WebGL坐标系对比和不同的画图方式, 程序对象通信,顶点着色器,片元着色器
WebGL 坐标系 canvas2d画布和webgl画布使用的坐标系都是二维直角坐标系,但它们坐标原点、y 轴的坐标方向,坐标基底都不一样canvas2d 坐标系的原点在左上角, x轴朝右,y轴朝下1个单位的宽就是一个像素的宽,1个单位的高就是一个像素…...
【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码
冒泡排序原理 每次比较两个相邻的元素,将较大的元素交换至右端 冒泡排序执行过程输出效果 冒泡排序实现思路 每次冒泡排序操作都会将相邻的两个元素进行比较,看是否满足大小关系要求,如果不满足,就交换这两个相邻元素的次序&…...
多模块和分布式项目
一、什么是多模块项目 多模块项目是一种软件项目组织结构,其中一个大型项目被分成多个独立的子模块或子项目。每个子模块通常具有自己的功能、目录结构和开发周期,但它们可以协同工作以构建一个完整的应用程序。这种项目结构有助于提高代码的可维护性、…...
AI视频剪辑:批量智剪技巧大揭秘
对于许多内容创作者来说,视频剪辑是一项必不可少的技能。然而,传统的视频剪辑方法需要耗费大量的时间和精力。如今,有一种全新的剪辑方式正在改变这一现状,那就是批量AI智剪。这种智能化的剪辑方式能够让你在短时间内轻松剪辑大量…...
vue项目实现地址自动识别功能
1、安装第三方依赖 npm install address-parse 2、在需要使用的页面引入 import AddressParse from address-parse; 3、在页面上写入静态的html代码,可以输入地址,加上识别的输入框; <div class"auto_address"><van-…...
基于springboot财务管理系统springboot006
大家好✌!我是CZ淡陌。一名专注以理论为基础实战为主的技术博主,将再这里为大家分享优质的实战项目,本人在Java毕业设计领域有多年的经验,陆续会更新更多优质的Java实战项目,希望你能有所收获,少走一些弯路…...
C语言-扫雷游戏的实现
🌈write in front🌈 🧸大家好,我是Aileen🧸.希望你看完之后,能对你有所帮助,不足请指正!共同学习交流. 🆔本文由Aileen_0v0🧸 原创 CSDN首发🐒 如…...
七天学会C语言-第七天(结构体)
1.定义结构体 例 1:把一个学生的信息(包括学号、姓名、性别、住址等 4 项信息) 放在一个结构体变量中,然后输出这个学生的信息。 #include <stdio.h>struct Student {int student_id;char name[30];char gender;char address[60]; };int main() …...
《深度学习工业缺陷检测》专栏介绍 CSDN独家改进实战
💡💡💡深度学习工业缺陷检测 1)提供工业小缺陷检测性能提升方案,满足部署条件; 2)针对缺陷样品少等难点,引入无监督检测; 3)深度学习 C、C#部署方案&#…...
unity 实现双击物体让其隐藏,单击物体让其显示
unity 实现双击物体让其隐藏,单击物体让其显示 private float tapThreshold 0.25f; private float tapTimer 0.0f; private bool tap false; private void Update() { if (Input.GetMouseButtonDown(0)) { if (Time.time < this.tapTimer this.tapThreshold)…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...
协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...
redis和redission的区别
Redis 和 Redisson 是两个密切相关但又本质不同的技术,它们扮演着完全不同的角色: Redis: 内存数据库/数据结构存储 本质: 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能: 提供丰…...
Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合
作者:来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布,Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明,Elastic 作为 …...
算术操作符与类型转换:从基础到精通
目录 前言:从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符:、-、*、/、% 赋值操作符:和复合赋值 单⽬操作符:、--、、- 前言:从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...
