插入排序(形象类比)

最近在看riscv手册的时候,里面有一段代码是插入排序,但是单看代码的时候有点迷,没看懂咋操作的,后来又查资料复习了一下,最终才把代码看明白,所以写篇博客记录一下。

插入排序像打扑克牌

这是我听到过比较形象的一个比喻。在打扑克牌的时候,我们是一张一张去摸牌,然后将牌按照某种自己定义的顺序进行排序。下面我来类比一下:

  • 从牌堆顶将要摸取的10张牌  <->  待排序数组
  • 一张一张摸牌  <->  一个数一个数进行排序
  • 牌要么在牌堆中,要么在手中;数要么在待排序子数组中,要么在已排序子数组中
  • 在牌堆中的牌加上在手中的牌是所有牌;在待排序子数组中的数加上在已排序子数组中的数是所有数(换句话说 我们将所有牌(数)分为了牌堆牌(待排序数组)和手中牌(已排序数组)两部分)
  • 初始状态:手中无牌(已排序数组为空),牌(数)全在牌堆(待排序数组)中
  • 依次从牌堆(待排序数组)中取牌(数),拿取到的牌(数)与手中的最大的牌进行比较,如果大于,则直接放在手的最右边,否则就和次大的牌进行比较,直到找到这张牌的位置(不再进行具体的类比替换)
  • 直到牌堆中无牌,手中牌为排好序的牌

其实我咋说,都说不清,如果打牌的话,自己类比一下,会发现特别有意思。即使是a[j] = a[j-1]这一步,在摸牌时也有对应。下面我解释一下这行码。

比如说,我的手只能放10张牌,并且摸得牌都是从左到右以此放在我手上,所以我在比较大小的时候,如果这个牌比手里当前比较的牌小时,我会把手里当前比较的牌往后挪一下,给刚摸得牌放的空间。(我说的比较抽象 感觉还是需要想象 如果没打过扑克 可能不太好理解我在说啥)  

下面放一段正儿八经的插入排序的说明吧。

 插入排序是一种简单而有效的排序算法,它的基本思想是将一个元素插入到已经有序的序列中,从而得到一个新的、元素个数增加的有序序列。插入排序的过程可以类比于打扑克牌时,将摸到的牌按照大小顺序插入到手中的牌中。插入排序的平均时间复杂度是 O(n^2),空间复杂度是 O(1)。下面我用一些例子来详细解释插入排序的原理和步骤。

假设我们有一个数组 [6, 7, 9, 3, 1, 5, 4, 8],我们要对它进行升序排序。我们可以用以下的方法进行插入排序:

  • 首先,我们将数组的第一个元素 6 看作是一个已经有序的序列,将剩余的元素看作是未排序的序列。
  • 然后,我们从未排序的序列中取出第一个元素 7,与已排序的序列中的元素从后往前依次比较,如果 7 大于或等于已排序的元素,则将 7 插入到该元素的后面,否则继续比较。在这个例子中,7 大于 6,所以我们将 7 插入到 6 的后面,得到新的有序序列 [6, 7],未排序序列为 [9, 3, 1, 5, 4, 8]。
  • 接着,我们从未排序的序列中取出第一个元素 9,与已排序的序列中的元素从后往前依次比较,如果 9 大于或等于已排序的元素,则将 9 插入到该元素的后面,否则继续比较。在这个例子中,9 大于 7 和 6,所以我们将 9 插入到 7 的后面,得到新的有序序列 [6, 7, 9],未排序序列为 [3, 1, 5, 4, 8]。
  • 依此类推,我们每次从未排序的序列中取出第一个元素,与已排序的序列中的元素从后往前依次比较,找到合适的位置插入,直到未排序的序列为空,排序完成。最终的有序序列为 [1, 3, 4, 5, 6, 7, 8, 9]。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/180116.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

运动戴什么耳机好?运动无线耳机哪个品牌比较好?运动耳机推荐

