当前位置: 首页 > news >正文

八大排序(四)--------直接插入排序

本专栏内容为:八大排序汇总 通过本专栏的深入学习,你可以了解并掌握八大排序以及相关的排序算法。

💓博主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)(n1)/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)(n1)/2次。

如果排序记录是随机的,那么根据概率相同的原则,平均比较和移动次数约为n2/4次。因此,我们得出直接插入排序法的时间复杂度为O(n2)。从这里也看出,同样的O(n2)时间复杂度,直接插入排序法比冒泡和简单选择排序的性能要好一些。

相关文章:

八大排序(四)--------直接插入排序

本专栏内容为&#xff1a;八大排序汇总 通过本专栏的深入学习&#xff0c;你可以了解并掌握八大排序以及相关的排序算法。 &#x1f493;博主csdn个人主页&#xff1a;小小unicorn ⏩专栏分类&#xff1a;八大排序汇总 &#x1f69a;代码仓库&#xff1a;小小unicorn的代码仓库…...

MYSQL--存储引擎和日志管理

存储引擎&#xff1a; 一、存储引擎概念&#xff1a; MySQL中的数据用各种不同的技术存储在文件中&#xff0c;每一种技术都使用不同的存储机制、索引技巧、锁定水平并最终提供不同的功能和能力&#xff0c;这些不同的技术以及配套的功能在MySQL中称为存储引擎。存储引擎是My…...

VUE之更换背景颜色

1. 确定需求 在实现之前&#xff0c;首先需要明确需求&#xff0c;即用户可以通过某种方式更改页面背景颜色&#xff0c;所以我们需要提供一个可操作的控件来实现此功能。 2. 创建Vue组件 为了实现页面背景颜色更换功能&#xff0c;我们可以创建一个Vue组件。下面是一个简单…...

大型集团借力泛微搭建语言汇率时区统一、业务协同的国际化OA系统

国际化、全球化集团&#xff0c;业务遍布全世界&#xff0c;下属公司众多&#xff0c;集团对管理方式和企业文化塑造有着很高的要求。不少大型集团以数字化方式助力全球统一办公&#xff0c;深化企业统一管理。 面对大型集团全球化的管理诉求&#xff0c;数字化办公系统作为集…...

Quartz 建表语句SQL文件

SQL文件在jar里面&#xff0c;github下载 https://github.com/quartz-scheduler/quartz/releases/tag/v2.3.2 解压&#xff0c;sql文件路径&#xff1a;quartz-core\src\main\resources\org\quartz\impl\jdbcjobstore tables_mysql_innodb.sql # # In your Quartz propertie…...

nginx SseEmitter 长连接

1、问题还原&#xff1a; 在做openai机器人时&#xff0c;后台使用 SseEmitterEventSource 实现流式获取数据&#xff0c;前端通过 EventSourcePolyfill 函数接收后端的数据&#xff0c;在页面流式输出到页面&#xff0c;做成逐字打稿的效果。本地测试后&#xff0c;可以正常获…...

若依cloud -【 100 ~ 】

100 分布式日志介绍 | RuoYi 分布式日志就相当于把日志存储在不同的设备上面。比如若依项目中有ruoyi-modules-file、ruoyi-modules-gen、ruoyi-modules-job、ruoyi-modules-system四个应用&#xff0c;每个应用都部署在单独的一台机器里边&#xff0c;应用对应的日志的也单独存…...

VPN协议是如何工作的

VPN&#xff0c;全名 Virtual Private Network&#xff0c;虚拟专用网&#xff0c;就是利用开放的公众网络&#xff0c;建立专用数据传输通道&#xff0c;将远程的分支机构、移动办公人员等连接起来。 VPN 通过隧道技术在公众网络上仿真一条点到点的专线&#xff0c;是通过利用…...

c++::作用域符解析

1&#xff09;当存在具有相同名称的局部变量时&#xff0c;要访问全局变量 2&#xff09;在类之外定义函数。 class A { } void A::func(){ }A a;a.func();3&#xff09;访问一个类的静态变量 class A { static int b; } A::b; 4) 如果两个命名空间中都存在一个具有相同名称的类…...

【电源专题】什么是充电芯片的Shipping Mode(船运模式)

