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

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

💓博主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)时间复杂度,直接插入排序法比冒泡和简单选择排序的性能要好一些。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

uniappAndroid平台签名证书(.keystore)生成

一、安装JRE环境 https://www.oracle.com/java/technologies/downloads/#java8 记住下载默认安装地址。ps&#xff1a;我都默认安装地址C:\Program Files\Java\jdk-1.8 二、安装成功后配置环境变量 系统变量配置 AVA_HOME 放到环境变量去 %JAVA_HOME%\bin 三、生成签名证书…

【开发篇】二、属性绑定与校验

文章目录 1、ConfigurationProperties自定义Bean属性绑定2、EnableConfigurationProperties注解3、ConfigurationProperties第三方Bean属性绑定4、松散绑定5、常用计量单位6、数据校验7、yaml绑定值的坑--关于进制 1、ConfigurationProperties自定义Bean属性绑定 前面读取yaml…

【Python Fastapi】js上传文件,fastapi处理,js显示回传信息

python from fastapi import FastAPI, File, UploadFile, HTTPException from fastapi.staticfiles import StaticFiles from fastapi.responses import HTMLResponse from typing import List import requestsapp FastAPI()# 配置静态文件目录 app.mount("/static"…

【深度学习实验】前馈神经网络(四):自定义逻辑回归模型:前向传播、反向传播算法

目录 一、实验介绍 二、实验环境 1. 配置虚拟环境 2. 库版本介绍 三、实验内容 0. 导入必要的工具包 1. 逻辑回归Logistic类 a. 构造函数__init__ b. __call__(self, x)方法 c. 前向传播forward d. 反向传播backward 2. 模型训练 3. 代码整合 一、实验介绍 实现逻…

YOLOv5、YOLOv8改进:Decoupled Head解耦头

目录 1.Decoupled Head介绍 2.Yolov5加入Decoupled_Detect 2.1 DecoupledHead加入common.py中&#xff1a; 2.2 Decoupled_Detect加入yolo.py中&#xff1a; 2.3修改yolov5s_decoupled.yaml 1.Decoupled Head介绍 Decoupled Head是一种图像分割任务中常用的网络结构&#…

MySQL进阶 —— 超详细操作演示!!!(中)

MySQL进阶 —— 超详细操作演示&#xff01;&#xff01;&#xff01;&#xff08;中&#xff09; 三、SQL 优化3.1 插入数据3.2 主键优化3.3 order by 优化3.4 group by 优化3.5 limit 优化3.6 count 优化3.7 update 优化 四、视图/存储过程/触发器4.1 视图4.2 存储过程4.3 存…

阿里云大数据实战记录10:Hive 兼容模式的坑

文章目录 1、前言2、什么是 Hive 兼容模式&#xff1f;3、为什么要开启 Hive 模式&#xff1f;4、有什么副作用&#xff1f;5、如何开启 Hive 兼容模式&#xff1f;6、该场景下&#xff0c;能不能不开启 Hive 兼容模式&#xff1f;7、为什么不是DATE_FORMAT(datetime, string)&…

【Qt-17】Qt调用matlab生成的dll库

matlab生成dll库 1、matlab示例代码 function BDCube(x,y)[x,y,z] cylinder(x,y);t1 hgtransform;s1 surf(3*x,3*y,4*z,Parent,t1);grid onview(3)shading interp end 2、matlab环境配置 首先检查自己的mcc编译器是否可用&#xff0c;输出以下命令&#xff1a; &#x…

如何在没有第三方.NET库源码的情况,调试第三库代码?

大家好&#xff0c;我是沙漠尽头的狼。 本方首发于Dotnet9&#xff0c;介绍使用dnSpy调试第三方.NET库源码&#xff0c;行文目录&#xff1a; 安装dnSpy编写示例程序调试示例程序调试.NET库原生方法总结 1. 安装dnSpy dnSpy是一款功能强大的.NET程序反编译工具&#xff0c;…

【Java 基础篇】Java线程安全与并发问题详解

