排序基础之插入排序
目录
前言
一、什么是插入排序
二、实现插入排序
三、插入排序优化
四、插入排序的特性
前言
上一篇中我们说到了《排序基础之选择排序》,这一篇我们来学习一下排序算法中的另一种基础排序算法——插入排序。
一、什么是插入排序
简单来说就是:每次只处理一个元素,把这个元素插入到前面已经排好序的元素中,即:arr[0,i)已排好序,arr[i...n)未排序,把arr[i]放到合适的位置,比如:
![]()

实现思想:双层循环,外层循环i从下标0开始遍历,内层循环j从下标i处开始遍历,将下标j和下标j-1处的两个元素进行比较,如果下标j位置处的元素比下标j-1位置处的元素小,则将二者交换位置,然后下标j继续减1向左比较它的前一个元素,直到下标j所在位置元素不大于下标j-1处的元素,则跳出该层循环,依次类推,直至排序完成。
二、实现插入排序
下面我们通过代码来实现这个排序的过程:
public class InsertSort {public static void main(String[] args) {Integer[] arr = {6, 4, 2, 3, 1, 5};InsertSort.sort(arr);for (int ele : arr) {System.out.print(ele + " ");}System.out.println();Student[] students = {new Student("张三", 89),new Student("李四", 98),new Student("王五", 60)};InsertSort.sort(students);for (Student s : students) {System.out.println(s);}}private InsertSort() {}public static <T extends Comparable<T>> void sort(T[] arr) {// 将arr[i]插入到合适的位置for (int i = 0; i < arr.length; i++) {for (int j = i; j - 1 >= 0; j--) {if (arr[j].compareTo(arr[j - 1]) < 0) {swap(arr, j, j - 1);} else {break;}}}}private static <T> void swap(T[] arr, int i, int j) {T temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}
运行结果如下:

三、插入排序优化
同样来看上面说到的这个数组[6,4,2,3,1,5],假如我们要对3这个元素它所在的位置进行排序,当前数组应该是:
![]()
我们上面的实现方式是用3这个元素不断的与它之前的元素进行位置的交换,要知道一次位置交换实际上进行了3次的操作,如果数据量很大的话,这个影响还是有的。现在我们想要对这种方式进行一定的优化,我们可以采用赋值的方式进行优化,思想就是:使用一个变量暂存元素3,然后进行元素比较时,如果前一个元素比3大,则直接把原来3所在位置的元素赋值为6,然后继续再比较前一个元素,直到找到对应的位置之后,将该位置的元素赋值为之前变量暂存的元素,这个流程实际上并未进行元素的交换,而是进行了元素的平移。
下面直接用代码来实现一下:

四、插入排序的特性
从上面的示例及代码中我们可以得到如下特性:
对于有序数组,插入排序的复杂度是O(n)的
但是对于整体来说,插入排序的复杂度仍然是O(n^2)的,有序数组是一种特殊情况
选择排序的复杂度永远是O(n^2)的
OK,到这里我们关于插入排序的内容就介绍的差不多了,下期再会吧!
祝:工作顺利!
相关文章:
排序基础之插入排序
目录 前言 一、什么是插入排序 二、实现插入排序 三、插入排序优化 四、插入排序的特性 前言 上一篇中我们说到了《排序基础之选择排序》,这一篇我们来学习一下排序算法中的另一种基础排序算法——插入排序。 一、什么是插入排序 简单来说就是:每…...
LabVIEW控制DO通道输出一个精确定时的数字波形
LabVIEW控制DO通道输出一个精确定时的数字波形如何使用数据采集板卡的DO通道输出一个精确定时的数字波形?解答:产生一个数字波形首先需要创建一个布尔数组,把波形序列信息放到该布尔数组中,然后通过一个布尔数组至数字转换vi来产生数字波形。…...
openpnp - 零碎记录
文章目录openpnp - 零碎记录概述笔记配置文件保存无效必须在查找问题之后, 才能保存配置文件如果想找出配置动作引起的配置内容变化, 还是要尝试保存后, 比对变化才行ENDopenpnp - 零碎记录 概述 这段时间, 正在配置校准手头的openpnp设备, 用的官网最新的openpnp2.0. 由于o…...
Qt编写微信支付宝支付
文章目录一 微信支付配置参数二 支付宝支付配置参数三 功能四 Demo效果图五 体验地址一 微信支付配置参数 微信支付API,需要三个基本必填参数。 微信公众号或者小程序等的appid;微信支付商户号mchId;微信支付商户密钥mchKey; 具…...
LeetCode 剑指 Offer 64. 求1+2+…+n
求 12…n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。 示例 1: 输入: n 3 输出: 6 限制: 1 < n < 10000 解法一:利用逻辑运算符的短路…...
Mapper代理开发
MyBatis快速开发https://blog.csdn.net/weixin_51882166/article/details/129204439?spm1001.2014.3001.5501 使用Mapper代理方式完成 定义与SQL映射文件同名的Mapper接口 ,将Mapper接口和SQL映射文件放置同一目录结构 新建接口和包: 将Mapper接口和…...
为什么在连接mysql时,设置 SetConnMaxIdleTime 没有作用
目录测试1go 1.15.15go 1.17.12测试2go 1.15.15go 1.17.12参考在使用golang 连接 mysql时,为了节省连接资源,在连接使用过后,希望在指定长度时间不再使用后,自动关闭连接。 这时,经常会使用SetConnMaxLifetime()&#…...
嵌入式开发利器
前言 俗话说,工欲善其事必先利其器,做嵌入式开发首先需要选择好的工具,对的工具,工具选对了能事半功倍,节省很多时间,那些开发大佬一般都会使用各种各样的工具,不同的环节使用不同的工具&#…...
Qt 的QString类的使用
Qt的QString类提供了很方便的对字符串操作的接口。 使某个字符填满字符串,也就是说字符串里的所有字符都有等长度的ch来代替。 QString::fill ( QChar ch, int size -1 ) 例: QString str "Berlin";str.fill(z);// str "zzzzzz"…...
django项目部署(腾讯云服务器centos)
基本步骤: 购买腾讯云服务器并配配置好 >> 本地项目依赖收集准备 >> 上传项目等文件到服务器 >> 服务器安装部署软件和python环境 >> 开始部署(全局来看就这5个步骤) 目录 目录 1. 购买腾讯云服务器并配配置好 …...
计算机网络笔记、面试八股(一)——TCP/IP网络模型
Note:【计算机网络笔记、面试八股】系列文章共计5篇,现已更新3篇,剩余2篇(TCP连接、Web响应)会尽快更新,敬请期待! 本章目录1. TCP/IP网络模型1.1 应用层1.1.1 应用层作用1.1.2 应用层有哪些常用…...
51单片机入门 - 简短的位运算实现扫描矩阵键盘
介绍 例程使用 SDCC 编译、 stcgal 烧录,如果你想要配置一样的环境,可以参考本专栏的第一篇文章“51单片机开发环境搭建 - VS Code 从编写到烧录”,我的设备是 Windows 10,使用普中51单片机开发板(STC89C52RC…...
Mr. Cappuccino的第45杯咖啡——Kubernetes之部署SpringBoot项目
Kubernetes之部署SpringBoot项目创建一个SpringBoot项目将SpringBoot项目打成Jar包使用Dockerfile制作镜像部署SpringBoot项目创建一个SpringBoot项目 pom.xml <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache…...
vscode在远程服务器提交git的时候无需每次都要输入账号密码的配置
要避免在每次 git 操作时都需要输入账号和密码,可以使用 SSH 鉴权,具体步骤如下:生成 SSH key在本地计算机上使用命令 ssh-keygen -t rsa -b 4096 生成 SSH key。这个命令将在 ~/.ssh 目录下生成两个文件:id_rsa 和 id_rsa.pub&am…...
【Spring 基础】
【Spring 基础】 一、 Spring 介绍 1. 简述 Spring 技术是 JavaEE 开发必备技能,企业开发技术选型专业角度 简化开发,降低企业级开发的复杂性 IoCAOP 事务处理 框架整合,高效整合其他技术,提高企业级应用开发与运行效率 MyBat…...
2023年全国最新机动车签字授权人精选真题及答案5
百分百题库提供机动车签字授权人考试试题、机动车签字授权人考试预测题、机动车签字授权人考试真题、机动车签字授权人证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 四、多选题 1.以下哪些气体属于排放污染物(…...
5138: 数字游戏
描述爸爸、妈妈还有YuYu一起玩一个数字游戏,玩家从某个数开始挨个轮流报数,当数字里含有4或7时,不能报出该数字,只能拍一下手。报数的顺序总是从YuYu开始,然后妈妈、爸爸,最后回到YuYu,以此类推…...
阅读笔记9——DenseNet
一、DenseNet DenseNet的网络结构如图1-1所示,其核心是Dense Block模块,Dense Block中的一个黑点就代表一个卷积模块(不是一个卷积层,而是DenseNet提出的一个BottleNeck模块,后文有讲解),每条黑…...
PowerAutomation获取邮件附件并删除这个邮件方法
这个文章是怎么来的呢?现在不是低代码开发平台启蒙阶段嘛?笔者也有幸在工作中进行了尝试,目前也已经在实际工作中结合Python进行了使用,当然,是可以提高IT的工作效率的。需求是这样的,想从公司的EBS平台报表…...
websocket报错集锦-不断更新中
问题1:Failed to construct ‘WebSocket’: An insecure WebSocket connection may not be initiated from a page loaded over HTTPS. 问题描述 Mixed Content: The page at https://AAAAAA.com was loaded over HTTPS, but attempted to connect to the insecur…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
