插入排序的简单理解
详细描述
插入排序的基本思想是:将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增 1 的有序表。
在其实现过程中使用双层循环,外层循环针对除了第一个元素之外的所有元素,内层循环针对当前元素前面的有序表进行待插入位置查找,并进行移动。
选择排序详细的执行步骤如下:
- 从第一个元素开始,该元素可以认为已经被排序;
- 取出下一个元素,在已经排序的元素序列中从后向前扫描;
- 如果该元素(已排序)大于新元素,将该元素移到下一位置;
- 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置;
- 将新元素插入到该位置;
- 重复步骤 2~5。
算法图解

问题解疑
插入排序是原地排序算法吗?
插入排序算法的运行并不需要额外的存储空间,所以空间复杂度是 O(1),也就是说,这是一个原地排序算法。
插入排序是稳定的排序算法吗?
对于值相同的元素,可以选择将后面出现的元素,插入到前面出现元素的后面,这样就可以保持原有的前后顺序不变,所以插入排序是稳定的排序算法。
插入排序的时间复杂度是多少?
最好情况时间复杂度为 O(n);最坏情况时间复杂度为 O(n2);平均时间复杂度为 O(n2)。
代码实现
排序接口
package cn.fatedeity.algorithm.sort; | |
/** | |
* 排序接口 | |
*/ | |
public interface Sort { | |
int[] sort(int[] numbers); | |
} |
排序抽象类
package cn.fatedeity.algorithm.sort; | |
/** | |
* 排序抽象类 | |
*/ | |
public abstract class AbstractSort implements Sort { | |
protected void swap(int[] numbers, int src, int target) { | |
int temp = numbers[src]; | |
numbers[src] = numbers[target]; | |
numbers[target] = temp; | |
} | |
} |
插入排序类
package cn.fatedeity.algorithm.sort; | |
/** | |
* 插入排序类 | |
*/ | |
public class InsertionSort extends AbstractSort { | |
@Override | |
public int[] sort(int[] numbers) { | |
if (numbers.length <= 1) { | |
return numbers; | |
} | |
for (int i = 1; i < numbers.length; i++) { | |
for (int j = i; j > 0; j--) { | |
// 一直交换到顺序相反 | |
if (numbers[j - 1] <= numbers[j]) { | |
break; | |
} | |
this.swap(numbers, j, j - 1); | |
} | |
} | |
return numbers; | |
} | |
} |
相关文章:
插入排序的简单理解
详细描述 插入排序的基本思想是:将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增 1 的有序表。 在其实现过程中使用双层循环,外层循环针对除了第一个元素之外的所有元素,内层循环针对当前元素前面的有序表进行…...
Springboot框架集成Websocket通信方式
Websocket实现了“服务器”主动向“客户端”发送数据,改变了以往通过轮询、长轮训、长连接等方式获取服务器端数据的方式。 一、Websocket有三种不同的用场景,单播、广播和组播; (一)、单播(Unicast) 单播是客户端与服务器之间的“一对一”的连接。是在一个单个的发送…...
将json数据分组
在工作中有时需要根据业务需要,将大量数据进行处理分成几个一组 // 例如要将下方数据进行处理 var stuCount [{"id": "1612321835288","libraryCode": "D","regionCode": "A","positionCode&qu…...
从零开始实现一个C++高性能服务器框架----Socket模块
此项目是根据sylar框架实现,是从零开始重写sylar,也是对sylar丰富与完善 项目地址:https://gitee.com/lzhiqiang1999/server-framework 简介 项目介绍:实现了一个基于协程的服务器框架,支持多线程、多协程协同调度&am…...
ld: library not found for -lcrt0.o
ld: library not found for -lcrt0.o 背景: Mac 系统编译的时候报错 语言:golang 原因: 代码使用了静态编译,-static。stack overflow 上说 This option will not work on Mac OS X unless all libraries (including libgcc.a…...
接口测试和功能测试的区别有哪些?说一些你不知道的知识
目录 接口测试和功能测试的区别 目的 测试范围 测试方法 重要性 编辑 举个例子 对于接口测试 对于功能测试 编辑 总结 接口测试和功能测试是软件测试中的两种常见测试类型,主要用于评估软件系统的质量。尽管这两种测试都是为了评估软件系统的性…...
深度学习实战——不同方式的模型部署(CNN、Yolo)
忆如完整项目/代码详见github:https://github.com/yiru1225(转载标明出处 勿白嫖 star for projects thanks) 目录 系列文章目录 一、实验综述 1.实验工具及及内容 2.实验数据 3.实验目标 4.实验步骤 二、ML/DL任务综述与模型部署知识…...
【论文阅读】GNN阅读笔记
A gentle introduction on gnn 前言 发表在distill的文章 图神经网络在应用上才刚刚开始 搭建了一个GNN playground 什么是图 图是表示实体之间的关系 可以分别表示成点向量、边向量、图向量 图可以分为有向图和无向图 数据是怎么表示成图 图片表示成图: …...
QT常用控件——QTreeWidget(树控件),QTableWidget控件
目录 ★先开个小灶,在此插句话:【有关Halcon与Qt联编变量转换】 QTreeWidget树控件 QTableWidget控件...
为什么学校购买小型数控机床而不是大型工业数控机床?
CNC 机器是计算机控制的设备,可以高精度和准确度地切割、雕刻、钻孔或雕刻各种材料。 它们广泛应用于制造、工程、设计和艺术行业。 CNC 机器具有不同的尺寸和功能,从小型台式机到大型工业机型。 人们可能想知道为什么学校会选择购买小型 CNC 机器而不是…...
【Go自学】一文搞懂Go append方法
我们先看一下append的源码 // The append built-in function appends elements to the end of a slice. If // it has sufficient capacity, the destination is resliced to accommodate the // new elements. If it does not, a new underlying array will be allocated. //…...
【压测】通过Jemeter进行压力测试(超详细)
文章目录背景一、前言二、关于JMeter三、准备工作四、创建测试4.1、创建线程组4.2、配置元件4.3、构造HTTP请求4.4、添加HTTP请求头4.5、添加断言4.6、添加察看结果树4.7、添加Summary Report4.8、测试计划创建完成五、执行测试计划总结背景 通过SpringCloudGateway整合Nacos进…...
C# | 上位机开发新手指南(七)加密算法
上位机开发新手指南(七)加密算法 文章目录上位机开发新手指南(七)加密算法前言加密算法的分类对称加密算法和非对称加密算法流加密算法和块加密算法分组密码和序列密码哈希函数和消息认证码对称加密与非对称对称加密优点缺点对称加…...
实验一 跨VLAN访问
目录 一、按照拓扑图配置VLAN,并实现跨VLAN间的访问。 二、实验环境 三、实验步骤 一、按照拓扑图配置VLAN,并实现跨VLAN间的访问。 1、配置好交换机的VLAN和各个终端的地址,实现各个VLAN内能连通。 2、开启两个交换机的VTY连接࿰…...
通信算法之130:软件无线电-接收机架构
1. 超外差式接收机 2.零中频接收机 3.数字中频接收机...
C++编程大师之路:从入门到精通-C++基础入门
文章目录前言主要内容C基础入门初识C第一个C程序注释变量常量关键字标识符命名规则数据类型整型sizeof关键字实型(浮点型)字符型转义字符字符串型布尔类型 bool数据的输入运算符算术运算符赋值运算符比较运算符逻辑运算符程序流程结构选择结构if语句三目…...
如何在千万级数据中查询 10W 的数据并排序
前言 在开发中遇到一个业务诉求,需要在千万量级的底池数据中筛选出不超过 10W 的数据,并根据配置的权重规则进行排序、打散(如同一个类目下的商品数据不能连续出现 3 次)。 下面对该业务诉求的实现,设计思路和方案优…...
RocketMQ消息文件过期原理
文章目录 消费完后的消息去哪里了?什么时候清理物理消息文件?这样设计带来的好处跳过历史消息的处理所有的消费均是客户端发起Pull请求的,告诉消息的offset位置,broker去查询并返回。但是有一点需要非常明确的是,消息消费后,消息其实并没有物理地被清除,这是一个非常特殊…...
Docker容器理解
目录 目录 一:简单理解操作系统 操作系统: 内核: 内核空间和用户空间: 二:简单理解文件系统 1:什么是文件系统 2:什么是root文件系统 三:docker 1:docker镜像 2&…...
SpringBoot 整合knife4j
文章目录SpringBoot 整合knife4j引入knife4j注解案例knife4j增强功能接口添加作者资源屏蔽访问页面加权控制接口排序分组排序请求参数缓存过滤请求参数禁用调试禁用搜索框SpringBoot 整合knife4j Knife4j是一款基于Swagger 2的在线API文档框架 在Spring Boot中,使…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)
UniApp 集成腾讯云 IM 富媒体消息全攻略(地理位置/文件) 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型,核心实现方式: 标准消息类型:直接使用 SDK 内置类型(文件、图片等)自…...
Axure 下拉框联动
实现选省、选完省之后选对应省份下的市区...
flow_controllers
关键点: 流控制器类型: 同步(Sync):发布操作会阻塞,直到数据被确认发送。异步(Async):发布操作非阻塞,数据发送由后台线程处理。纯同步(PureSync…...
