八大排序(四)--------直接插入排序
本专栏内容为:八大排序汇总 通过本专栏的深入学习,你可以了解并掌握八大排序以及相关的排序算法。
💓博主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)…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...
小木的算法日记-多叉树的递归/层序遍历
🌲 从二叉树到森林:一文彻底搞懂多叉树遍历的艺术 🚀 引言 你好,未来的算法大神! 在数据结构的世界里,“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的,它…...
spring Security对RBAC及其ABAC的支持使用
RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型,它将权限分配给角色,再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...
【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
Monorepo架构: Nx Cloud 扩展能力与缓存加速
借助 Nx Cloud 实现项目协同与加速构建 1 ) 缓存工作原理分析 在了解了本地缓存和远程缓存之后,我们来探究缓存是如何工作的。以计算文件的哈希串为例,若后续运行任务时文件哈希串未变,系统会直接使用对应的输出和制品文件。 2 …...
【QT控件】显示类控件
目录 一、Label 二、LCD Number 三、ProgressBar 四、Calendar Widget QT专栏:QT_uyeonashi的博客-CSDN博客 一、Label QLabel 可以用来显示文本和图片. 核心属性如下 代码示例: 显示不同格式的文本 1) 在界面上创建三个 QLabel 尺寸放大一些. objectName 分别…...
中国政务数据安全建设细化及市场需求分析
(基于新《政务数据共享条例》及相关法规) 一、引言 近年来,中国政府高度重视数字政府建设和数据要素市场化配置改革。《政务数据共享条例》(以下简称“《共享条例》”)的发布,与《中华人民共和国数据安全法》(以下简称“《数据安全法》”)、《中华人民共和国个人信息…...
