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

插入排序的简单理解

详细描述

插入排序的基本思想是:将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增 1 的有序表。

在其实现过程中使用双层循环,外层循环针对除了第一个元素之外的所有元素,内层循环针对当前元素前面的有序表进行待插入位置查找,并进行移动。

选择排序详细的执行步骤如下:

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  4. 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置;
  6. 重复步骤 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;
}
}

 

相关文章:

插入排序的简单理解

详细描述 插入排序的基本思想是&#xff1a;将一个记录插入到已经排好序的有序表中&#xff0c;从而得到一个新的、记录数增 1 的有序表。 在其实现过程中使用双层循环&#xff0c;外层循环针对除了第一个元素之外的所有元素&#xff0c;内层循环针对当前元素前面的有序表进行…...

Springboot框架集成Websocket通信方式

Websocket实现了“服务器”主动向“客户端”发送数据,改变了以往通过轮询、长轮训、长连接等方式获取服务器端数据的方式。 一、Websocket有三种不同的用场景,单播、广播和组播; (一)、单播(Unicast) 单播是客户端与服务器之间的“一对一”的连接。是在一个单个的发送…...

将json数据分组

在工作中有时需要根据业务需要&#xff0c;将大量数据进行处理分成几个一组 // 例如要将下方数据进行处理 var stuCount [{"id": "1612321835288","libraryCode": "D","regionCode": "A","positionCode&qu…...

从零开始实现一个C++高性能服务器框架----Socket模块

此项目是根据sylar框架实现&#xff0c;是从零开始重写sylar&#xff0c;也是对sylar丰富与完善 项目地址&#xff1a;https://gitee.com/lzhiqiang1999/server-framework 简介 项目介绍&#xff1a;实现了一个基于协程的服务器框架&#xff0c;支持多线程、多协程协同调度&am…...

ld: library not found for -lcrt0.o

ld: library not found for -lcrt0.o 背景&#xff1a; Mac 系统编译的时候报错 语言&#xff1a;golang 原因&#xff1a; 代码使用了静态编译&#xff0c;-static。stack overflow 上说 This option will not work on Mac OS X unless all libraries (including libgcc.a…...

接口测试和功能测试的区别有哪些?说一些你不知道的知识

目录 接口测试和功能测试的区别 目的 测试范围 测试方法 重要性 ​编辑 举个例子 对于接口测试 对于功能测试 ​编辑 总结 接口测试和功能测试是软件测试中的两种常见测试类型&#xff0c;主要用于评估软件系统的质量。尽管这两种测试都是为了评估软件系统的性…...

深度学习实战——不同方式的模型部署(CNN、Yolo)

忆如完整项目/代码详见github&#xff1a;https://github.com/yiru1225&#xff08;转载标明出处 勿白嫖 star for projects thanks&#xff09; 目录 系列文章目录 一、实验综述 1.实验工具及及内容 2.实验数据 3.实验目标 4.实验步骤 二、ML/DL任务综述与模型部署知识…...

【论文阅读】GNN阅读笔记

A gentle introduction on gnn 前言 发表在distill的文章 图神经网络在应用上才刚刚开始 搭建了一个GNN playground 什么是图 图是表示实体之间的关系 可以分别表示成点向量、边向量、图向量 图可以分为有向图和无向图 数据是怎么表示成图 图片表示成图&#xff1a; …...

QT常用控件——QTreeWidget(树控件),QTableWidget控件

目录 ★先开个小灶,在此插句话:【有关Halcon与Qt联编变量转换】 QTreeWidget树控件 QTableWidget控件...

为什么学校购买小型数控机床而不是大型工业数控机床?

CNC 机器是计算机控制的设备&#xff0c;可以高精度和准确度地切割、雕刻、钻孔或雕刻各种材料。 它们广泛应用于制造、工程、设计和艺术行业。 CNC 机器具有不同的尺寸和功能&#xff0c;从小型台式机到大型工业机型。 人们可能想知道为什么学校会选择购买小型 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# | 上位机开发新手指南(七)加密算法

上位机开发新手指南&#xff08;七&#xff09;加密算法 文章目录上位机开发新手指南&#xff08;七&#xff09;加密算法前言加密算法的分类对称加密算法和非对称加密算法流加密算法和块加密算法分组密码和序列密码哈希函数和消息认证码对称加密与非对称对称加密优点缺点对称加…...

实验一 跨VLAN访问

目录 一、按照拓扑图配置VLAN&#xff0c;并实现跨VLAN间的访问。 二、实验环境 三、实验步骤 一、按照拓扑图配置VLAN&#xff0c;并实现跨VLAN间的访问。 1、配置好交换机的VLAN和各个终端的地址&#xff0c;实现各个VLAN内能连通。 2、开启两个交换机的VTY连接&#xff0…...

通信算法之130:软件无线电-接收机架构

1. 超外差式接收机 2.零中频接收机 3.数字中频接收机...

C++编程大师之路:从入门到精通-C++基础入门

文章目录前言主要内容C基础入门初识C第一个C程序注释变量常量关键字标识符命名规则数据类型整型sizeof关键字实型&#xff08;浮点型&#xff09;字符型转义字符字符串型布尔类型 bool数据的输入运算符算术运算符赋值运算符比较运算符逻辑运算符程序流程结构选择结构if语句三目…...

如何在千万级数据中查询 10W 的数据并排序

前言 在开发中遇到一个业务诉求&#xff0c;需要在千万量级的底池数据中筛选出不超过 10W 的数据&#xff0c;并根据配置的权重规则进行排序、打散&#xff08;如同一个类目下的商品数据不能连续出现 3 次&#xff09;。 下面对该业务诉求的实现&#xff0c;设计思路和方案优…...

RocketMQ消息文件过期原理

文章目录 消费完后的消息去哪里了?什么时候清理物理消息文件?这样设计带来的好处跳过历史消息的处理所有的消费均是客户端发起Pull请求的,告诉消息的offset位置,broker去查询并返回。但是有一点需要非常明确的是,消息消费后,消息其实并没有物理地被清除,这是一个非常特殊…...

Docker容器理解

目录 目录 一&#xff1a;简单理解操作系统 操作系统&#xff1a; 内核&#xff1a; 内核空间和用户空间&#xff1a; 二&#xff1a;简单理解文件系统 1&#xff1a;什么是文件系统 2&#xff1a;什么是root文件系统 三&#xff1a;docker 1&#xff1a;docker镜像 2&…...

SpringBoot 整合knife4j

文章目录SpringBoot 整合knife4j引入knife4j注解案例knife4j增强功能接口添加作者资源屏蔽访问页面加权控制接口排序分组排序请求参数缓存过滤请求参数禁用调试禁用搜索框SpringBoot 整合knife4j Knife4j是一款基于Swagger 2的在线API文档框架 在Spring Boot中&#xff0c;使…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...