【数据结构】直接插入排序
目录
一、基本思想
二、动图演示
三、思路分析
四、代码实现
五、易错提醒
六、时间复杂度分析
一、基本思想
直接插入排序(Straight Insertion Sort)是一种简单直观的排序算法,其基本思想是:
把待排序的一个记录按其关键码值的大小,从后往前扫描,插入到一个已经排好的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。
生活中我们玩扑克牌以及整理书籍的时候都用到了直接插入排序算法的思想。
二、动图演示

三、思路分析
这里以升序为例:
- 首先要从无序表中取出第一个元素a,确定a的位置序号,跟有序表中最后一个元素进行比较
- 若发现a小于有序表的最后一个元素,则将有序表的最后一个元素放在元素a的位置(这里要先将a用临时变量tmp存放起来,防止被覆盖)
- 然后再让tmp与有序表倒数第二个元素进行比较,以此类推......
- 当a不小于有序表中的某个元素时,则将a放在该元素的下一个位置即可
- 这样就完成了单趟的排序,下一个无序表中的元素重复相同步骤
结合图分析,如下所示:

四、代码实现
下面是升序代码的实现
//n为数据元素个数
void InsertSort(int*a,int n)
{for (int i=0;i<n-1;i++)//这里i不能从1开始{//单趟排序//[0,end]的值有序,end+1处的值插入[0,end],仍保持有序int end = i;int tmp = a[end+1];while (end>=0){if (tmp < a[end]) //注意这里的tmp不能换成a[end+1],因为之前的a[end+1]会被覆盖{a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}
五、易错提醒
为什么要将a[end+1]=tmp写在while循环外面呢?而不是写在else语句里呢?
分析如下:
因为这里会出现两种情况
情况1:当待排的数字不比有序序列的第一个元素小的时候,那就可以将a[end+1]=tmp;写在else语句里
情况2:当待排的数字比有序序列的第一个元素小的时候,也就是如下图情况:

经过上图分析可知,我们其实可以将代码写成如下形式:
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]) {a[end + 1] = a[end];end--;}else{a[end + 1] = tmp;break;}}if (end == -1){a[end + 1] = tmp;}}
}
该代码是把情况1和情况2分开来写,这种写法更易于理解
而将a[end+1]=tmp写在while循环外面是把两种情况写在了一起,使得代码更加简洁高效。
六、时间复杂度分析
最好情况下的时间复杂度是:O(N)
最坏情况下的时间复杂度是:O(N^2)
分析过程如下图所示:

相关文章:
【数据结构】直接插入排序
目录 一、基本思想 二、动图演示 三、思路分析 四、代码实现 五、易错提醒 六、时间复杂度分析 一、基本思想 直接插入排序(Straight Insertion Sort)是一种简单直观的排序算法,其基本思想是: 把待排序的一个记录按其关键码…...
JavaScript 实现虚拟滚动技术
虚拟滚动 虚拟滚动(有时称为 虚拟列表、虚拟滚动条)是 JavaScript 中的一种技术,旨在优化大数据量的列表渲染,尤其是当有成千上万的数据项时,直接渲染整个列表会导致性能问题。虚拟列表通过只渲染用户视口中可见的那一…...
【重学 MySQL】十八、逻辑运算符的使用
【重学 MySQL】十八、逻辑运算符的使用 AND运算符OR运算符NOT运算符异或运算符使用 XOR 关键字使用 BIT_XOR() 函数注意事项 注意事项 在MySQL中,逻辑运算符是构建复杂查询语句的重要工具,它们用于处理布尔类型的数据,进行逻辑判断和组合条件…...
关于 QImage原始数据格式与cv::Mat原始数据进行手码数据转换 的解决方法
若该文为原创文章,转载请注明原文出处 本文章博客地址:https://hpzwl.blog.csdn.net/article/details/141996117 长沙红胖子Qt(长沙创微智科)博文大全:开发技术集合(包含Qt实用技术、树莓派、三维、OpenCV…...
前端WebSocket客户端实现
// 创建WebSocket连接 var socket new WebSocket(ws://your-spring-boot-server-url/websocket-endpoint);// 连接打开时触发 socket.addEventListener(open, function (event) {socket.send(JSON.stringify({type: JOIN, room: general})); });// 监听从服务器来的消息 socke…...
读取realsense d455双目及imu
问题定义 实时读取realsense数据喂给slam系统 代码 /** rs_d455设备 */#include <librealsense2/rs.hpp> #include <iostream>#include "rs_common_device.h"// opencv #include <opencv2/opencv.hpp>class RsD455Device: public rsCmmonDevice…...
浮点的运算
浮点数表示: N 尾数 * 基数指数 1.25 X 106 尾数一般用补码,指数一般用移码 在IEEE745中尾数可以是原码。 尾数可以表示数值的有效精度,位数越多精度越高 阶码的位数决定数的表示范围,位数越多,范围越大 对阶时&…...
对随机游走问题的分析特定行为模式的建模
从一段随机游走的数据中寻找特定的行为模式,这种问题涉及 序列模式识别 或 序列分析。处理这种问题的算法选择取决于你要找的模式的具体性质和复杂性。以下是几种可能的算法: 隐马尔可夫模型(HMM) 隐马尔可夫模型特别适合处理随…...
JVM面试(七)G1垃圾收集器剖析
概述 上一章我们说了,G1收集器,它属于里程碑式的发展,开创了面向局部收集垃圾的概念。专门针对多核处理器以及大内存的机器。在JDK9中,更是呗指定为官方的GC收集器。满足高吞吐的通知满足GC的STW停顿时间尽可能的短。 虽然现在我…...
php转职golang第一期
入局golang 基础语法:学习 Go 语言的基本语法、数据类型、流程控制等。 数据结构与算法:掌握常用的数据结构和算法。 Web 开发基础:了解 HTTP 协议、Web 开发的基本概念。 Gin 框架或其他 Web 框架:深入学习使用一种 Go 的 Web…...
java后端服务监控与告警:Prometheus与Grafana集成
Java后端服务监控与告警:Prometheus与Grafana集成 大家好,我是微赚淘客返利系统3.0的小编,是个冬天不穿秋裤,天冷也要风度的程序猿! 在现代的微服务架构中,监控和告警是确保服务稳定性的关键组成部分。Pr…...
【系统架构设计师】工厂方法设计模式
工厂方法(Factory Method)模式是一种创建型设计模式,它定义了一个用于创建对象的接口,但让子类决定要实例化的类是哪一个。工厂方法让类的实例化延迟到子类中进行。 工厂方法模式的主要角色 产品(Product):定义工厂的创建对象的接口。具体产品(Concrete Product):实…...
怎样解决OpenEuler下载sdl2失败
OpenEuler 下载 sdl2失败 解决办法(使用wget中git上下载) wget https://github.com/libsdl-org/SDL/releases/download/release-2.30.6/SDL2-2.30.6.tar.gz使用yum下载,下载的最后说找不到这样的库(no match)使用 apt-get,说找不到apt-get使用curl冲gi…...
基于Python的自然语言处理系列(2):Word2Vec(负采样)
在本系列的第二篇文章中,我们将继续探讨Word2Vec模型,这次重点介绍负采样(Negative Sampling)技术。负采样是一种优化Skip-gram模型训练效率的技术,它能在大规模语料库中显著减少计算复杂度。接下来,我们将…...
每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟
每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五…...
大数据之Flink(六)
17、Flink CEP 17.1、概念 17.1.1、CEP CEP是“复杂事件处理(Complex Event Processing)”的缩写;而 Flink CEP,就是 Flink 实现的一个用于复杂事件处理的库(library)。 总结起来,复杂事件处…...
设计模式学习[5]---装饰模式
文章目录 前言1. 原理阐述2. 举例2.1 人装饰方案一2.2 人装饰方案二2.3 人装饰方案三 总结 前言 近期在给一个已有的功能拓展新功能时,基于原有的设计类图进行讨论。其中涉及到了装饰模式,因为书本很早已经看过一遍,所以谈及到这个名词的时候…...
3.C_数据结构_栈
概述 什么是栈: 栈又称堆栈,是限定在一段进行插入和删除操作的线性表。具有后进先出(LIFO)的特点。 相关名词: 栈顶:允许操作的一端栈底:不允许操作的一端空栈:没有元素的栈 栈的作用: 可…...
Debian11安装DolphinScheduler
安装地址 前置准备工作 JDK安装 下载JDK (1.8),安装并配置 JAVA_HOME 环境变量,并将其下的 bin 目录追加到 PATH 环境变量中。如果你的环境中已存在,可以跳过这步 二进制包安装DolphinScheduler 依赖 apt-get install psmisc 二进制安…...
C语言深度剖析--不定期更新的第五弹
const关键字 来看一段代码: #include <stdio.h> int main() {int a 10;a 20;printf("%d\n", a);return 0; }运行结果如下: 接下来我们在上面的代码做小小的修改: #include <stdio.h> int main() {const int a 1…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
