数据结构——插入排序

基本思想:


直接插入排序是一种简单的插入排序法,其基本思想是:
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。
实际中我们玩扑克牌时,就用了插入排序的思想
 

直接插入排序:
当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移
 

代码实现:

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

时间复杂度分析:

//时间复杂度(最坏):O(N^2)--有序
//时间复杂度(最好):O(N)--顺序有序

与冒泡排序对比:

 乍一看,冒泡排序和插入排序十分相似,但是也有不同之处。就单独论代码量来说,插入排序比冒泡多一点,但是一个算法的好坏是不能已代码量来评判的,冒泡排序的时间复杂度固定是O(N^2)而我们插入排序是的时间复杂度在最好的情况下可以达到O(N)。

那么问题来了,为什么大家学的排序算法第一个都是冒泡排序这个这么“low”的算法呢?

虽然说,我们的冒泡排序是最鸡肋的排序算法,但是它有很好的教学意义,能让我们很容易的了解简单的排序方法,并且理解我们的循环体作用。

PS:看到这里了,码字不易,给个一键三连鼓励一下吧!有不足或者错误之处欢迎在评论区指出! 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

视频通话实时换脸:支持训练面部模型 | 开源日报 No.235

iperov/DeepFaceLive Stars: 19.7k License: GPL-3.0 DeepFaceLive 是一个用于 PC 实时流媒体或视频通话的人脸换装工具。 可以使用训练好的人脸模型从网络摄像头或视频中交换面部。提供多个公共面部模型&#xff0c;包括 Keanu Reeves、Mr. Bean 等。支持自己训练面部模型以…

图像处理到神经网络:线性代数的跨领域应用探索

作者介绍&#xff1a;10年大厂数据\经营分析经验&#xff0c;现任大厂数据部门负责人。 会一些的技术&#xff1a;数据分析、算法、SQL、大数据相关、python 欢迎加入社区&#xff1a;码上找工作 作者专栏每日更新&#xff1a; LeetCode解锁1000题: 打怪升级之旅 python数据分析…

Maven解决找不到依赖项

报错如图 方案一&#xff1a;Maven的Setting文件中添加albaba的镜像文件 1.下载maven &#xff1a;Maven – Download Apache Maven 2. 配置镜像 更改成这个&#xff1a; <mirror> <id>alimaven</id> <name>aliyun maven</name> <url&g…

Rust腐蚀服务器搭建架设教程ubuntu系统

Rust腐蚀服务器搭建架设教程ubuntu系统 大家好我是艾西一个做服务器租用的网络架构师。Rust腐蚀游戏对于服务器的配置有一定的要求很多小伙伴就思考用linux系统搭建的话占用会不会小一点&#xff0c;有一定电脑基础的小伙伴都知道Linux系统和windows系统相比较linux因为是面板…

短视频生成背景文字工具(前端工具)

过年这两天有些无聊就刷刷抖音&#xff0c;刷着刷着自己也蠢蠢欲动&#xff0c;想发上几个&#xff0c;可是却找不到合适自己的模板。由于个人喜欢一些古诗文之类的&#xff0c;所以自己简单的编写了一个小工具&#xff0c;如下图&#xff1a; 当设置好了之后&#xff0c;将浏…

小程序线多点路图绘制

需求 当接口返回一连串地图坐标&#xff0c;需要根据这些坐标串联起来&#xff0c;形成一个线路图&#xff08;本次使用步行导航线路图&#xff09;。 思路 首先优先想到使用小程序Map组件的polyline属性去进行展示。但是我们发现直接使用该属性进行坐标绘制画出来的数据都是…

《架构风清扬-Java面试系列第25讲》聊聊ArrayBlockingQueue的特点及使用场景

ArrayBlockingQueue是BlockingQueue接口的一个实现类之一 这个属于基础性问题&#xff0c;老规矩&#xff0c;我们将从使用场景和代码示例来进行讲解 来&#xff0c;思考片刻&#xff0c;给出你的答案 1&#xff0c;使用场景 实现&#xff1a;基于数组实现的有界阻塞队列&…

编写一个函数fun,它的功能是:实现两个字符串的连接(不使用库函数strcat),即把p2所指的字符串连接到p1所指的字符串后。

本文收录于专栏:算法之翼 https://blog.csdn.net/weixin_52908342/category_10943144.html 订阅后本专栏全部文章可见。 本文含有题目的题干、解题思路、解题思路、解题代码、代码解析。本文分别包含C语言、C++、Java、Python四种语言的解法完整代码和详细的解析。 题干 编写…

Docker② —— Cgroups详解

1. 概述 Cgroups 的全称是control groups&#xff0c;cgroups为每种可以控制的资源定义了一个子系统。Cgroups分为三个部分&#xff1a; cgroup 本身&#xff1a;对进程进行分组hierarchy&#xff1a;将 cgroup 形成树形结构subsystem&#xff1a;真正起到限制作用的部组件 cp…

【navicat】oracle library is not loaded 问题复现和解决方案

