直接插入排序算法详解
直接插入排序(Straight Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,找到排序位置后,需要将已排序元素逐步向后挪位,为最新元素提供插入空间。
直接插入排序的步骤
- 从第一个元素开始,该元素可以认为已经被排序。
- 取出下一个元素,在已经排序的元素序列中从后向前扫描。
- 如果该元素(已排序)大于新元素,将该元素移到下一位置。
- 重复步骤3,直到找到已排序的元素小于或等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤2~5。
直接插入排序的性能
-
时间复杂度:
- 最好情况(输入数组已经是排序好的):O(n),其中n是数组的长度。
- 最坏情况(输入数组是逆序的):O(n^2)。
- 平均情况:O(n^2)。
-
空间复杂度:O(1),因为它是一种原地排序算法,只需要常量级别的额外空间。
-
稳定性:稳定排序。如果两个相等的元素在排序前的相对顺序和排序后的相对顺序相同,则认为排序是稳定的。在直接插入排序中,如果两个元素相等,则后出现的元素不会移动到先出现的元素之前,因此它是稳定的。
实际应用
尽管直接插入排序在大数据集上效率不高,但由于其实现简单,且在小规模数据或基本有序的数据集上性能良好,因此在某些情况下仍然被使用。此外,它也是其他更复杂排序算法(如希尔排序)的基础。
模板代码:
class Solution {
public:vector<int> sortArray(vector<int>& nums) {int n=nums.size();for(int i=1;i<n;i++){ //对nums[0...n-1]进行直接插入排序if(nums[i-1] > nums[i]){ //需要插入到前面已经排好序的子表中int j,temp=nums[i]; //temp暂存待插入元素for(j=i-1;j>=0 && nums[j]>temp;j--) //将大于temp的元素全部向后移以为,给nums[i]腾出空间nums[j+1]=nums[j];nums[j+1]=temp;}}return nums;}
};
相关文章:
直接插入排序算法详解
直接插入排序(Straight Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排…...
sql手动自增id
有时候在运维处理数据的时候,需要给某张表插入新的记录,那么需要知道最新插入数据的id,并在最新id的基础上加上id增长步长获取新的id,这个过程往往需要现将max出来加1,再手动补充到sql语句中,很麻烦,而且数据多的时候容易出错。有…...
10_TypeScript中的泛型
TypeScript中的泛型) 一、泛型的定义二、泛型函数三、泛型类:比如有个最小堆算法,需要同时支持返回数字和字符串两种类型。通过类的泛型来实现四、泛型接口五、泛型类 --扩展 把类作为参数类型的泛型类1、实现:定义一个 User 的类…...
Unity3D之TextMeshPro使用
文章目录 1. TextMeshPro简介2. TextMeshPro创建3. TextMeshPro脚本中调用4. TextMeshPro字体设置及中文支持过程中出现的一些问题 1. TextMeshPro简介 【官网文档】https://docs.unity.cn/cn/2020.3/Manual/com.unity.textmeshpro.html TextMeshPro 是 Unity 的最终文本解决…...
K8S 上部署 Prometheus + Grafana
文章目录 一、使用 Helm 安装 Prometheus1. 配置源2. 下载 prometheus 包3. 安装 prometheus4. 卸载 二、使用 Helm 安装 Grafana1. 配置源2. 安装 grafana3. 访问4. 卸载 一、使用 Helm 安装 Prometheus 1. 配置源 地址:https://artifacthub.io/packages/helm/pro…...
雷军的逆天改命与顺势而为
雷军年度演讲前,朋友李翔提了一个问题:雷军造车是属于顺势而为还是逆势而为?评论互动区有一个总结,很有意思,叫“顺势逆袭”。 大致意思是产业趋势下小米从手机到IOT再切入汽车,是战略的必然,不…...
Leetcode 11. 盛最多水的容器
Leetcode 11. 盛最多水的容器 Leetcode 11. 盛最多水的容器 一、题目描述二、我的想法 一、题目描述 给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线,使得它们与 x 轴共同构成…...
Java笔试分享
1、设计模式(写>3种常用的设计模式) 设计模式是在软件工程中解决常见问题的经验性解决方案。以下是一些常用的设计模式: 单例模式(Singleton): 意图:确保一个类只有一个实例,并…...
LeetCode:对称的二叉树(C语言)
1、问题概述:给一个二叉树,看是否按轴对称 2、示例 示例 1: 输入:root [1,2,2,3,4,4,3] 输出:true 示例 2: 输入:root [1,2,2,null,3,null,3] 输出:false 3、分析 (1&a…...
Postman中的API Schema验证:确保响应精准无误
Postman中的API Schema验证:确保响应精准无误 在API开发和测试过程中,验证响应数据的准确性和一致性是至关重要的。Postman提供了一个强大的功能——API Schema验证,它允许开发者根据预定义的JSON Schema来检查API响应。本文将详细介绍如何在…...
深入浅出WebRTC—GCC
GoogCcNetworkController 是 GCC 的控制中心,它由 RtpTransportControllerSend 通过定时器和 TransportFeedback 来驱动。GoogCcNetworkController 不断更新内部各个组件的状态,并协调组件之间相互配合,向外输出目标码率等重要参数࿰…...
leetcode日记(49)旋转链表
其实不难,就是根据kk%len判断需要旋转的位置,再将后半段接在前半段前面就行。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : …...
InteliJ IDEA最新2024版下载安装与快速配置激活使用教程+jdk下载配置
第一步:下载ideaIC-2024.1.4 方法1:在线链接 IntelliJ IDEA – the Leading Java and Kotlin IDE (jetbrains.com) 选择社区版进行下载 方法2:百度网盘 链接:https://pan.baidu.com/s/1ydS6krUX6eE_AdW4uGV_6w?pwdsbfm 提取…...
【23】Android高级知识之Window(四) - ThreadedRenderer
一、概述 在上一篇文章中已经讲了setView整个流程中,最开始的addToDisplay和WMS跨进程通信的整个过程做了什么。继文章Android基础知识之Window(二),这算是另外一个分支了,接着讲分析在performTraversals的三个操作中,最后触发pe…...
Java-根据前缀-日期-数字-生成流水号(不重复)
🎈边走、边悟🎈迟早会好 小伙伴们在日常开发时可能会遇到的业务-生成流水号,在企业中可以说是比较常见的需求, 可以采用"前缀日期数字"的方式(ps:此方式是需要用到缓存的)前缀:为了…...
跟李沐学AI:卷积层
从全连接层到卷积 多层感知机十分适合处理表格数据,其中行对应样本,列对应特征。但对于图片等数据,全连接层会导致参数过多。卷积神经网络(convolutional neural networks,CNN)是机器学习利用自然图像中一…...
使用RedisTemplate操作executePipelined
前言 RedisTemplate 是 Spring 提供的用于操作 Redis 的模板类,它封装了 Redis 的连接、连接池等管理,并提供了一系列的操作方法来简化 Redis 的使用。其中,executePipelined 方法是 RedisTemplate 中的一个高级特性,用于支持 Re…...
react-native从入门到实战系列教程一环境安装篇
充分阅读官网的环境配置指南,严格按照他的指导作业,不然你一直只能在web或沙箱环境下玩玩 极快的网络和科学上网,必备其中的一个较好的心理忍受能力,因为上面一点就可以让你放弃坚持不懈,努力尝试 成功效果 三大件 …...
【Gin】精准应用:Gin框架中工厂模式的现代软件开发策略与实施技巧(下)
【Gin】精准应用:Gin框架中工厂模式的现代软件开发策略与实施技巧(下) 大家好 我是寸铁👊 【Gin】精准应用:Gin框架中工厂模式的现代软件开发策略与实施技巧(下)✨ 喜欢的小伙伴可以点点关注 💝 前言 本次文章分为上下两部分&…...
国科大作业考试资料-人工智能原理与算法-2024新编-第十二次作业整理
袋子里面有3个有偏差的硬币a、b和c,抛掷硬币正面朝上的概率分别是20%、60%和80%。从袋子里随机取出一个硬币(3个硬币被取出的概率是相等的),并把取出的硬币抛掷3次,得到抛掷结果依次是X1 , X2和 X3。 a. 画出对应的贝叶斯网络并定义必要的CPT表。 b. 如果抛掷结果是2次正…...
《0基础》学习Python——第二十一讲__网络爬虫/<4>爬取豆瓣电影电影信息
爬取网页数据(获取网页信息全过程) 1、爬取豆瓣电影的电影名称、导演、主演、年份、国家、评价 2、首先我们先爬取页面然后再获取信息 1、爬取网页源码 import requests from lxml import etree if __name__ __main__:#UA伪装head{User-Agent:Mozilla/…...
【C++初阶】string类
【C初阶】string类 🥕个人主页:开敲🍉 🔥所属专栏:C🥭 🌼文章目录🌼 1. 为什么学习string类? 1.1 C语言中的字符串 1.2 实际中 2. 标准库中的string类 2.1 string类 2.…...
RAS--APEI 报错解析流程(2)
RAS--APEI 报错解析流程(1) 除了APEI 中除了GHES会记录错误,在Post过程中的错误通常是通过BERT Table汇报 1.BERT Boot Error Record Table is used to report unhandled errors that occurred in a previous boot,it is reported as a ‘one-time polle…...
微软蓝屏事件对企业数字化转型有什么影响?
引言:从北京时间2024年7月19日(周五)下午2点多开始,全球大量Windows用户出现电脑崩溃、蓝屏死机、无法重启等情况。事发后,网络安全公司CrowdStrike称,收到大量关于Windows电脑出现蓝屏报告,公司…...
【Gin】精准应用:Gin框架中工厂模式的现代软件开发策略与实施技巧(上)
【Gin】精准应用:Gin框架中工厂模式的现代软件开发策略与实施技巧(上) 大家好 我是寸铁👊 【Gin】精准应用:Gin框架中工厂模式的现代软件开发策略与实施技巧(上)✨ 喜欢的小伙伴可以点点关注 💝 前言 本次文章分为上下两部分&…...
浅谈Devops
1.什么是Devops DevopsDev(Development)Ops(Operation) DevOps(Development和Operations的混合词)是一种重视“软件开发人员(Dev)”和“IT运维技术人员(Ops)”…...
大文件分片上传(前端TS实现)
大文件分片上传 内容 一般情况下,前端上传文件就是new FormData,然后把文件 append 进去,然后post发送给后端就完事了,但是文件越大,上传的文件也就越长,如果在上传过程中,突然网络故障,又或者…...
unity2D游戏开发02添加组件移动玩家
添加组件 给PlayGame和EnemyObject添加组件BoxCollider 2D碰撞器,不用修改参数 给PlayGame添加组件Rigibody 2D 设置数据 添加EnemyObject,属性如下 Edit->project setting->Physics 2D 将 y的值改为0 给playerObject添加标签 新建层 将PlayerObj…...
设计模式 之 —— 单例模式
目录 什么是单例模式? 定义 单例模式的主要特点 单例模式的几种设计模式 1.懒汉式:线程不安全 2.懒汉式:线程安全 3.饿汉式 4.双重校验锁 单例模式的优缺点 优点: 缺点: 适用场景: 什么是单例模…...
深入浅出WebRTC—ULPFEC
FEC 通过在发送端添加额外的冗余信息,使接收端即使在部分数据包丢失的情况下也能恢复原始数据,从而减轻网络丢包的影响。在 WebRTC 中,FEC 主要有两种实现方式:ULPFEC 和 FlexFEC,FlexFEC 是 ULPFEC 的扩展和升级&…...
Python从0到100(四十三):数据库与Django ORM 精讲
前言: 零基础学Python:Python从0到100最新最全教程。 想做这件事情很久了,这次我更新了自己所写过的所有博客,汇集成了Python从0到100,共一百节课,帮助大家一个月时间里从零基础到学习Python基础语法、Pyth…...
Redis-主从模式
目录 前言 一.主从节点介绍 二.配置redis主从结构 二.主从复制 四.拓扑结构 五.数据同步 全量复制(Full Sync Replication) 局部复制(Partial Replication) Redis的学习专栏:http://t.csdnimg.cn/a8cvV 前言 …...
加速决策过程:企业级爬虫平台的实时数据分析
摘要 在当今数据驱动的商业环境中,企业如何才能在海量信息中迅速做出精准决策?本文将探讨企业级爬虫平台如何通过实时数据分析加速决策过程,实现数据到决策的无缝衔接。我们聚焦于技术如何赋能企业,提升数据处理效率,…...
字典树(前缀树)数组实现(只能查26个单词)
这段代码实现了一个基于 Trie 树的字典树(Trie)数据结构,用于存储和检索字符串。其中包含以下几个方法. insert(String word): 向 Trie 树中插入一个单词。首先将单词转换为字符数组,然后遍历字符数组,逐个字符在 Trie…...
CTF-pwn-虚拟化-vmmware 前置
文章目录 参考vmware逃逸简介虚拟机和主机通信机制(guest to host)共享内存(弃用)backdoor机制Message_Send和Message_RecvGuestRPC实例RpcOutSendOneRawWork实例 vmware-rpctool info-get guestinfo.ip各个步骤对应的backdoor操作Open RPC channelSend …...
thinkphp8结合layui2.9 图片上传验证
<?php declare (strict_types 1);namespace app\index\validate;use think\Validate;class Upload extends Validate {/*** 定义验证规则* 格式:字段名 > [规则1,规则2...]** var array*/protected $rule [image > fileExt:jpg,png|fileSize:204800|fi…...
农村污水处理难题:探索低成本高效解决方案
农村污水处理难题:探索低成本高效解决方案 农村污水处理作为国家生态文明建设的重要一环,面临着诸多挑战,尤其是技术落后、管理分散、资源匮乏等问题。物联网技术的引入,为解决这些痛点提供了创新途径,实现了对污水处…...
lightningcss介绍及使用
lightningcss介绍及使用 一款使用 rust 编写的 css 解析器,转换器、及压缩器。 特性 特别快:可以在毫秒级别解析、压缩大量的 css 文件,而且比其他工具的打包结果更小给值添加类型:许多其他css解析器会将值解析成一个无类型的 …...
HTTP服务的应用
1、编辑json请求参数; 2、把json发送到服务url,接收服务的返回参数; 3、解析返回参数。 procedure TfrmCustomQuery.btnFullUpdateClick(Sender: TObject); varfrm: TfrmInputQueryConditionEX;b_OK: Boolean;sBeginDate, sEndDate, sJSON…...
uni-app:踩坑路---scroll-view内使用fixed定位,无效的问题
前言: emmm,说起来这个问题整得还挺好笑的,本人在公司内,奋笔疾书写代码,愉快的提交测试的时候,测试跟我说,在苹果手机上你这个样式有bug,我倒是要看看,是什么bug。 安卓…...
MySQL4.索引及视图
1.建库 create database mydb15_indexstu; use mydb15_indexstu;2.建表 2.1 student表学(sno)号为主键,姓名(sname)不能重名,性别(ssex)仅能输入男或女,默认所在系别&a…...
MongoDB - 聚合阶段 $match、$sort、$limit
文章目录 1. $match 聚合阶段1. 构造测试数据2. $match 示例3. $match 示例 2. $sort 聚合阶段1. 排序一致性问题2. $sort 示例 3. $limit 聚合阶段 1. $match 聚合阶段 $match 接受一个指定查询条件的文档。 $match 阶段语法: { $match: { <query> } }$ma…...
ModuleNotFoundError: No module named ‘scrapy.utils.reqser‘
在scrapy中使用scrapy-rabbitmq-scheduler会出现报错 ModuleNotFoundError: No module named scrapy.utils.reqser原因是新的版本的scrapy已经摒弃了该方法,但是scrapy-rabbitmq-scheduler 没有及时的更新,所以此时有两种解决方法 方法一.将scrapy回退至旧版本,找到对应的旧版…...
vue3+ts+vite+electron+electron-packager打包成exe文件
目录 1、创建vite项目 2、添加需求文件 3、根据package.json文件安装依赖 4、打包 5、electron命令运行 6、electron-packager打包成exe文件 Build cross-platform desktop apps with JavaScript, HTML, and CSS | Electron 1、创建vite项目 npm create vitelatest 2、添…...
使用脚本搭建MySQL数据库基础环境
数据库的基本概念 数据(Data) 描述事物的符号记录 包括数字,文字,图形。图像,声音,档案记录等。 以记录形式按统一格式进行存储 表 将不同的记录组织在一起 用来储存具体数据 数据库 表的集合,是…...
Parameter index out of range (2 > number of parameters, which is 1【已解决】
文章目录 1、SysLogMapper.xml添加注释导致的2、解决方法3、总结 1、SysLogMapper.xml添加注释导致的 <!--定义一个查询方法,用于获取日志列表--><!--方法ID为getLogList,返回类型com.main.server.api.model.SysLogModel,参数类型为com.main.se…...
rk3588s 定制版 USB adb , USB2.0与USB3.0 区别,adb 由typeC 转换到USB3.0(第二部分)
硬件资源: rk3588s 核心板定制的地板 软件资源: 网盘上的 android12 源码 1 硬件上 客户只想使用 type c 接口中的 usb2.0 OTG 。在硬件上,甚至连 CC芯片都没有连接。 关于一些前置的知识。 1 USB2.0 与 USB3.0 的区别。 usb3.0 兼容2.0 …...
Cookie与Session 实现登录操作
Cookie Cookie 是网络编程中使用最广泛的一项技术,主要用于辨识用户身份。 客户端(浏览器)与网站服务端通讯的过程如下图所示: 从图中看,服务端既要返回 Cookie 给客户端,也要读取客户端提交的 Cookie。所…...
通过IEC104转MQTT网关轻松接入阿里云平台
随着智能电网和物联网技术的飞速发展,电力系统中的传统IEC 104协议设备正面临向现代化、智能化转型的迫切需求。阿里云作为全球领先的云计算服务提供商,其强大的物联网平台为IEC 104设备的接入与数据处理提供了强大的支持。本文将深入探讨钡铼网关在MQTT…...
lua 游戏架构 之 游戏 AI (五)ai_autofight_find_way
这段Lua脚本定义了一个名为 ai_autofight_find_way 的类,继承自 ai_base 类。 lua 游戏架构 之 游戏 AI (一)ai_base-CSDN博客文章浏览阅读238次。定义了一套接口和属性,可以基于这个基础类派生出具有特定行为的AI组件。例如&…...