Go 实现插入排序算法及优化
插入排序
插入排序是一种简单的排序算法,以数组为例,我们可以把数组看成是多个数组组成。插入排序的基本思想是往前面已排好序的数组中插入一个元素,组成一个新的数组,此数组依然有序。光看文字可能不理解,让我们看看图示:

插入排序的时间复杂度为 O(N²)。
算法实现
import ("fmt"
)func main() {nums := [4]int{4, 1, 3, 2}fmt.Println("原数组:", nums)fmt.Println("--------------------------------")InsertionSort(nums)
}func InsertionSort(nums [4]int) {for i := 1; i < len(nums); i++ {for j := i; j > 0 && nums[j] < nums[j-1]; j-- {nums[j], nums[j-1] = nums[j-1], nums[j]}fmt.Printf("第 %d 轮后:%v\n", i, nums)}fmt.Println("--------------------------------")fmt.Println("排序后的数组:", nums)
}
执行结果:
原数组: [4 1 3 2]
--------------------------------
第 1 轮后:[1 4 3 2]
第 2 轮后:[1 3 4 2]
第 3 轮后:[1 2 3 4]
--------------------------------
排序后的数组: [1 2 3 4]
原数组: [4 1 3 2]
第 1 轮后:[1 4 3 2]
第 2 轮后:[1 3 4 2]
第 3 轮后:[1 2 3 4]
排序后的数组: [1 2 3 4]
算法优化
上面的代码,是通过不断地交换元素,直到无法交换,才能将元素放置到待插入的位置,为了避免频繁交换元素而导致效率低,将交换的逻辑变成把前面的数往后移,最后再将待排序的元素插入到合适的位置即可。
import ("fmt"
)func main() {nums := [4]int{4, 1, 3, 2}fmt.Println("原数组:", nums)fmt.Println("--------------------------------")InsertionSort(nums)
}func InsertionSort(nums [4]int) {for i := 1; i < len(nums); i++ {t := nums[i]j := ifor ; j > 0 && t < nums[j-1]; j-- {nums[j] = nums[j-1]}nums[j] = tfmt.Printf("第 %d 轮后:%v\n", i, nums)}fmt.Println("--------------------------------")fmt.Println("排序后的数组:", nums)
}
用变量 t 记录待排序的元素,用 j 变量往前查找,只要前面的数比 t 大,那么就往后移,最后将 t 插入到合适的位置。
小结
本文首先对插入排序进行简单地介绍,通过图片来演示插入排序的过程,然后使用 Go 语言实现插入排序的算法。为减少算法中交换次数的逻辑,对算法进行优化,将交换的逻辑变成把前面的数往后移,最后将待排序的数插入到合适的位置即可。
除了这种优化方式,还有一种改造方式:普通的算法往左查找的方式是线性查找,由于元素是有序的,因此线性查找可以换成二分查找,但是经过二分找到待插入的位置之后,也得移动前面的元素,相比上面的优化方法,还多了 O(logn) 的查找时间复杂度,因此我认为没有必要改造成二分查找。
相关文章:
Go 实现插入排序算法及优化
插入排序 插入排序是一种简单的排序算法,以数组为例,我们可以把数组看成是多个数组组成。插入排序的基本思想是往前面已排好序的数组中插入一个元素,组成一个新的数组,此数组依然有序。光看文字可能不理解,让我们看看…...
LuatOS-SOC接口文档(air780E)--max30102 - 心率模块
max30102.init(i2c_id,int)# 初始化MAX30102传感器 参数 传入值类型 解释 int 传感器所在的i2c总线id,默认为0 int int引脚 返回值 返回值类型 解释 bool 成功返回true, 否则返回nil或者false 例子 if max30102.init(0,pin.PC05) thenlog.info("max30102&q…...
设计模式(2)-创建型模式
1,创建型模式 4.1 单例设计模式 单例模式(Singleton Pattern)是 Java 中最简单的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。 这种模式涉及到一个单一的类,该类负责创建自己…...
elasticsearch一些重要的配置参数
先看一下官网给我们提供的全部的参数配置项 官网地址 官方文档链接:注意版本是8.1Configuring Elasticsearch | Elasticsearch Guide [8.1] | Elastic编辑https://www.elastic.co/guide/en/elasticsearch/reference/current/settings.html 重要(基本…...
raft和zab算法的区别
首先,二者都是通过选举一个 Leader 来简化复杂度,后续的工作都是由 Leader 来做。 投票的时候,二者都需要定义一个轮次 Raft 定义了 term 来表示选举轮次 ZooKeeper 定义了 electionEpoch 来表示 同步数据的时候,都希望选举出来…...
Arthas生成火焰图命令报错汇总
操作步骤 1、在容器中集成了arthas诊断和调试工具,想生产火焰图,执行profiler start,报错 如下: [arthas1]$ profiler start AsyncProfiler error: Can not find libasyncProfiler so, please check the arthas directory. 2、…...
【PyQt学习篇 · ⑤】:QWidget - 鼠标操作
文章目录 鼠标形状设置常用鼠标形状设置自定义鼠标形状 重置形状获取鼠标鼠标跟踪鼠标跟踪案例 鼠标形状设置 常用鼠标形状设置 在PyQt中,QWidget类提供了设置鼠标形状的功能。可以使用setCursor()方法来更改QWidget及其子类的鼠标形状。该方法接受一个Qt.CursorS…...
2-多媒体数据压缩国际标准-Part3
文章目录 视频压缩的国际标准MPEG-1&MPEG-2/H.262视频标准MPEG-4 AVC/H.264视频标准H.264编码框架概述H.264视频编码的技术创新点 H.265/HEVC视频标准HEVC性能与编解码框架概述Quadtree-based coding structureDeblocking & SAO FilterHEVC各模块运算量 视频压缩的国际…...
使用Go模块进行依赖管理
摘要:本文将介绍Go语言中的模块(module)概念,以及如何使用Go模块进行依赖管理。我们会探讨模块的基本概念、使用方法、配置和依赖关系管理等方面的内容。 一、引言 Go语言自2007年发布以来,一直以其简洁、高效和强大…...
人工智能与航天技术的融合:未来发展的新趋势
人工智能与航天技术的融合:未来发展的新趋势 随着科技的飞速发展,人工智能和航天技术已经成为人类探索未知世界的重要工具。本文将探讨这两个领域的结合点,以及未来的发展趋势和应用前景。通过了解这些技术,读者将更好地理解人工…...
私有云:【11】win10安装Agent客户端组件
私有云:【11】win10安装Agent客户端组件 1、配置IP及加入域2、安装Agent客户端组件3、生成win10快照 1、配置IP及加入域 配置ip及dns 修改计算机名且加入域 进行验证 加入成功 将cloudadmin用户加入管理员组 输入cloudadmin户名密码验证 2、安装Agent客户端组件 …...
什么是程序化交易
大到量化、程序化、高频交易、套利交易、主观投资这些基本的概念,小到网格交易、条件单、T0、ETF套利、期现套利、算法拆单交易、打板策略等具体的投资方式。如果没有接触过这些,很容易混淆。 程序化交易: 指通过既定程序或特定软件…...
企业如何安全跨国传输30T文件数据
对于一些对数据敏感性比较高的企业,如IT企业和国企等,跨国数据传输是当今企业面临的一个重要挑战,尤其是当数据量达到30T这样的规模时,如何保证数据的速度、安全和合规性,就成为了企业必须考虑的问题。本文将从以下几个…...
【Linux】centos安装配置及远程连接工具的使用
🎉🎉欢迎来到我的CSDN主页!🎉🎉 🏅我是Java方文山,一个在CSDN分享笔记的博主。📚📚 🌟推荐给大家我的专栏《微信小程序开发实战》。🎯Ἲ…...
算法|每日一题|掷骰子等于目标和的方法数|动态规划
1155.掷骰子等于目标和的方法数 原题地址: 力扣每日一题:掷骰子等于目标和的方法数 这里有 n 个一样的骰子,每个骰子上都有 k 个面,分别标号为 1 到 k 。 给定三个整数 n , k 和 target ,返回可能的方式(从总共 kn 种…...
Java架构师软件工程全流程
目录 1 导学2 软件工程概述(原)3 能力成熟度模型4 软件过程模型5 逆向工程6 需求工程6.1 软件需求6.2 需求获取6.3 需求分析6.4 需求定义6.5 需求验证6.6 需求管理7 处理流程设计8 系统设计6.1 人机界面设计7 测试基础知识7.1 测试原则和方法7.2 测试阶段7.3 测试用例的设计7.4…...
深度学习中Transformer的简单理解
Transformer 网络结构 Transformer也是由编码器和解码器组成的。 每一层Encoder编码器都由很多层构成的,编码器内又是self-attention和前馈网络构成的。Self-attention是用来做加权平均,前馈网络用来组合。 但是decoder有点不同,多了一层En…...
Java架构师系统安全
目录 1 导学2 信息安全基础知识3 信息安全系统的组成框架4 信息安全技术4.1 加密技术4.2 对称加密技术4.3 非对称加密技术4.4 信息摘要4.5数字签名5 信息安全的抗攻击技术5.1 ARP欺骗的原理5.2 ARP欺骗的防范措施5.3 IP欺骗的原理和流程6 信息安全的保证体系和评估方法7 网络安…...
Stable Diffusion 图生图+ControlNet list index out of range
在webui1.5中用图生图ControlNet批量处理图片的时候报错: controlnet indexError: list index out of range 解决方法: 在controlNet的设置页中勾选不输出检测图即可。 参考:https://github.com/AUTOMATIC1111/stable-diffusion-webui/issu…...
SylixOS BSP开发(七)
实现系统调试信息打印接口 当系统出错时或者使用内核日志时会输出一些打印信息,这最终都是调用到bspLib.c中的bspDebugMsg 这个接口来实现的,所以我们在开发BSP时,第一个要做的工作就是实现这个接口。 一般的调试信息都是通过串口来输出的&am…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG
TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码:HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...
TJCTF 2025
还以为是天津的。这个比较容易,虽然绕了点弯,可还是把CP AK了,不过我会的别人也会,还是没啥名次。记录一下吧。 Crypto bacon-bits with open(flag.txt) as f: flag f.read().strip() with open(text.txt) as t: text t.read…...
【实施指南】Android客户端HTTPS双向认证实施指南
🔐 一、所需准备材料 证书文件(6类核心文件) 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...