问题原因&#xff1a;客户端oci版本安装错误&#xff0c;navicat需要64位的oci,但是使用32位的oci。 解决方案&#xff1a;官网下载64位oci进行配置。本次演示的解决多了splplus&#xff0c;其实不必要安装也能运行。 首先判断是否数据库已经打开 尝试使用splplus连接数据库 1…

安装crossover游戏提示容量不足怎么办 如何把游戏放到外置硬盘里 Mac电脑清理磁盘空间不足

CrossOver作为一款允许用户在非原生操作系统上运行游戏和应用程序的软件&#xff0c;为不同平台的用户提供了极大的便利。然而&#xff0c;随着游戏文件大小的不断增加&#xff0c;内置硬盘的容量往往无法满足安装需求。幸运的是&#xff0c;通过一些简单的步骤&#xff0c;我们…

基于自注意力机制的长短期记忆神经网络(LSTM-SelfAttention)的回归预测

提示&#xff1a;MATLAB版本需要R2023a以上 基于自注意力机制的长短期记忆神经网络&#xff08;LSTM-SelfAttention&#xff09;是一种用于时序数据预测的模型。这个模型结合了两个不同的结构&#xff0c;即长短期记忆网络&#xff08;LSTM&#xff09;和自注意力机制&#xff…

2024.阳光能源追光计划暨大陆考察团交流分享会

近日大陆考察团抵达香港&#xff0c;受到了本司热情接待和安排。公司于4月27日下午举办了阳光能源追光计划主题交流会。 会上公司营销部总监张超&#xff0c;分享了阳光能源近几年的能源发展之路及公司新推出的追光计划&#xff0c;得到了大陆考察交流团团长杨国均先生的高度赞…

如何在 Visual Studio 中通过 NuGet 添加包

在安装之前要先确定Nuget的包源是否有问题。 Visual Studio中怎样更改Nuget程序包源-CSDN博客 1.图形界面安装 打开您的项目&#xff0c;并在解决方案资源管理器中选择您的项目。单击“项目”菜单&#xff0c;然后选择“管理 NuGet 程序包”选项。在“NuGet 包管理器”窗口中…

Dubbo应用可观测性升级指南与踩坑记录

应用从dubbo-3.1.*升级到dubbo-*:3.2.*最新稳定版本&#xff0c;提升应用的可观测性和度量数据准确性。 1. dubbo版本发布说明(可不关注) dubbo版本发布 https://github.com/apache/dubbo/releases 【升级兼容性】3.1 升级到 3.2 2. 应用修改点 应用一般只需要升级dubbo-s…

第72天:漏洞发现-Web框架中间件联动GobyAfrogXrayAwvsVulmap

案例一&#xff1a;某 APP-Web 扫描-常规&联动-Burp&Awvs&Xray Acunetix 一款商业的 Web 漏洞扫描程序&#xff0c;它可以检查 Web 应用程序中的漏洞&#xff0c;如 SQL 注入、跨站脚本攻击、身份验证页上的弱口令长度等。它拥有一个操作方便的图形用户界 面&#…

JavaEE初阶——多线程(七)——定时器

T04BF &#x1f44b;专栏: 算法|JAVA|MySQL|C语言 &#x1faf5; 小比特 大梦想 此篇文章与大家分享多线程的第七篇文章——关于定时器 如果有不足的或者错误的请您指出! 目录 4.定时器4.1标准库提供的定时器4.2自己实现一个定时器4.2.1任务类4.2.2Timer类4.2.3 有一个线程来负…

JavaScript云LIS系统源码 前端框架JQuery+EasyUI+后端框架MVC+SQLSuga大型医院云LIS检验系统源码 可直接上项目

JavaScript云LIS系统源码 前端框架JQueryEasyUI后端框架MVCSQLSuga大型医院云LIS检验系统源码 可直接上项目 云LIS系统概述&#xff1a; 云LIS是为区域医疗提供临床实验室信息服务的计算机应用程序&#xff0c;可协助区域内所有临床实验室相互协调并完成日常检验工作&#xff…

cve-2018-19518漏洞复现

一、靶场的启动 在相应的文件夹位置打开终端后进行如下操作 1.运行此靶场 sudo docker-compose up -d 2.查看启动环境 sudo docker ps 3.关闭此靶场环境 docker-compose down 二、漏洞内容简介 php imap扩展用户在php中执行邮件收发操作&#xff0c;其imap_open函数会调用rsh…

【java数据结构之八大排序(上)-直接插入排序,希尔排序,选择排序,堆排序,向下调整(大根堆,小根堆)等知识详解】

&#x1f308;个人主页&#xff1a;努力学编程’ ⛅个人推荐&#xff1a;基于java提供的ArrayList实现的扑克牌游戏 |C贪吃蛇详解 ⚡学好数据结构&#xff0c;刷题刻不容缓&#xff1a;点击一起刷题 &#x1f319;心灵鸡汤&#xff1a;总有人要赢&#xff0c;为什么不能是我呢 …