插入排序的简单理解
详细描述
插入排序的基本思想是:将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增 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中,使…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
【记录坑点问题】IDEA运行:maven-resources-production:XX: OOM: Java heap space
问题:IDEA出现maven-resources-production:operation-service: java.lang.OutOfMemoryError: Java heap space 解决方案:将编译的堆内存增加一点 位置:设置setting-》构建菜单build-》编译器Complier...
在Spring Boot中集成RabbitMQ的完整指南
前言 在现代微服务架构中,消息队列(Message Queue)是实现异步通信、解耦系统组件的重要工具。RabbitMQ 是一个流行的消息中间件,支持多种消息协议,具有高可靠性和可扩展性。 本博客将详细介绍如何在 Spring Boot 项目…...
