【排序】详解插入排序
一、思想
插入排序是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。具体步骤如下,将数组下标为0的元素视为已经排序的部分,从1开始遍历数组,在遍历的过程中当前元素从当前位置开始在已经排序的部分中寻找到合适的位置并插入,直到遍历完整个数组。
二、图解
图解
初识时遍历指针指向下标为1的元素

此时在已排序部分[0 , i - 1]开始寻找合适的位置进行插入,先将i位置的值进行记录,然后开始定义指针在已排序区间寻找

在j从i-1遍历向0的过程中,拿arr[j]与存储的变量t进行比较,因为前部分都是已排序部分,所有在进行比较时会出现两种情况:1》arr[j] > t 说明此时j位置并不是t要插入的位置,这个时候我们可以让j+1的位置修改为arr[j],然后j--继续去比较 2》arr[j] < =t, 此时说明j位置就是t要插入的位置,我们可以结束j的遍历然后让j + 1位置的值更改为t


此时i指针继续向后遍历,j依旧指向i-1向0遍历寻找arr[i]也就是t要插入的位置

i再往后遍历,重复上述过程

这个时候arr[j] > t,于是让arr[j+1]=arr[j]

依旧是arr[j] > t,于是让arr[j+1]=arr[j]



接着i++,继续重复这个过程


说明:上述寻找t的插入位置的过程我们也可以通过二分在已排序的区间中寻找到t该插入的位置,在寻找到t要插入的位置后,在插入t之前,我们要先将t要插入的位置到i-1的区间所有的值都后移一位