多线程编程在Java中是一个常见的需求&#xff0c;它可以提高程序的性能和响应能力。然而&#xff0c;多线程编程也带来了一系列的线程安全与并发问题。在本文中&#xff0c;我们将深入探讨这些问题&#xff0c;以及如何解决它们&#xff0c;适用于Java初学者和基础用户。 什么…

【AI视野·今日NLP 自然语言处理论文速览 第三十六期】Wed, 20 Sep 2023

AI视野今日CS.NLP 自然语言处理论文速览 Wed, 20 Sep 2023 Totally 64 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computation and Language Papers SlimPajama-DC: Understanding Data Combinations for LLM Training Authors Zhiqiang Shen, Tianhua Tao, Li…

原生js值之数据类型详解

js的数据类型 数据类型分类基本数据类型boolean:布尔类undefined:未定义的值null类型数值转换 NumberparseInt 转换整数 parseFloat转换浮点数 String类型特点如何转换成字符串模板字面量字符串插值模板字面量标签函数 symbol类型特性使用 BigInt类型复杂数据类型Object类属性与…

[杂谈]-八进制数

八进制数 文章目录 八进制数1、概述2、八进制数的表示2.1 八进制数2.2 以八进制计数2.3 二进制数补零 3、八进制到十进制转换4、十进制到八进制转换5、二进制到八进制转换示例6、八进制到二进制和十进制转换示例7、总结 1、概述 八进制编号系统是另一种使用基数为8计数系统&am…

【Stm32】【Lin通信协议】Lin通信点亮灯实验

Lin通信点亮灯实验 通过STM32的串口发送数据&#xff0c;然后通过串口转换模块将数据转换成LIN&#xff08;Local Interconnect Network&#xff09;协议&#xff0c;最终控制点亮灯。需要工程和入门资料的可以私信我&#xff0c;看到了马上回。 入门书本推荐&#xff1a; 一…

【C++面向对象侯捷下】2.转换函数 | 3.non-explicit-one-argument ctor

文章目录 operator double() const {} 歧义了 标准库的转换函数

exe文件运行后无输出直接闪退如何找解决办法

一.搜索栏搜事件查看器 二.点开windows日志下的应用程序 三.找到错误处 四.搜索异常代码 点开有错误的详细信息&#xff0c;直接用搜索引擎搜索这个异常代码能大致判断是什么问题&#xff0c;给了一个解决思路&#xff0c;不至于不知道到底哪里出了问题

AUTOSAR词典:CAN驱动Mailbox配置技术要点全解析

AUTOSAR词典&#xff1a;CAN驱动Mailbox配置技术要点全解析 前言 首先&#xff0c;请问大家几个小小问题&#xff0c;你清楚&#xff1a; AUTOSAR框架下的CAN驱动关键词定义吗&#xff1f;是不是有些总是傻傻分不清楚呢&#xff1f;CAN驱动Mailbox配置过程中有哪些关键配置参…

Angular变更检测机制

前段时间遇到这样一个 bug&#xff0c;通过一个 click 事件跳转到一个新页面&#xff0c;新页面迟迟不加载&#xff1b; 经过多次测试发现&#xff0c;将鼠标移入某个 tab &#xff0c;页面就加载出来了。 举个例子&#xff0c;页面内容无法加载&#xff0c;但是将鼠标移入下图…

[面试] k8s面试题 2

文章目录 核心组件1.什么是 Kubernetes 中的控制器&#xff08;Controller&#xff09;&#xff1f;请提供一些常见的控制器类型。2.请解释一下 Kubernetes 中的 Ingress 是什么&#xff0c;以及它的作用。3.如何通过命令行在 Kubernetes 中创建一个 Pod&#xff1f;4.Stateful…

Pdf文件签名检查

如何检查pdf的签名 首先这里有一个已经签名的pdf文件&#xff0c;通过pdf软件可以看到文件的数字签名。 图1为签名后的文件&#xff0c;图2为签名后文件被篡改。 下面就是如何代码检查这里pdf文件的签名 1.引入依赖 <dependency><groupId>org.projectlombok<…