排序基础之插入排序
目录
前言
一、什么是插入排序
二、实现插入排序
三、插入排序优化
四、插入排序的特性
前言
上一篇中我们说到了《排序基础之选择排序》,这一篇我们来学习一下排序算法中的另一种基础排序算法——插入排序。
一、什么是插入排序
简单来说就是:每次只处理一个元素,把这个元素插入到前面已经排好序的元素中,即: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…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
django blank 与 null的区别
1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是,要注意以下几点: Django的表单验证与null无关:null参数控制的是数据库层面字段是否可以为NULL,而blank参数控制的是Django表单验证时字…...
通过MicroSip配置自己的freeswitch服务器进行调试记录
之前用docker安装的freeswitch的,启动是正常的, 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...
高考志愿填报管理系统---开发介绍
高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发,采用现代化的Web技术,为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## 📋 系统概述 ### 🎯 系统定…...
