啥是插入排序 ?
一、概述
排序是算法中的一部分。所以我们学习排序也是算法的入门,为了能让大家感受到排序是算法的一部分,我举个例子证明一下:比如麻将游戏,发完牌之后需要对手上的牌进行排序,大家想想,麻将排序如何排呢?它有什么特点呢?而且在摸牌打牌的过程中,我们要不断的排序,如何排序呢?选择什么排序算法最快呢?
以上这种情况我们就可以分析选择哪种排序算法更高效。比如下图已经有一副固定顺序的牌了:

此时轮到我们摸牌,摸到的牌如下:

此时,要将这个“三同”放到上面的一副牌中,就存在如下规律:
1、正常“3同”应该放到“2同”和”4同“中间。
2、跟其他花色的牌没有关系,甚至跟”5同“也没有关系。只需要把”3同“放到”2同“和”4同“中间就行。至于”2同”和”4同”在哪里不要紧。
我们前面学习了选择排序,如果使用选择排序对上面这副牌进行排序是否合适呢?显然是不合适的,因为选择排序必须从“七万”开始比较,选择最小牌跟第一张牌交换位置,依次类推。但是此处麻将牌的“3同”跟”七万“没有关系,不需要影响”7万“。所以使用选择排序不合适,因为时间负责度很高;此处使用插入排序会更好,什么是插入排序呢?就是本节需要介绍的内容。
二、插入排序
插入排序属于简单排序的一种,通常指的简单排序只是因为其算法思路比较容易理解,不代表其用途很简单。为了让大家掌握插入排序,我们先看看插入排序的原理。
2.1、插入排序的原理
首先有一个待排序的数组如下:

以上数组中只有一个数字0的顺序需要排列,其他数字的顺序都是对的。这种数组使用插入排序的效率更高,下面介绍此数组使用插入排序的流程。
1、先比较1和2,如果2比1小则交换位置。否则不交换位置。此数组不需要交换位置。

2、再比较2和3,如果3比2小,则交换位置。但是实际3比2大所以不交换位置,保持不变。

3、同理,3和4比较也不需要交换位置,保持不变

4、接来下,4和0比较,0小于4,所以交换位置

交换位置之后的数组如下:

5、因为3的邻居发生变化,所以3和0再次比较,0比3小,交换位置,交换之后的数组如下:

6、依次类推,0分别和2交换位置之后的数组如下:

0再和1交换位置的数组如下:

这样一个数组的顺序就对了,但是循环还没有完成,因为我们刚才仅仅循环到数字4这个位置,数字5还没有比较。
7、最后比较4和5,如果5比4小则交换位置,但是5比4大,所以位置不变。数组循环完毕,最终排序如下:

上面就是插入排序的原理。
2.2、插入排序和选择排序的区别
比如就上面这个例子而言,插入排序是将0从索引为4的位置移动到索引3、2、1、0,最终才算结束。而选择排序是找到最小的值0,直接跟1进行交换,0到1的位置,1到0的位置。大家可以翻看前面关于选择排序的介绍。
三、插入排序的代码实现
以下是java代码的实现:
/** * 插入排序 */ public static void algorithm5(){ //原始数组 int[] array={1,2,3,4,0,5}; //数组的长度 int length=array.length; //对数组进行遍历 for (int i = 0; i < length; i++) { //第二个循环仅仅是将当前数据跟自己左边的数字进行比较,如果小于左边数字则交换位置,否则位置不变。 for (int j = i; j > 0 && array[j]<array[j-1]; j--) { int temp = 0; temp = array[j-1]; array[j-1]=array[j]; array[j]=temp; } } //将排好序的数组打印输出 for (int i = 0; i < length; i++) { System.out.print(array[i]+","); } }
以上是插入排序的java代码实现,代码中的第二个for循环是重点,第二个for循环是只比较当前数据左边的值,如果比左边的值小则交换位置,否则位置不变。
3.1 插入排序的时间复杂度
插入排序的时间复杂度有两种:
1、当数组本身是有序的,比如{1,2,3,4,5},则采用插入排序的时间复杂度是O(n)。原因:如果数组本身是有序,插入排序需要每两个挨着的数字进行比较一次,总共比较N-1次,所以时间复杂度是O(n)。
2、当数组是无序的,最坏的情况下需要比较(n^2)/2次,所以时间复杂度是O(n^2)。
四、总结
根据插入排序的时间复杂度来看,插入排序适合如下类型的数组:
1、数组中的每一个元素距离其最终的位置都不远。比如{1,0,2,3,4,5},这个数组中0最终位置应该是第一个位置,0此时的位置距离第一个位置不远。
2、一个有序的大数组中融入一个小数组。比如有序大数组{1,2,3,4,5,6},融入一个小数组{0,1}。
3、数组中只有几个元素的位置不正确。
上述这三种情况的数组适合使用插入排序算法。打过麻将的同学想想,打麻将过程中不停地摸牌、打牌、整理牌的过程是不是就是一次插入排序呢!
排序是算法的基础,排序的用途很多。看完本节内容之后,大家不妨自己动手写个代码将无需的扑克牌进行排序,看更适合哪种排序算法。
相关文章:
啥是插入排序 ?
一、概述 排序是算法中的一部分。所以我们学习排序也是算法的入门,为了能让大家感受到排序是算法的一部分,我举个例子证明一下:比如麻将游戏,发完牌之后需要对手上的牌进行排序,大家想想,麻将排序如何排呢…...
华为OD机试题 Q2 押题【贪心的商人 or 最大利润】用 C++ 编码,速通
最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧本篇题解:贪心的商人 or 最大利润 题目…...
spring框架注解
3.Spring有哪些常用注解呢? Spring常用注解 Web: Controller:组合注解(组合了Component注解),应用在MVC层(控制层)。 RestController:该注解为一个组合注解,相当于Con…...
前端如何处理文本溢出
前言 在现代网页设计中,文本是网页中最重要的内容之一。然而,当文本超出其容器的大小时,会发生文本溢出的问题。文本溢出不仅会影响网页的视觉效果,还会影响网页的可读性和可用性。在前端开发中,解决文本溢出的问题是…...
vue elementUI select下拉框设置默认值(赋值)失败
vue elementUI select下拉框设置默认值 要为select下拉框设定默认值,只需要把 v-model 绑定的值和你想要选中 option 的 value 值设置一样即可。 下面上代码: html部分代码: <el-select v-model"valuetype" change"ch…...
TensorRT创建Engine并推理engine
1. 验证集数据集 Class Images Labels P R mAP.5 mAP.5:.95: 100%|██████████| 84/all 1000 28423 0.451 0.374 0.376 0.209pedestrians 1000 17833 0.737 0.855 0.88 …...
生成式人工智能所面临的问题有哪些?
在生成式人工智能中工作需要混合技术、创造性和协作技能。通过发展这些技能,您将能够在这个令人兴奋且快速发展的领域应对具有挑战性的问题。 生成式人工智能是指一类机器学习技术,旨在生成与训练数据相似但不完全相同的新数据。 换句话说,…...
代码随想录算法训练营第四十三天 | 1049. 最后一块石头的重量 II、494. 目标和、474. 一和零
打卡第43天,01背包应用。 今日任务 1049.最后一块石头的重量 II494.目标和474.一和零 1049. 最后一块石头的重量 II 有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合,从中选出任意两块石头࿰…...
PostCSS 让js可以处理css
GitHub 中文readmie PostCSS 中文网(建设中) PostCSS 不是样式预处理器 是 CSS 语法转换的工具,但不严格遵循css规范,只要符合css语法规则就可以被处理。这也让提前实现新提案成为可能。 使用 webpack 中使用 postcss-loader …...
【C语言进阶:自定义类型详解】位段
本节重点内容: 什么是位段位段的内存分配位段的跨平台问题位段的应用⚡什么是位段 位段的声明和结构是非常类似的,但是有两个不同: 位段的成员必须是 int、unsigned int 或signed int 。位段的成员名后边有一个冒号和一个数字。 struct A…...
十三、RNN循环神经网络实战
因为我本人主要课题方向是处理图像的,RNN是基本的序列处理模型,主要应用于自然语言处理,故这里就简单的学习一下,了解为主 一、问题引入 已知以前的天气数据信息,进行预测当天(4-9)是否下雨 日期温度气压是否下雨4-…...
五子棋透明棋盘界面设计(C语言)
五子棋透明棋盘设计,漂亮的界面制作。程序设置双人对奕,人机模式,对战演示三种模式。设置悔棋,记录功能,有禁手设置。另有复盘功能设置。 本文主要介绍透明的玻璃板那样的五子棋棋盘的制作。作为界面设计,…...
Redis第六讲 Redis之List底层数据结构实现
List数据结构 List是一个有序(按加入的时序排序)的数据结构,Redis采用quicklist(双端链表) 和 ziplist 作为List的底层实现。可以通过设置每个ziplist的最大容量,quicklist的数据压缩范围,提升数据存取效率 list-max-ziplist-size -2 // 单个ziplist节点最大能存储 8kb ,…...
电子学会2023年3月青少年软件编程python等级考试试卷(四级)真题,含答案解析
目录 一、单选题(共25题,共50分) 二、判断题(共10题,共20分) 三、编程题(共3题,共30分)...
【MATLAB】一篇文章带你了解beatxbx工具箱使用
目录 一篇文章带你了解beatxbx工具箱使用 一篇文章带你了解beatxbx工具箱使用 clc;clear; tic; % step1 初始化 % 个体数量 NIND = 35; % 最大遗传代数 MAXGEN = 180; % 变量的维数 NVAR = 2; % 变量的二进制位数 % 上下界 bounds=[-10 10-10 10]; precision=0.0001; %运算精度…...
【LinuxC Sqlite数据库小项目】基于Sqlite的打卡系统------适合初学者练手的小项目
最近小哥老是想浪,不想好好学习,这不行啊,得想点办法,多少做点努力,于是就自己给自己写了个打卡程序; 该程序基于Sqlite数据库,实现一个简单的打卡功能,该函数具有自动初始化的功能…...
在掌握C#基础上再学习C语言
C#和C语言虽然名字相似,但它们在很多方面都有很大的区别。 首先,C#是一种面向对象的语言,而C语言是过程化的语言。这意味着C#具有更丰富的语言特性,如类、接口、继承和多态性等,而C语言则更侧重于直接对计算机硬件进行…...
HTML5 <body> 标签
HTML <body> 标签 实例 一个简单的 HTML 文档,包含尽可能少的必需的标签: <!DOCTYPE html> <html> <head> <meta charset"utf-8"> <title>文档标题</title> </head><body> 文档内容…...
(链表)反转链表
文章目录前言:问题描述:解题思路:代码实现:总结:前言: 此篇是针对链表的经典练习。 问题描述: 给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1…...
deb文件如何安装到iphone方法分享
Cydia或同类APT管理软件在线安装 Cydia或同类APT管理软件在线安装,这个是最佳的安装方式,因为通常无需考虑依赖关系,但缺点是对网络的要求比较高;命令行中以dpkg-iXXX.deb的形式安装,好处是可以以通配符一次性安装多个deb,而且也可以直接看到脚本的运行状况和安装成功/失…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...