​如果你是一名户外运动爱好者&#xff0c;那么一款高品质的运动耳机是必不可少的。它们具备好音质、高稳固性舒适度、防尘防水等多项防护功能&#xff0c;让你在恶劣的天气条件下也能保持音乐的陪伴。面对市面上越来越多的运动耳机&#xff0c;到底哪款更值得入手&#xff1f;…

SS8837T-DF-TP-12V/1.8A直流有刷H桥驱动芯片

由工采网代理提供的SS8837T-H桥驱动芯片为摄像机、消费类产品、玩具和其它低电压或者电池供电的运动控制类应用提供了一个集成的电机驱动器解决方案 可广泛应用于&#xff1a;指纹锁、阀门控制、监控安抚、摄像机、数字单镜头反光 (DSLR) 镜头、消费类产品、玩具、机器人技术、…

CyberRT-共享内存实现

CyberRT共享内存类图 共享内存消息发布 数据用共享内存发布时&#xff0c;首先会创建ShmTransmitter对象&#xff0c;包含两个主要成员segment和notifier&#xff0c;Segment用于创建共享内存&#xff08;上面绿色部分&#xff09;&#xff0c;Notifer 最终构建ReadableInfo通…

高通OTA升级方案介绍

高通OTA升级方案介绍 1. 高通LE OTA1.1 背景1.2 Recovery系统 2. SDX12 OTA方案3 OTA包的加密 3UK Penetration Test对于OTA升级也有严格的安全要求&#xff0c;下面是几条用例要求&#xff1a; Firmware: A sufficiently strong signing key MUST be in use. Signing keys MUS…

kubernetes 部署 spinnaker

spinnaker简介 Spinnaker 是一个开源、多云持续交付平台&#xff0c;它将强大而灵活的管道管理系统与主要云提供商的集成相结合。Spinnaker 提供应用程序管理和部署&#xff0c;帮助您快速、自信地发布软件变更。 Spinnaker 提供了两组核心的功能&#xff1a; 应用管理与应用程…

信息系统的安全保护等级的五个级别

信息系统的安全保护等级分为五级&#xff1a;第一级为自主保护级、第二级为指导保护级、第三级为监督保护级、第四级为强制保护级、第五级为专控保护级。 法律依据&#xff1a;《信息安全等级保护管理办法》第四条 信息系统的安全保护等级分为以下五级&#xff1a;   &#…

外贸自建站服务器怎么选?网站搭建的工具?

外贸自建站服务器用哪个好&#xff1f;如何选海洋建站的服务器&#xff1f; 外贸自建站是企业拓展海外市场的重要手段之一。而在这个过程中&#xff0c;选择一个适合的服务器对于网站的稳定运行和优化至关重要。海洋建站将为您介绍如何选择适合的外贸自建站服务器。 外贸自建…

SAP LU04记账更改通知单创建转储单报错:L3094 记帐修改没有份存在

解决办法&#xff1a; 使用事务码LU02&#xff0c;修改过账更改状态&#xff0c;将过账更改状态改为U&#xff0c;强制关闭 1. LU04 查找记账更改通知单号 2. 事务码LU02修改状态 这个时候再用LU04去查看的时候&#xff0c;就不会再显示了

一个ETL流程搞定数据脱敏

数据脱敏是什么&#xff1f; 数据脱敏是指在数据处理过程中&#xff0c;通过一系列的技术手段去除或者替换敏感信息&#xff0c;以保护个人隐私和敏感信息的安全的过程。数据脱敏通常在数据共享、数据分析和软件测试等场景下使用&#xff0c;它旨在降低数据泄露和滥用的风险。…

Sealos 云操作系统私有化部署教程

Sealos 私有云已经正式发布了&#xff0c;它为企业用云提供了一种革命性的新方案。Sealos 的核心优势在于&#xff0c;它允许企业在自己的机房中一键构建一个功能与 Sealos 公有云完全相同的私有云。这意味着企业可以在自己的控制和安全范围内&#xff0c;享受到公有云所提供的…

