【探索数据结构与算法】插入排序:原理、实现与分析(图文详解)

目录

一、插入排序 算法思想

二、插入排序 算法步骤 

四、复杂度分析

时间复杂度:O(n^2)

空间复杂度:O(1) 

稳定性:稳定算法 

五、应用场景 


💓 博客主页:C-SDN花园GGbond

⏩ 文章专栏:探索数据结构与算法

一、插入排序 算法思想

**插入排序(Insert Sort)**是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。它的思想类似于我们打扑克牌时的整理 

二、插入排序 算法步骤 

  1. 将第一待排序 序列的第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
  2. 从尾到头依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)     
  3. 具体步骤是这样的:
    (以排升序为例)

    从第一个元素开始,该元素可以认为已经被排序。
    取出下一个元素,在已经排序的元素序列中从后向前扫描。
    如果该元素(已排序)大于新元素,将该元素向后移动一位。
    重复步骤3,直到找到已排序的元素小于或者等于新元素的位置。
    将新元素插入到该位置后。
    重复步骤2~5,直到所有元素都排序完成。

动图 

三、C语言代码实现 

//插入排序
void InsertSort(int* a, int len)
{//0到end有序,插入a[end+1]for (int i = 0; i < len - 1; i++){int end = i;int tmp = a[i + 1];while (end >= 0){if (a[end]>tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

四、复杂度分析

时间复杂度:O(n^2)

最好情况(O(n)):

当输入数组已经是排序状态时,插入排序的性能最优。此时,每个元素只需与其前面的一个元素进行比较(因为它已经位于正确的位置),因此总共需要进行大约n-1次比较,时间复杂度为O(n)。这里的n是数组的长度。

最坏情况(O(n^2)):

当输入数组完全逆序时,插入排序的性能最差。对于每个元素,都需要与其前面的所有元素进行比较,直到找到合适的位置。因此,第i个元素需要比较i次(其中i从2开始,直到n),总共需要进行的比较次数大约为1 + 2 + 3 + ... + (n-1) = n(n-1)/2,时间复杂度为O(n^2)。

平均情况(O(n^2)):

对于随机排列的数组,插入排序的平均时间复杂度也是O(n^2)。这是因为大部分情况下,元素都需要进行多次移动和比较才能找到正确的位置。

空间复杂度:O(1) 

插入排序是一种原地排序算法,它只需要一个额外的存储空间来暂存当前需要插入的元素(即“key”),而不需要额外的数组来存储排序过程中的数据。因此,其空间复杂度为O(1)。

稳定性:稳定算法 

 插入排序是一种稳定的排序算法。在插入排序过程中,如果两个相等的元素,后面的元素不会移动到前面元素的前面,而是直接插入到与它相等的元素之后,从而保持了原有的相对顺序。

五、应用场景 

插入排序虽然在大规模数据集上可能不是最高效的排序算法,但其简单性、稳定性和在某些特定场景下的高效性使得它在许多实际应用中仍然具有一定的价值。

小规模数据集:由于插入排序在小规模数据集上表现良好,且实现简单,因此常用于对少量数据进行排序的场景。快速排序的小区间优化
几乎有序的数据集:当数据已经接近有序时,插入排序的性能会显著提高。因为此时大部分元素已经处于或接近其最终位置,所需的比较和移动次数会大幅减少。
链表排序:由于链表不支持像数组那样的随机访问,因此在链表上进行排序时,插入排序成为了一个非常合适的选择。它可以通过改变节点的指针来实现元素的移动,而不需要额外的存储空间。

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

STM32之FMC—扩展外部 SDRAM

文章目录 一、FMC外设介绍二、SDRAM 控制原理1、SDRAM关键参数a、容量、分区b、引脚SDRAM 使用 2、SDRAM芯片IS42S16400J3、SDRAM 控制引脚说明控制逻辑地址控制SDRAM 的存储阵列SDRAM 的命令预充电刷新 W9825G6KH&#xff1a;W9825G6KH引脚 三、STM32F429 FMC四、其他文章打开…

基于ssm的个性化影片推荐系统设计与实现

需要项目源码请联系我&#xff0c;目前有各类成品 毕设 javaweb ssh ssm springboot等等项目框架&#xff0c;源码丰富。 专业团队&#xff0c;咨询就送开题报告&#xff0c;活动限时免费&#xff0c;有需要的朋友可以来咨询。 一、摘要 随着科学技术的飞速发展&#xff0c;社…

Matlab simulink建模与仿真 第十五章(信号源库)

参考视频&#xff1a;simulink1.1simulink简介_哔哩哔哩_bilibili 一、信号源库中的模块概览 注&#xff1a;部分模块在第二章中有介绍&#xff0c;本章不再赘述。 二、from输入源模块 1、From Workspace模块 &#xff08;1&#xff09;该模块可从MATLAB工作区、模型工作区…

双指针算法专题(2)

找往期文章包括但不限于本期文章中不懂的知识点&#xff1a; 个人主页&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏&#xff1a; 优选算法专题 想要了解双指针算法的介绍&#xff0c;可以去看下面的博客&#xff1a;双指针算法的介绍 目录 611.有效三角形的个数 LCR 1…

King3399 SDK编译简明教程

该文章仅供参考&#xff0c;编写人不对任何实验设备、人员及测量结果负责&#xff01;&#xff01;&#xff01; 0 引言 文章主要介绍King3399&#xff08;瑞芯微rk3399开发板&#xff0c;荣品&#xff09;官方SDK编译过程&#xff0c;涉及环境配置、补丁以及编译过程中注意事…

shiro漏洞复现

目录 shiro介绍框架介绍判断是否使用shiro框架 环境搭建CVE-2010-3863漏洞原理影响版本漏洞复现 CVE-2016-4437漏洞原理影响版本漏洞复现 CVE-2020-1957漏洞原理影响版本漏洞复现 shiro-721拉取环境漏洞原理漏洞复现 shiro介绍 框架介绍 Apache Shiro提供了认证、授权、加密和…

CSARA机械手正反解代码解读和左右手定则应用

前言&#xff1a;前段时间在某鱼上买了一份CSARA的机械臂的程序&#xff0c;拿出来分享一下&#xff0c;并记录一下。说明一下并非是公司的核心代码&#xff0c;我也不搞这个....侵权就删了。 首先简单回顾一下CSARA的正逆解。 根据几何的方法能求出末端在平面坐标系中的xy坐标…

第二百三十五节 JPA教程 - JPA Lob列示例

JPA教程 - JPA Lob列示例 以下代码显示了如何使用Lob注释将字节数组保存到数据库。 LOB在数据库中有两种类型&#xff1a;字符大对象&#xff08;称为CLOB&#xff09;和二进制大对象&#xff08;或BLOB&#xff09;。 CLOB列保存大字符序列&#xff0c;BLOB列可存储大字节序…

Linux memcg lru lock提升锁性能

内核关于per memcg lru lock的重要提交&#xff1a; f9b1038ebccad354256cf84749cbc321b5347497 6168d0da2b479ce25a4647de194045de1bdd1f1d 计算虚拟地址转换基本机制 为了处理多应用程序的地址冲突&#xff0c; linux 系统在应用中使用了虚拟地址&#xff0c;得益于硬件的…

SpringBoot+vue集成sm国密加密解密

文章目录 前言认识SM2后端工具类实现引入依赖代码实现工具类&#xff1a;SM2Util 单元测试案例1&#xff1a;生成服务端公钥、私钥&#xff0c;前端js公钥、私钥案例2&#xff1a;客户端加密&#xff0c;服务端完成解密案例3&#xff1a;服务端进行加密&#xff08;可用于后面前…

禹神:一小时彻底搞懂跨域解决方案

1. 浏览器的同源策略 2. 跨域会受到哪些限制 4. CORS 解决 Ajax 跨域问题 exposedHeaders 不加这个&#xff0c;js拿不到这个响应头(浏览器控制台network中能看见&#xff0c;但是js拿不到) 5. JSONP 解决跨域问题 JSOP只能解决get请求 服务端代码 客户端代码 服务端代码升…

卡尔曼滤波中Q和R与噪声的关系

卡尔曼滤波 一种用于估计系统状态的递归滤波器&#xff0c;通过融合传感器测量和系统模型&#xff0c;提供系统状态的最优估计。 Q和R是什么 在卡尔曼滤波中&#xff0c;Q和R分别表示过程噪声和测量噪声的协方差矩阵。 Q Q Q矩阵&#xff08;过程噪声协方差矩阵&#xff09;…

LC并联电路在正弦稳态下的传递函数推导(LC并联谐振选频电路)

LC并联电路在正弦稳态下的传递函数推导&#xff08;LC并联谐振选频电路&#xff09; 本文通过 1.解微分方程、2.阻抗模型两种方法推导 LC 并联选频电路在正弦稳态条件下的传递函数&#xff0c;并通过仿真验证不同频率时 vo(t) 与 vi(t) 的幅值相角的关系。 电路介绍 已知条件…

人工智能和大模型的简介

文章目录 前言一、大模型简介二、大模型主要功能1、自然语言理解和生成2、文本总结和翻译3、文本分类和信息检索4、多模态处理三、大模型的技术特性1、深度学习架构2、大规模预训练3、自适应能力前言 随着技术的进步,人工智能(Artificial Intelligence, AI)和机器学习(Mac…

建设世界一流财务管理体系【数字化顶层设计】【持续更新】

财务管理是企业管理的中心环节&#xff0c;是企业实现基业长青的重要基础和保障。近年来&#xff0c;中央企业认真贯彻落实党中央、国务院决策部署&#xff0c;高度重视财务管理工作&#xff0c;持续优化管理手段&#xff0c;不断创新管理模式&#xff0c;积极应用先进管理工具…

CSS调整背景

一、设置背景颜色 通过 background-color 属性指定&#xff0c;值可以是十六进制 #ffffff&#xff0c;也可以是rgb(0, 255, 255)&#xff0c;或是颜色名称 "red" div {background-color: red; /* 通过颜色名称设置 */background-color: #ff0000; /* 通过十六进制设…

面向对象程序设计之继承(C++)

1.继承的定义 1.1继承的概念 继承(inheritance)机制是⾯向对象程序设计使代码可以复⽤的最重要的⼿段&#xff0c;它允许我们在保持原有类特性的基础上进⾏扩展&#xff0c;增加⽅法(成员函数)和属性(成员变量)&#xff0c;这样产⽣新的类&#xff0c;称派⽣类。继承 呈现了⾯向…

给虚拟机linux系统安装交叉编译工具链

我们在电脑上写的代码编译生成的是X86架构的二进制文件&#xff0c;只能在X86平台上运行&#xff0c;而开发板是ARM架构因此需要安装交叉编译链工具&#xff0c;这样在电脑上写的代码交叉编译之后生成的是ARM架构的二进制文件。 绿色的字眼是与本文无关的只是这样有助于我们的…

推荐5款AI论文大纲生成器,一键极速生成!

在当今学术研究和写作领域&#xff0c;AI论文大纲生成器的出现极大地提高了写作效率和质量。以下是五款功能强大且全面的AI论文大纲生成器推荐&#xff1a; 一、千笔-AIPassPaper 千笔-AIPassPaper是一款基于深度学习和自然语言处理技术的AI写作助手&#xff0c;旨在帮助用户…

【探索数据结构与算法】希尔排序原理、实现与分析(图文详解)

目录 一、 引言 二、算法思想 三、算法步骤 四、代码实现 五、复杂度 &#x1f493; 博客主页&#xff1a;C-SDN花园GGbond ⏩ 文章专栏&#xff1a;探索数据结构与算法 一、 引言 希尔排序&#xff08;Shell Sort&#xff09;是插入排序的一种更高效的改进版本&#x…