排序基础之插入排序
目录
前言
一、什么是插入排序
二、实现插入排序
三、插入排序优化
四、插入排序的特性
前言
上一篇中我们说到了《排序基础之选择排序》,这一篇我们来学习一下排序算法中的另一种基础排序算法——插入排序。
一、什么是插入排序
简单来说就是:每次只处理一个元素,把这个元素插入到前面已经排好序的元素中,即: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…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
