排序算法之——直接插入排序
直接插入排序——以升序排列为例
- 1.1基本思想
- 1.2动态图示感知
- 1.3静态图示详解
- 1.4代码实现
- 1.5时间复杂度
- 1.5.1最好情况
- 1.5.2最差情况
- 1.6空间复杂度
- 1.7稳定性
- 1.7.1一个小问题
1.1基本思想
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。实际中我们玩扑克牌时,就用了插入排序的思想。

1.2动态图示感知

1.3静态图示详解
以一组待排序数据:5 3 1 6 9 9为例:

1.4代码实现
public static void insertSort(int[] array){for(int i = 1;i < array.length;i++){int tmp = array[i];//初始化tmp的值int j = i - 1;for( ;j >= 0;j--){//这里带不带等号,会影响排序的稳定性if(array[j] > tmp){array[j+1] = array[j];}else{break;}}array[j + 1] = tmp;}}
1.5时间复杂度
1.5.1最好情况
当待排序数组已经是一个升序排列的数组时,此时时间复杂度最低。因为对于i遍历的每一个值,j无需向左遍历,此时只相当于i遍历了一遍数组(确切的说,是遍历了除第一个元素外的数组),因此时间复杂度为O(n)。

1.5.2最差情况
当待排序数组已经是一个降序排列的数组时,此时时间复杂度最高。因为对于i遍历的每一个值,j需要向左遍历直到-1,因此整个排休的时间复杂度为O(n^2)。

特点:由以上分析可知,待排序的数据越“有序”,直接插入排序算法的时间复杂度越低。这一特点可以用到某些排序算法的优化上,比如快速排序。
1.6空间复杂度
整个排序过程只创建了常数个临时变量,因此空间复杂度为O(1)。
1.7稳定性
在1.2图示详解中,原始数组中的数据9和9,在排序后相对位置没有发生变化,因此直接插入排序是稳定的排序。
1.7.1一个小问题
如果将原有代码中的这句:
if(array[j] > tmp){array[j+1] = array[j];
}else{break;
}
改为:
if(array[j] >= tmp){array[j+1] = array[j];
}else{break;
}
即将判断条件的 “>” 改为 “>=”
原有的直接插入排序还是稳定的吗?
答:不稳定。
图示说明如下(对比1.3静态图示详解的最后两步):

所以直接插入排序是稳定的还是不稳定的呢?
前面已经说明了直接插入排序是稳定的排序。之所以会出现把 > 修改成 >=,原有的排序由稳定变为不稳定的情况,是因为:一个本身就不稳定的排序,是不可能是现成稳定的排序的;而一个本身稳定的排序,是可以实现为不稳定的排序的。
相关文章:
排序算法之——直接插入排序
直接插入排序——以升序排列为例 1.1基本思想1.2动态图示感知1.3静态图示详解1.4代码实现1.5时间复杂度1.5.1最好情况1.5.2最差情况 1.6空间复杂度1.7稳定性1.7.1一个小问题 1.1基本思想 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直…...
突出最强算法模型——回归算法 !!
文章目录 1、特征工程的重要性 2、缺失值和异常值的处理 (1)处理缺失值 (2)处理异常值 3、回归模型的诊断 (1)残差分析 (2)检查回归假设 (3)Cooks 距离 4、学…...
云数据库 Redis 性能深度评测(阿里云、华为云、腾讯云、百度智能云)
在当今的云服务市场中,阿里云、腾讯云、华为云和百度智能云都是领先的云服务提供商,他们都提供了全套的云数据库服务,其中 Redis属于RDS 之后第二被广泛应用的服务,本次测试旨在深入比较这四家云服务巨头在Redis云数据库性能方面的…...
Android---Retrofit实现网络请求:Java 版
简介 在 Android 开发中,网络请求是一个极为关键的部分。Retrofit 作为一个强大的网络请求库,能够简化开发流程,提供高效的网络请求能力。 Retrofit 是一个建立在 OkHttp 基础之上的网络请求库,能够将我们定义的 Java 接口转化为…...
使用静态CRLSP配置MPLS TE隧道
正文共:1591 字 13 图,预估阅读时间:4 分钟 静态CRLSP(Constraint-based Routed Label Switched Paths,基于约束路由的LSP)是指在报文经过的每一跳设备上(包括Ingress、Transit和Egress…...
gentoo安装笔记
最近比较闲,所以挑战一下自己,在自己的台式电脑上安装gentoo 下面记录了我亲自安装的步骤,作为以后我再次安装时参考所用。 整体步骤 一般来将一个linux发行版的安装步骤其实大体上都差不多,基本分为一下几步: 1. …...
Git如何使用 五分钟快速入门
Git如何使用 五分钟快速入门 Git是一个分布式版本控制系统,它可以帮助开发人员跟踪和管理项目的代码变更。与传统的集中式版本控制系统(如SVN)不同,Git允许开发人员在本地存储完整的代码仓库,并且可以独立地进行代码修…...
FreeRTOS学习笔记——(FreeRTOS临界段代码保护及调度器挂起与恢复)
这里写目录标题 1,临界段代码保护简介(熟悉)2,临界段代码保护函数介绍(掌握)3,任务调度器的挂起和恢复(熟悉) 1,临界段代码保护简介(熟悉…...
箱形理论在交易策略中的实战应用与优化
箱形理论,简单来说,就是将价格波动分成一段一段的方框,研究这些方框的高点和低点,来推测价格的趋势。 在上升行情中,价格每突破新高价后,由于群众惧高心理,可能会回跌一段,然后再上升…...
MinIO 和 Apache Tika:文本提取模式
Tl;dr: 在这篇文章中,我们将使用 MinIO Bucket Notifications 和 Apache Tika 进行文档文本提取,这是大型语言模型训练和检索增强生成 LLM和RAG 等关键下游任务的核心。 前提 假设我想构建一个文本数据集,然后我可以用它来微调 LLM.为了做…...
c编译器学习05:与chibicc类似的minilisp编译器(待续)
minilisp项目介绍 项目地址:https://github.com/rui314/minilisp 作者也是rui314,commits也是按照模块开发提交的。 minilisp只有一个代码文件:https://github.com/rui314/minilisp/blob/master/minilisp.c 加注释也只有996行。 代码结构&a…...
手撕qsort函数
前言 本篇主要讲解的是qsort函数细节以及运用实例。 紧跟我的脚步一起手撕qsort函数吧~ 欢迎关注个人主页:逸狼 更多优质内容: 拿捏c语言指针(上) 拿捏c语言指针(中) 拿捏c语言指针(下&…...
项目在linux上的简单部署
本文章只介绍项目的简单部署,暂时没有Docker部署。 项目部署有两种方式,一种是直接命令部署,第二种是用脚本,脚本本身也是将命令进行封装来执行。 命令 项目通过maven打包,启动命令: # 启动命令 nohup …...
MySQL安装教程(详细版)
今天分享的是Win10系统下MySQL的安装教程,打开MySQL官网,按步骤走呀~ 宝们安装MySQL后,需要简单回顾一下关系型数据库的介绍与历史(History of DataBase) 和 常见关系型数据库产品介绍 呀,后面就会进入正式…...
Linux platform tree下的单总线驱动程序设计(DHT11)
目录 概述 1 认识DHT11 1.1 DHT11特性 1.2 DHT11数据格式 1.3 DHT11与MCU通信 1.4 DHT11信号解析 1.4.1 起始信号 1.4.2 解析信号0 1.4.3 解析信号1 2 驱动开发 2.1 硬件接口 2.2 更新设备树 2.2.1 添加驱动节点 2.2.2 编译.dts 2.2.3 更新板卡中的.dtb 2.3 驱…...
自研爬虫框架的经验总结(理论及方法)
背景: 由于业务需要,承接一部分的数据采集工作。目前市场内的一些通用框架不太适合。故而进行了自研。 对比自研和目前成熟的框架,自研更灵活适配,可以自己组装核心方法;后者对于新场景的适配需要对框架本身有较高的理…...
配置基于 AWS CRT 的 HTTP 客户端
基于 AWS CRT 的 HTTP 客户端包括同步 AwsCrtHttpClient 和异步 AwsCrtAsyncHttpClient。基于 AWS CRT 的 HTTP 客户端具有以下 HTTP 客户端优势: 更快的 SDK 启动时间 更小的内存占用空间 降低的延迟时间 连接运行状况管理 DNS 负载均衡 SDK 中基于 AWS CRT …...
挑战杯 基于LSTM的天气预测 - 时间序列预测
0 前言 🔥 优质竞赛项目系列,今天要分享的是 机器学习大数据分析项目 该项目较为新颖,适合作为竞赛课题方向,学长非常推荐! 🧿 更多资料, 项目分享: https://gitee.com/dancheng-senior/po…...
我为什么不喜欢关电脑?
程序员为什么不喜欢关电脑? 你是否注意到,程序员们似乎从不关电脑?别以为他们是电脑上瘾,实则是有他们自己的原因!让我们一起揭秘背后的原因,看看程序员们真正的“英雄”本色! 一、上大学时。 …...
Unity【角色/摄像机移动控制】【1.角色移动】
本文主要总结实现角色移动的解决方案。 1. 创建脚本:PlayerController 2. 创建游戏角色Player,在Player下挂载PlayerController脚本 3. 把Camera挂载到Player的子物体中,调整视角,以实现相机跟随效果 3. PlayerController脚本代码…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...
Web后端基础(基础知识)
BS架构:Browser/Server,浏览器/服务器架构模式。客户端只需要浏览器,应用程序的逻辑和数据都存储在服务端。 优点:维护方便缺点:体验一般 CS架构:Client/Server,客户端/服务器架构模式。需要单独…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
