插入排序的简单理解
详细描述
插入排序的基本思想是:将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增 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中,使…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
