当前位置: 首页 > news >正文

排序算法:插入排序

        插入排序的思想非常简单,生活中有一个很常见的场景:在打扑克牌时,我们一边抓牌一边给扑克牌排序,每次摸一张牌,就将它插入手上已有的牌中合适的位置,逐渐完成整个排序。

        插入排序有两种写法:

  • 交换法:在新数字插入过程中,不断与前面的数字交换,直到找到自己合适的位置。
  • 移动法:在新数字插入过程中,与前面的数字不断比较,前面的数字不断向后挪出位置,当新数字找到自己的位置后,插入一次即可。

交换法插入排序

public static void insertSort(int[] arr) {// 从第二个数开始,往前插入数字for (int i = 1; i < arr.length; i++) {// j 记录当前数字下标int j = i;// 当前数字比前一个数字小,则将当前数字与前一个数字交换while (j >= 1 && arr[j] < arr[j - 1]) {swap(arr, j, j - 1);// 更新当前数字下标j--;}}
}
private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

        当数字少于两个时,不存在排序问题,当然也不需要插入,所以我们直接从第二个数字开始往前插入。

        整个过程就像是已经有一些数字坐成了一排,这时一个新的数字要加入,这个新加入的数字原本坐在这一排数字的最后一位,然后它不断地与前面的数字比较,如果前面的数字比它大,它就和前面的数字交换位置。

移动法插入排序

        我们发现,在交换法插入排序中,每次交换数字时,swap 函数都会进行三次赋值操作。但实际上,新插入的这个数字并不一定适合与它交换的数字所在的位置。也就是说,它刚换到新的位置上不久,下一次比较后,如果又需要交换,它马上又会被换到前一个数字的位置。

        由此,我们可以想到一种优化方案:让新插入的数字先进行比较,前面比它大的数字不断向后移动,直到找到适合这个新数字的位置后,新数字只做一次插入操作即可。

        这种方案我们需要把新插入的数字暂存起来,代码如下:

public static void insertSort(int[] arr) {// 从第二个数开始,往前插入数字for (int i = 1; i < arr.length; i++) {int currentNumber = arr[i];int j = i - 1;// 寻找插入位置的过程中,不断地将比 currentNumber 大的数字向后挪while (j >= 0 && currentNumber < arr[j]) {arr[j + 1] = arr[j];j--;}// 两种情况会跳出循环:1. 遇到一个小于或等于 currentNumber 的数字,跳出循环,currentNumber 就坐到它后面。// 2. 已经走到数列头部,仍然没有遇到小于或等于 currentNumber 的数字,也会跳出循环,此时 j 等于 -1,currentNumber 就坐到数列头部。arr[j + 1] = currentNumber;}
}

        整个过程就像是已经有一些数字坐成了一排,这时一个新的数字要加入,所以这一排数字不断地向后腾出位置,当新的数字找到自己合适的位置后,就可以直接坐下了。重复此过程,直到排序结束。

时间复杂度 & 空间复杂度

插入排序过程需要两层循环,时间复杂度为O(n²);只需要常量级的临时变量,空间复杂度为 O(1)。

相关文章:

排序算法:插入排序

插入排序的思想非常简单&#xff0c;生活中有一个很常见的场景&#xff1a;在打扑克牌时&#xff0c;我们一边抓牌一边给扑克牌排序&#xff0c;每次摸一张牌&#xff0c;就将它插入手上已有的牌中合适的位置&#xff0c;逐渐完成整个排序。 插入排序有两种写法&#xff1a; 交…...

掌握AI助手的魔法工具:解密Prompt(提示)在AIGC时代的应用「上篇」

在当今的AIGC时代&#xff0c;我们面临着越来越多的人工智能技术和应用。其中一个引人注目的工具就是Prompt&#xff08;提示&#xff09;。它就像是一种魔法&#xff0c;可以让我们与AI助手进行更加互动和有针对性的对话。那么&#xff0c;让我们一起来了解一下Prompt&#xf…...

JMeter - 接口压力测试工具简单使用

【启动前配置】 启动JMeter前可以先配置语言和编码: 修改:E:\JMeter\apache-jmeter-5.5\bin\jmeter.properties文件中: 1.language=en # 指定语言 language=zh_CN 2.sampleresult.default.encoding=ISO-8859-1 # 指定编码 UTF-8 sampleresult.default.encoding=UTF-8 也…...

【C++入门到精通】C++入门 —— priority_queue(STL)优先队列

阅读导航 前言一、priority_queue简介1. 概念2. 特点 二、priority_queue使用1. 基本操作2. 底层结构 三、priority_queue模拟实现⭕ C代码⭕priority_queue中的仿函数 总结温馨提示 前言 ⭕文章绑定了VS平台下std::priority_queue的源码&#xff0c;大家可以下载了解一下&…...

静态代码扫描工具 Sonar 配置及使用

概览 Sonar 是一个用于代码质量管理的开放平台。通过插件机制&#xff0c;Sonar 可以集成不同的测试工具&#xff0c;代码分析工具&#xff0c;以及持续集成工具。与持续集成工具&#xff08;例如 Hudson/Jenkins 等&#xff09;不同&#xff0c;Sonar 并不是简单地把不同的代…...

docker 03(docker 容器的数据卷)

一、数据卷的概念和作用 删除后&#xff0c;数据也没了。 不能 数据卷 是宿主机中的一个目录或文件当容器目录和数据卷目录绑定后&#xff0c;对方的修改会立即同步一个数据卷可以被多个容器同时挂载 作用&#xff1a; 容器数据持久化 外部机器和容器间接通信 容器之间数据交换…...

【04】基础知识:typescript中的类