三、代码实现
C++
void insert_sort(vector<int>& arr) {for (int i = 1; i < arr.size(); i++) {int j = i - 1, t = arr[i];for (j = i - 1; j >= 0; j--) {if (arr[j] > t) {arr[j + 1] = arr[j];} else {break;}}arr[j + 1] = t;}
}
Java
public static void insertSort(int[] arr) {for (int i = 1; i < arr.length; i++) {int j = i - 1, t = arr[i];for (j = i - 1; j >= 0; j--) {if (arr[j] > t) {arr[j + 1] = arr[j];} else {break;}}arr[j + 1] = t;}}相关文章:
【排序】详解插入排序
一、思想 插入排序是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。具体步骤如下,将数组下标为0的元素视为已经排序的部分,从1开始遍历数组,在遍历的过程中当前元素从…...
Linux开发板移植rz、sz指令实现串口传输文件
一、开发环境 实现开发板和电脑通过串口来收发互传文件。 开发板:NUC980开发板 环境:Ubuntu 22.04.3 LTS 64-bit lrzsz的源码包:例如 lrzsz-0.12.20.tar.gz,下载地址https://ohse.de/uwe/software/lrzsz.html 二、移植步骤 在开发板上移植…...
Android抓包--不走代理的请求Proxy.NO_PROXY,过代理检测,burpsuite+Postern
网上很多不走代理检测的抓包都是charles + Postern 或 charles + Postern + burpsuite,本文使用burpsuite+Postern。 使用无代理 Proxy.NO_PROXY 访问网络接口原理 在Android开发中,大部分的App的网络请求都是基于charles 和 fiddler 来进行抓包的,对网络客户端使用无代理模…...
SQL教学: MySQL进阶操作详解--探索DML语句的高级用法
欢迎回到我们的SQL-DML语句教学系列。在之前的文章中,我们已经学习了如何使用DDL语句来定义和修改数据库的结构,以及如何使用DML语句进行基本的“增删改查”操作。今天,我们将进一步提升技能,探讨DML语句的高级用法,包…...
JavaScript命名标识符规范,JavaScript的for循环与双重for循环
一个合格的前端需要 戳这里领取完整开源项目:【一线大厂前端面试题解析核心总结学习笔记Web真实项目实战最新讲解视频】 哪些能力? 1、三大基础技能,js、css、html这三项技能是前端工程师能力中的基础,任何框架、工具、库都是基于…...
Qt/自定义控件的封装
新建文件,选择Qt设计师界面类 创建空界面 这是自己控件封装的文件,双击跳转到设计界面进行设计 跳转到其他的ui界面,创建一个widget 右键,选择提升为 在提升的类名称输入刚刚创建的类名,添加后选择提升,勾选…...
【硬件相关】RDMA网络类别及基础介绍
文章目录 一、前言1、RDMA网络协议2、TCP/IP网络协议 二、RDMA类别1、IB2、RoCE3、iWARP 三、RDMA对比1、优缺点说明a、性能b、扩展性c、维护难度 2、总结说明 一、前言 roce-vs-infiniband-vs-tcp-ip RoCE、IB和TCP等网络的基本知识及差异对比 分布式存储常见网络协议有TCP/IP…...
POS 之 ETH质押现状
ETH总质押数量趋势图 质押的ETH总数量,数量越多,网络越安全 ETH质押率 质押的ETH数量占总流通数的比率,对ETH价格有积极的影响 ETH总验证人数 质押的总人数,人数越多,说明社区共识越强,活跃度越高 ETH质押日新增质押 新增质押越多说明人们对ETH价格的很乐…...
Qt之插件
插件结构 #mermaid-svg-HMxjwDgwwRejLSQ5 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-HMxjwDgwwRejLSQ5 .error-icon{fill:#552222;}#mermaid-svg-HMxjwDgwwRejLSQ5 .error-text{fill:#552222;stroke:#552222;}#…...
Tensorflow2.0+部署(tensorflow/serving)过程备忘记录Windows
Tensorflow2.0部署(tensorflow/serving)过程备忘记录 部署思路:采用Tensorflow自带的serving进模型部署,采用容器docker 1.首先安装docker 下载地址(下载windows版本):https://desktop.docke…...
Docker的安装跟基础使用一篇文章包会
目录 国内源安装新版本 1、清理环境 2、配置docker yum源 3、安装启动 4、启动Docker服务 5、修改docker数据存放位置 6、配置加速器 现在我们已经完成了docker的安装和初始配置。以下为基本测试使用 自带源安装的版本太低 docker官方源安装的话速度太慢了 所以本篇文…...
SQL技巧笔记(一):连续3人的连号问题—— LeetCode601.体育馆的人流量
SQL 技巧笔记 前言:我发现大数据招聘岗位上的应聘流程都是需要先进行笔试,其中占比很大的部分是SQL题目,经过一段时间的学习之后,今天开了一个力扣年会员,我觉得我很有必要去多练习笔试题目,这些题目是有技…...
LeetCode 1976.到达目的地的方案数:单源最短路的Dijkstra算法
【LetMeFly】1976.到达目的地的方案数:单源最短路的Dijkstra算法 力扣题目链接:https://leetcode.cn/problems/number-of-ways-to-arrive-at-destination/ 你在一个城市里,城市由 n 个路口组成,路口编号为 0 到 n - 1 ÿ…...
vulnhub-----Hackademic靶机
文章目录 1.C段扫描2.端口扫描3.服务扫描4.web分析5.sql注入6.目录扫描7.写马php反弹shell木马 8.反弹shell9.内核提权 1.C段扫描 kali:192.168.9.27 靶机:192.168.9.25 ┌──(root㉿kali)-[~] └─# arp-scan -l Interface: eth0,…...
十秒学会Ubuntu命令行:从入门到进阶
一、引言 在使用Ubuntu操作系统时,命令行界面(CLI)是不可或缺的一部分。对于初学者来说,掌握基本的命令行操作可以帮助他们更高效地管理系统和软件。 本文将介绍一些常见的Ubuntu命令以及如何解决与命令行相关的问题。 目录 一、…...
华为智慧教室3.0的晨光,点亮教育智能化变革
“教室外有更大的世界,但世界上没有比教室更伟大的地方。” 我们在求学阶段,都听说过这句话,但往往是在走出校园之后,才真正理解了这句话。为了让走出校园的孩子能够有能力,有勇气探索广阔的世界。我们应该准备最好的教…...
深度学习预测分析API:金融领域的Game Changer
🚀 引言 在这个AI遍地开花的时代,谁能成为金融领域的真正Game Changer?那必然是是深度学习预测分析API。如大脑般高效运转的系统不仅颠覆了传统操作,更是以无与伦比的速度和精度赋予了金融数据以全新的生命。 💼 广泛…...
外贸网站做Google SEO 用wordpress模板的优势
易于优化:WordPress模板是专门为搜索引擎优化(SEO)设计的。从一开始,WordPress模板就考虑到了搜索引擎的因素,因此在构建网站时已经考虑了如何优化网站的结构和内容。使用WordPress模板可以简化优化过程,让您的网站更容易被搜索引…...
后端面试题整理-1
1.Maven 依赖传递产生版本冲突怎么解决? 升级或降级依赖版本:通过修改相关依赖的版本号,选择与项目其他依赖兼容的版本。可以通过查看 Maven 依赖树来确定哪些依赖冲突,并找出合适的版本号进行调整。排除依赖:对于特定…...
Python图像处理之光斑分析
文章目录 质心目标截取光斑半径 python图像处理教程:初步📷插值变换📷形态学处理📷滤波 光斑是工程中经常出现的图像数据,其特点是目标明确,分布清晰。对光斑图像的分析,主要包括质心定位、目标…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
C++实现分布式网络通信框架RPC(2)——rpc发布端
有了上篇文章的项目的基本知识的了解,现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...
加密通信 + 行为分析:运营商行业安全防御体系重构
在数字经济蓬勃发展的时代,运营商作为信息通信网络的核心枢纽,承载着海量用户数据与关键业务传输,其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级,传统安全防护体系逐渐暴露出局限性&a…...
