数据结构和算法-插入排序分析|学习笔记

简介: 快速学习数据结构和算法-插入排序分析

开发者学堂课程【Go 语言核心编程 - 数据结构和算法:数据结构和算法-插入排序分析】学习笔记,与课程紧密联系,让用户快速学习知识。

课程地址:https://developer.aliyun.com/learning/course/627/detail/9849


数据结构和算法-插入排序分析


 内容介绍

一、插入排序法

二、插入排序法思想

三、思想的示意图

 

插入排序的速度会比选择排序更快。

 

一、插入排序法

插入式排序属于内部排序法,是对于欲排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的。

 

二、插入排序法思想

从代码理解,插入排序要比选择排序更麻烦,但是它的思想很先进,一般来说会比选择排序快一倍,

插入排序(Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表(意思就是先把第一个元素,因为只有一个元素无论是从小到大还是从大到小它都是有序的),开始时有序表中只包含一个元素,无序表中包含有 n-1个元素(就是把第一个看成是有序的,n-1看成是无序的),排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。

 

三、思想的示意图:

image.png

把它画成两个部分,一个部分是演示部分,另一个部分是排序思想。

1. 演示:

假设现在有一个数组,这个数组就当是按小牛的成绩排序,分别是23,0,12,56,34从大到小排序,假设原始的数组是[23,0,12,56,34]

(1)第一次找到插入位置,先是0和23比较,很容易找到位置,这个数组就变成[23,0]12,56,34是无序的

(2)第二次 insertval 的值就变成12,第二次找到插入位置,它如果比0大就后移,那么变完的结果[23,0,0]56,34这时候12已经被保存下来了,让23与12进行比较,是大于12的,位置就已经找到,找到之后,只需要在+1的位置就可以了,就变成[23,12,0]56,34

(3)第三次找到插入位置,并插入,56比0大,就会向后移,这个时候它就变成了[23,12,0,0] 34,移动下标指向12,insertval 还是56,56比12大,说明没有位置,就往后移动,就变成[23,12,12,0],23不大于12就继续向后移动,就变成[23,23,12,0]34,这个时候再向下移动,发现移动不了了,说明它是最大的,但是它还是会稍微移动一下才会退出循环,最后会变成[56,23,12,0]23 ,也就是它会不停的找位置找到之后加进去。但是这个优越的地方是 ,它总是有序数组在找位置,它比较的次数是在减少的。所以插入排序是比冒泡排序和选择排序快的,至少快一倍

(4)第四次也是一样的道理,第四次插入的值就找34就可以,每次都是从最后找。于是就变成[56,23,12,0,0]下标就指向了12,12比34 仍然是小的,所以还没有找到位置,往后面移动就是[56,23,12,12,0]继续向后移动就是[56,23,23,12,0]最后会变成[56,34,23,12,0]

不确定每次比较的次数到底是多少,它可能很快就退出来了,也可能会遍历完才退出,假如最后不是34是-1那比较一次就可以了,如果最后就是最大的,它就得遍历完

2.排序思想:

(1)将23当作是有序的数组

(2)给0找一个位置插入

(3)思路:先把0保存到一个变量 insertval 中,将这个变量插到23这个有序变量中,插入时候就相当于这个值被保存了,现在它的指针就指向它前一个位置,就是0的前一个位置,然后将插入的位置用一个变量保存,就是0的下标的前一个下标

(4)从后开始比较,给 insertval 找到一个位置,插入  

(5)找的过程中有序数组的元素位置是要后移的

相关文章
|
3天前
|
运维 监控 JavaScript
基于 Node.js 图结构的局域网设备拓扑分析算法在局域网内监控软件中的应用研究
本文探讨图结构在局域网监控系统中的应用,通过Node.js实现设备拓扑建模、路径分析与故障定位,提升网络可视化、可追溯性与运维效率,结合模拟实验验证其高效性与准确性。
41 3
|
4月前
|
机器学习/深度学习 边缘计算 算法
NOMA和OFDMA优化算法分析
NOMA和OFDMA优化算法分析
244 127
|
6月前
|
数据采集 机器学习/深度学习 算法
别急着上算法,咱先把数据整明白:大数据分析的5个基本步骤,你都搞对了吗?
别急着上算法,咱先把数据整明白:大数据分析的5个基本步骤,你都搞对了吗?
236 4
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
73 1
|
3月前
|
人工智能 自然语言处理 算法
2025 年 7 月境内深度合成服务算法备案情况分析报告
2025年7月,中央网信办发布第十二批深度合成算法备案信息,全国389款产品通过备案,服务提供者占比超七成。截至7月14日,全国累计备案达3834款,覆盖文本、图像、音视频等多模态场景,广泛应用于生活服务、医疗、金融等领域。广东以135款居首,数字人、AI客服等C端应用主导,民营企业成主力,国企聚焦公共服务。随着AI政策推动,备案已成为AI产品合规上线关键环节。
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
83 0
|
6月前
|
存储 监控 算法
员工行为监控软件中的 Go 语言哈希表算法:理论、实现与分析
当代企业管理体系中,员工行为监控软件已逐步成为维护企业信息安全、提升工作效能的关键工具。这类软件能够实时记录员工操作行为,为企业管理者提供数据驱动的决策依据。其核心支撑技术在于数据结构与算法的精妙运用。本文聚焦于 Go 语言中的哈希表算法,深入探究其在员工行为监控软件中的应用逻辑与实现机制。
148 14
|
7月前
|
自然语言处理 算法 安全
境内深度合成服务算法备案通过名单分析报告
本报告基于《境内深度合成服务算法备案通过名单》,分析了2023年6月至2025年3月公布的10批备案数据,涵盖属地分布、行业应用及产品形式等多个维度。报告显示,深度合成算法主要集中于经济发达地区,如北京、广东、上海等地,涉及教育、医疗、金融、娱乐等多行业。未来趋势显示技术将向多模态融合、行业定制化和安全合规方向发展。建议企业加强技术研发、拓展应用场景、关注政策动态,以在深度合成领域抢占先机。此分析旨在为企业提供参考,助力把握技术发展机遇。
境内深度合成服务算法备案通过名单分析报告
|
7月前
|
供应链 算法 搜索推荐
从公布的前十一批其他算法备案通过名单分析
2025年3月12日,国家网信办发布算法备案信息,深度合成算法通过395款,其他算法45款。前10次备案中,深度合成算法累计3234款,其他类别647款。个性化推送类占比49%,涵盖电商、资讯、视频推荐;检索过滤类占31.53%,用于搜索优化和内容安全;调度决策类占9.12%,集中在物流配送等;排序精选类占8.81%,生成合成类占1.55%。应用领域包括电商、社交媒体、物流、金融、医疗等,互联网科技企业主导,技术向垂直行业渗透,内容安全和多模态技术成新增长点。未来大模型检索和多模态生成或成重点。
从公布的前十一批其他算法备案通过名单分析
|
7月前
|
人工智能 自然语言处理 供应链
从第十批算法备案通过名单中分析算法的属地占比、行业及应用情况
2025年3月12日,国家网信办公布第十批深度合成算法通过名单,共395款。主要分布在广东、北京、上海、浙江等地,占比超80%,涵盖智能对话、图像生成、文本生成等多行业。典型应用包括医疗、教育、金融等领域,如觅健医疗内容生成算法、匠邦AI智能生成合成算法等。服务角色以面向用户为主,技术趋势为多模态融合与垂直领域专业化。

热门文章

最新文章