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

【排序】详解插入排序

一、思想

插入排序是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。具体步骤如下,将数组下标为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;}}

相关文章:

【排序】详解插入排序

一、思想 插入排序是通过构建有序序列&#xff0c;对于未排序数据&#xff0c;在已排序序列中从后向前扫描&#xff0c;找到相应位置并插入。具体步骤如下&#xff0c;将数组下标为0的元素视为已经排序的部分&#xff0c;从1开始遍历数组&#xff0c;在遍历的过程中当前元素从…...

Linux开发板移植rz、sz指令实现串口传输文件

一、开发环境 实现开发板和电脑通过串口来收发互传文件。 开发板&#xff1a;NUC980开发板 环境&#xff1a;Ubuntu 22.04.3 LTS 64-bit lrzsz的源码包:例如 lrzsz-0.12.20.tar.gz&#xff0c;下载地址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语句教学系列。在之前的文章中&#xff0c;我们已经学习了如何使用DDL语句来定义和修改数据库的结构&#xff0c;以及如何使用DML语句进行基本的“增删改查”操作。今天&#xff0c;我们将进一步提升技能&#xff0c;探讨DML语句的高级用法&#xff0c;包…...

JavaScript命名标识符规范,JavaScript的for循环与双重for循环

一个合格的前端需要 戳这里领取完整开源项目&#xff1a;【一线大厂前端面试题解析核心总结学习笔记Web真实项目实战最新讲解视频】 哪些能力&#xff1f; 1、三大基础技能&#xff0c;js、css、html这三项技能是前端工程师能力中的基础&#xff0c;任何框架、工具、库都是基于…...

Qt/自定义控件的封装

新建文件&#xff0c;选择Qt设计师界面类 创建空界面 这是自己控件封装的文件&#xff0c;双击跳转到设计界面进行设计 跳转到其他的ui界面&#xff0c;创建一个widget 右键&#xff0c;选择提升为 在提升的类名称输入刚刚创建的类名&#xff0c;添加后选择提升&#xff0c;勾选…...

【硬件相关】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总数量&#xff0c;数量越多&#xff0c;网络越安全 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部署&#xff08;tensorflow/serving&#xff09;过程备忘记录 部署思路&#xff1a;采用Tensorflow自带的serving进模型部署&#xff0c;采用容器docker 1.首先安装docker 下载地址&#xff08;下载windows版本&#xff09;&#xff1a;https://desktop.docke…...

Docker的安装跟基础使用一篇文章包会

目录 国内源安装新版本 1、清理环境 2、配置docker yum源 3、安装启动 4、启动Docker服务 5、修改docker数据存放位置 6、配置加速器 现在我们已经完成了docker的安装和初始配置。以下为基本测试使用 自带源安装的版本太低 docker官方源安装的话速度太慢了 所以本篇文…...

SQL技巧笔记(一):连续3人的连号问题—— LeetCode601.体育馆的人流量

SQL 技巧笔记 前言&#xff1a;我发现大数据招聘岗位上的应聘流程都是需要先进行笔试&#xff0c;其中占比很大的部分是SQL题目&#xff0c;经过一段时间的学习之后&#xff0c;今天开了一个力扣年会员&#xff0c;我觉得我很有必要去多练习笔试题目&#xff0c;这些题目是有技…...

LeetCode 1976.到达目的地的方案数:单源最短路的Dijkstra算法

【LetMeFly】1976.到达目的地的方案数&#xff1a;单源最短路的Dijkstra算法 力扣题目链接&#xff1a;https://leetcode.cn/problems/number-of-ways-to-arrive-at-destination/ 你在一个城市里&#xff0c;城市由 n 个路口组成&#xff0c;路口编号为 0 到 n - 1 &#xff…...

vulnhub-----Hackademic靶机

文章目录 1.C段扫描2.端口扫描3.服务扫描4.web分析5.sql注入6.目录扫描7.写马php反弹shell木马 8.反弹shell9.内核提权 1.C段扫描 kali:192.168.9.27 靶机&#xff1a;192.168.9.25 ┌──(root㉿kali)-[~] └─# arp-scan -l Interface: eth0,…...

十秒学会Ubuntu命令行:从入门到进阶

一、引言 在使用Ubuntu操作系统时&#xff0c;命令行界面&#xff08;CLI&#xff09;是不可或缺的一部分。对于初学者来说&#xff0c;掌握基本的命令行操作可以帮助他们更高效地管理系统和软件。 本文将介绍一些常见的Ubuntu命令以及如何解决与命令行相关的问题。 目录 一、…...

华为智慧教室3.0的晨光,点亮教育智能化变革

“教室外有更大的世界&#xff0c;但世界上没有比教室更伟大的地方。” 我们在求学阶段&#xff0c;都听说过这句话&#xff0c;但往往是在走出校园之后&#xff0c;才真正理解了这句话。为了让走出校园的孩子能够有能力&#xff0c;有勇气探索广阔的世界。我们应该准备最好的教…...

深度学习预测分析API:金融领域的Game Changer

&#x1f680; 引言 在这个AI遍地开花的时代&#xff0c;谁能成为金融领域的真正Game Changer&#xff1f;那必然是是深度学习预测分析API。如大脑般高效运转的系统不仅颠覆了传统操作&#xff0c;更是以无与伦比的速度和精度赋予了金融数据以全新的生命。 &#x1f4bc; 广泛…...

外贸网站做Google SEO 用wordpress模板的优势

易于优化&#xff1a;WordPress模板是专门为搜索引擎优化(SEO)设计的。从一开始&#xff0c;WordPress模板就考虑到了搜索引擎的因素&#xff0c;因此在构建网站时已经考虑了如何优化网站的结构和内容。使用WordPress模板可以简化优化过程&#xff0c;让您的网站更容易被搜索引…...

后端面试题整理-1

1.Maven 依赖传递产生版本冲突怎么解决&#xff1f; 升级或降级依赖版本&#xff1a;通过修改相关依赖的版本号&#xff0c;选择与项目其他依赖兼容的版本。可以通过查看 Maven 依赖树来确定哪些依赖冲突&#xff0c;并找出合适的版本号进行调整。排除依赖&#xff1a;对于特定…...

Python图像处理之光斑分析

文章目录 质心目标截取光斑半径 python图像处理教程&#xff1a;初步&#x1f4f7;插值变换&#x1f4f7;形态学处理&#x1f4f7;滤波 光斑是工程中经常出现的图像数据&#xff0c;其特点是目标明确&#xff0c;分布清晰。对光斑图像的分析&#xff0c;主要包括质心定位、目标…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...