排序基础之插入排序
目录
前言
一、什么是插入排序
二、实现插入排序
三、插入排序优化
四、插入排序的特性
前言
上一篇中我们说到了《排序基础之选择排序》,这一篇我们来学习一下排序算法中的另一种基础排序算法——插入排序。
一、什么是插入排序
简单来说就是:每次只处理一个元素,把这个元素插入到前面已经排好序的元素中,即: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…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
Rust 开发环境搭建
环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行: rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu 2、Hello World fn main() { println…...
DeepSeek越强,Kimi越慌?
被DeepSeek吊打的Kimi,还有多少人在用? 去年,月之暗面创始人杨植麟别提有多风光了。90后清华学霸,国产大模型六小虎之一,手握十几亿美金的融资。旗下的AI助手Kimi烧钱如流水,单月光是投流就花费2个亿。 疯…...