现在越来越多电子产品小型化,手持化,这样就需要电池来为产品供电。但电池供电造成的另一个难题就是产品的续航能力的强与弱。 如果想提升续航能力,有一种方法是提高电池容量。如果电池体积没有变化的情况下,可能使用了新型材料、高级技术来增加电池容量,但这势必会增加电池…...

WebGL笔记: 2D和WebGL坐标系对比和不同的画图方式, 程序对象通信,顶点着色器,片元着色器

WebGL 坐标系 canvas2d画布和webgl画布使用的坐标系都是二维直角坐标系&#xff0c;但它们坐标原点、y 轴的坐标方向&#xff0c;坐标基底都不一样canvas2d 坐标系的原点在左上角, x轴朝右&#xff0c;y轴朝下1个单位的宽就是一个像素的宽&#xff0c;1个单位的高就是一个像素…...

【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码

冒泡排序原理 每次比较两个相邻的元素&#xff0c;将较大的元素交换至右端 冒泡排序执行过程输出效果 冒泡排序实现思路 每次冒泡排序操作都会将相邻的两个元素进行比较&#xff0c;看是否满足大小关系要求&#xff0c;如果不满足&#xff0c;就交换这两个相邻元素的次序&…...

多模块和分布式项目

一、什么是多模块项目 多模块项目是一种软件项目组织结构&#xff0c;其中一个大型项目被分成多个独立的子模块或子项目。每个子模块通常具有自己的功能、目录结构和开发周期&#xff0c;但它们可以协同工作以构建一个完整的应用程序。这种项目结构有助于提高代码的可维护性、…...

AI视频剪辑:批量智剪技巧大揭秘

对于许多内容创作者来说&#xff0c;视频剪辑是一项必不可少的技能。然而&#xff0c;传统的视频剪辑方法需要耗费大量的时间和精力。如今&#xff0c;有一种全新的剪辑方式正在改变这一现状&#xff0c;那就是批量AI智剪。这种智能化的剪辑方式能够让你在短时间内轻松剪辑大量…...

vue项目实现地址自动识别功能

1、安装第三方依赖 npm install address-parse 2、在需要使用的页面引入 import AddressParse from address-parse; 3、在页面上写入静态的html代码&#xff0c;可以输入地址&#xff0c;加上识别的输入框&#xff1b; <div class"auto_address"><van-…...

基于springboot财务管理系统springboot006

大家好✌&#xff01;我是CZ淡陌。一名专注以理论为基础实战为主的技术博主&#xff0c;将再这里为大家分享优质的实战项目&#xff0c;本人在Java毕业设计领域有多年的经验&#xff0c;陆续会更新更多优质的Java实战项目&#xff0c;希望你能有所收获&#xff0c;少走一些弯路…...

C语言-扫雷游戏的实现

&#x1f308;write in front&#x1f308; &#x1f9f8;大家好&#xff0c;我是Aileen&#x1f9f8;.希望你看完之后&#xff0c;能对你有所帮助&#xff0c;不足请指正&#xff01;共同学习交流. &#x1f194;本文由Aileen_0v0&#x1f9f8; 原创 CSDN首发&#x1f412; 如…...

七天学会C语言-第七天(结构体)

1.定义结构体 例 1&#xff1a;把一个学生的信息(包括学号、姓名、性别、住址等 4 项信息) 放在一个结构体变量中&#xff0c;然后输出这个学生的信息。 #include <stdio.h>struct Student {int student_id;char name[30];char gender;char address[60]; };int main() …...

《深度学习工业缺陷检测》专栏介绍 CSDN独家改进实战

&#x1f4a1;&#x1f4a1;&#x1f4a1;深度学习工业缺陷检测 1&#xff09;提供工业小缺陷检测性能提升方案&#xff0c;满足部署条件&#xff1b; 2&#xff09;针对缺陷样品少等难点&#xff0c;引入无监督检测&#xff1b; 3&#xff09;深度学习 C、C#部署方案&#…...

unity 实现双击物体让其隐藏,单击物体让其显示

unity 实现双击物体让其隐藏&#xff0c;单击物体让其显示 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 工程全解析

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

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

EtherNet/IP转DeviceNet协议网关详解

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

【JavaWeb】Docker项目部署

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

分布式增量爬虫实现方案

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

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; 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博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...