一、es5 对象 1、定义 类&#xff08;对象&#xff09; 原型链上的属性和方法会被多个实例共享。构造函数中的属性和方法不会。 // 自定义构造函数 function Person(name, age) {this.name namethis.age agethis.getInfo function() {console.log(${this.name} - ${this.…...

CCClippingNode:在游戏中实现遮罩效果、剪切效果,以涂抹糖霜为例,如何更好的实现涂抹效果,提高用户的游戏体验

CCClippingNode&#xff1a;在游戏中实现遮罩效果、剪切效果&#xff0c;以涂抹糖霜为例&#xff0c;如何更好的实现涂抹效果 设备/引擎&#xff1a;Mac&#xff08;11.6&#xff09;/cocos2d-x 开发工具&#xff1a;Xcode&#xff08;13.0&#xff09; 开发需求&#xff1a…...

cuda gdb调试

如果cudaDeviceEnablePeerAccess函数不支持或不起作用&#xff0c;您仍然可以尝试其他方法来实现GPU之间的数据交换和通信。以下是一些替代方法&#xff1a; 通过主机内存进行数据传输&#xff1a; 如果GPU之间的数据交换不是非常频繁&#xff0c;您可以将数据从一个GPU复制到…...

【vim 学习系列文章 5 - cscope 过滤掉某些目录】

文章目录 cscope 过滤目录介绍 cscope 过滤目录介绍 第一步创建自己的cscope脚本~/.local/bin/cscope.sh&#xff0c;如下&#xff1a; function my_cscope() {CODE_PATHpwdecho "$CODE_PATH"echo "start cscope...."if [ ! -f "$CODE_PATH/cscope.…...

实验三 HBase1.2.6安装及配置

系列文章目录 文章目录 系列文章目录前言一、HBase1.2.6的安装二、HBase1.2.6的配置2.1 单机模式配置2.2 伪分布式模式配置 总结参考 前言 在安装HBase1.2.6之前&#xff0c;需要安装好hadoop2.7.6。 本篇文章参考&#xff1a;HBase2.2.2安装和编程实践指南 一、HBase1.2.6的安…...

LightDB sequence支持MAXVALUE最大值与Oracle相同

功能介绍 Oracle数据库在创建sequence的时候可以支持设置maxvalue 为9999999999999999999999999999&#xff0c;这样的SQL在LightDB23.3版本之前都是执行失败的。为了方便Oracle用户迁移到LightDB上&#xff0c;在LightDB23.3版本上&#xff0c;增加了sequence支持maxvalue设置…...

二、Kafka快速入门

目录 2.1 安装部署1、【单机部署】2、【集群部署】 2.2 Kafka命令行操作1、查看topic相关命令参数2、查看当前kafka服务器中的所有Topic3、创建 first topic4、查看 first 主题的详情5、修改分区数&#xff08;注意&#xff1a;分区数只能增加&#xff0c;不能减少&#xff09;…...

消息中间件-kafka实战-第五章-kafka重复消费、顺序消费及死信队列

目录 一、参考二、路由规则&#xff08;分片规则&#xff09;三、触发重复消费的场景场景一&#xff1a;触发rebalance问题描述可能原因实际影响参数在kafka0.10.1 之前:在kafka0.10.1之后&#xff1a;解决方案 场景二&#xff1a;服务宕机可能原因解决方案 消息幂等性 四、kaf…...

python爬虫9:实战2

python爬虫9&#xff1a;实战2 前言 ​ python实现网络爬虫非常简单&#xff0c;只需要掌握一定的基础知识和一定的库使用技巧即可。本系列目标旨在梳理相关知识点&#xff0c;方便以后复习。 申明 ​ 本系列所涉及的代码仅用于个人研究与讨论&#xff0c;并不会对网站产生不好…...

从业务层的代码出发,去排查通用框架代码崩溃的问题

目录 1、问题说明 1.1、Release下崩溃&#xff0c;Debug下很难复现 1.2、用Windbg打开dump文件&#xff0c;发现崩溃在通用的框架代码中 2、进一步分析 2.1、使用IDA查看汇编代码尝试寻找崩溃的线索 2.2、在Windbg中查看相关变量的值 2.3、查看最近代码的修改记录&#…...

LLM预训练大型语言模型Pre-training large language models

在上一个视频中&#xff0c;您被介绍到了生成性AI项目的生命周期。 如您所见&#xff0c;在您开始启动您的生成性AI应用的有趣部分之前&#xff0c;有几个步骤需要完成。一旦您确定了您的用例范围&#xff0c;并确定了您需要LLM在您的应用程序中的工作方式&#xff0c;您的下…...

[Machine Learning] 损失函数和优化过程

文章目录 机器学习算法的目的是找到一个假设来拟合数据。这通过一个优化过程来实现&#xff0c;该过程从预定义的 hypothesis class&#xff08;假设类&#xff09;中选择一个假设来最小化目标函数。具体地说&#xff0c;我们想找到 arg min ⁡ h ∈ H 1 n ∑ i 1 n ℓ ( X i…...

serialVersionUID 有何用途?如果没定义会有什么问题?

序列化是将对象的状态信息转换为可存储或传输的形式的过程。我们都知道&#xff0c;Java 对象是保持在 JVM 的堆内存中的&#xff0c;也就是说&#xff0c;如果 JVM 堆不存在了&#xff0c;那么对象也就跟着消失了。 而序列化提供了一种方案&#xff0c;可以让你在即使 JVM 停机…...

C# OpenCvSharp DNN 二维码增强 超分辨率

效果 项目 代码 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; using OpenCvSharp; using OpenCvSharp.Dnn; using OpenCvSh…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...