4.22每日一题(累次积分的计算:交换次序)

注&#xff1a;因为 是积不出的函数&#xff0c;所以先不用算&#xff0c;最后发现&#xff0c;出现dx与dy可以相互抵消&#xff0c;即可算出答案

【TypeScrpt算法】算法的复杂度分析

算法的复杂度分析 什么是算法复杂度&#xff1f; 不同的算法&#xff0c;其实效率是不一样的 让我举一个案例来比较两种不同的算法在查找数组中给定元素的时间复杂度 [1,2,3,4,5,6,7,...9999,n] 顺序查找 这种方法从头到尾遍历整个数组&#xff0c;依次比较每个元素和给定元…

Jenkins+Maven+Gitlab+Tomcat 自动化构建打包、部署

JenkinsMavenGitlabTomcat 自动化构建打包、部署 1、环境需求 本帖针对的是Linux环境&#xff0c;Windows或其他系统也可借鉴。具体只讲述Jenkins配置以及整个流程的实现。 1.JDK&#xff08;或JRE&#xff09;及Java环境变量配置&#xff0c;我用的是JDK1.8.0_144&#xff0…

Talk | UCSB博士生宋珍巧:基于人工智能的功能性蛋白质设计

本期为TechBeat人工智能社区第549期线上Talk。 北京时间11月22日(周三)20:00&#xff0c;UC Santa Barbara博士生—宋珍巧的Talk已准时在TechBeat人工智能社区开播&#xff01; 她与大家分享的主题是: “基于人工智能的功能性蛋白质设计”&#xff0c;介绍了如何利用机器学习算…

好用的局域网监控软件推荐

局域网监控软件是一种用于监控局域网内计算机使用情况的软件&#xff0c;可以帮助企业管理者更好地了解员工的工作状态和行为&#xff0c;规范上网行为并保护企业网络资源。 一、域之盾软件 这是一款专业的上网监控软件&#xff0c;它支持多种操作系统和平台&#xff0c;可以全…

CodeWhisperer 体验总结

CodeWhisperer 体验总结 | CodeWhisperer 是一款亚马逊新推出的通用代码生成器 可以实时进行代码数据的提供 还可以定义安全问题 CodeWhisperer 对个人用户是免费使用 企业用户需要订阅使用 亚马逊云科技开发者社区为开发者们提供全球的开发技术资源。这里有技术文档、开发案例…

【精选】改进的YOLOv5:红外遥感图像微型目标的高效识别系统

1.研究背景与意义 随着科技的不断发展&#xff0c;红外遥感技术在军事、安防、环境监测等领域中得到了广泛应用。红外遥感图像具有独特的优势&#xff0c;可以在夜间或恶劣天气条件下获取目标信息&#xff0c;因此在小目标检测方面具有重要的应用价值。然而&#xff0c;由于红…

当当网获得dangdang商品详情商品列表API 测试请求入口

item_get-获得dangdang商品详情 获取商品详情 item_search-按关键字搜索dangdang商品 获取商品列表 公共参数 名称类型必须描述keyString是调用key&#xff08;必须以GET方式拼接在URL中&#xff09;secretString是调用密钥api_nameString是API接口名称&#xff08;包括在请…

python数据结构与算法-13_高级排序算法-快速排序

快速排序 快速排序名字可不是盖的&#xff0c;很多程序语言标准库实现的内置排序都有它的身影&#xff0c;我们就直奔主题吧。 和归并排序一样&#xff0c;快排也是一种分而治之(divide and conquer)的策略。归并排序把数组递归成只有单个元素的数组&#xff0c;之后再不断两两…

PC端页面进去先出现加载效果

自定义指令v-loading&#xff0c;只需要绑定Boolean即可 v-loading“loading” <el-table :data"list" border style"width: 100%" v-loading"loading"><el-table-column align"center" label"序号" width"5…