八大排序(四)--------直接插入排序
本专栏内容为:八大排序汇总 通过本专栏的深入学习,你可以了解并掌握八大排序以及相关的排序算法。
💓博主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)…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...

【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...

ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...

EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...

【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...

分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...

Rust 开发环境搭建
环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行: rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu 2、Hello World fn main() { println…...

【Linux】自动化构建-Make/Makefile
前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具:make/makfile 1.背景 在一个工程中源文件不计其数,其按类型、功能、模块分别放在若干个目录中,mak…...