当前位置: 首页 > news >正文

数据结构与算法系列之插入排序

在这里插入图片描述

💗 💗 博客:小怡同学
💗 💗 个人简介:编程小萌新
💗 💗 如果博客对大家有用的话,请点赞关注再收藏 🌞

什么是插入排序

有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法–插入排序法
好比可以用打牌时对摸起的牌根据牌的点数来对其进行插入排列来描述。

在这里插入图片描述

实现思想

当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排序码与
array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移。 例如:
有一个有序区间,选其中一个数插入其中,这个数依次比较如果匹配失败则,换到下一个数比较。

在这里插入图片描述

插入排序的时间复杂度

时间复杂度是O(n^2) 在最坏情况下逆序需要每个数轮流插入 根据等差数列 1+2+3+…+n-1
所以时间复杂度是O(n^2) 在最好情况下只需要轮一遍 所以时间复杂度为O(n^2)

在这里插入图片描述

插入排序的稳定性

稳定性意思是两个元素之间的相对位置没有改变 如 4444 相等, 44在左 44在右,插入排序之后
44 仍在左 44 仍在右,这两个元素的相对位置没有改变。

在这里插入图片描述

代码实现

#include <stdio.h>
void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (tmp <= arr[end]){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}}int main()
{int arr[] = { 1,2,4,5,6,7,8,9,3 };int n = (sizeof(arr) / sizeof(arr[0]));InsertSort(arr, n);for (int i = 0; i < n; i++){printf("%d ", arr[i]);}return 0;
}

插入排序的优化——希尔排序

什么是希尔排序

希尔排序又称缩小增量排序,它通过比较相距一定间隔的元素来进行,各趟比较所用的距离随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。
通俗大意是:把原本一组的数组间断性分为几个数组,在对已经分完的数组进行插入排序

在这里插入图片描述

希尔排序的时间复杂度及稳定性

因为希尔排序的时间复杂度不好计算,因为gap的取值 方法很多,导致很难去计算。 时间复杂度;O(logNN)或者O(log3NN)
稳定性:不稳定

实现思想

先进行预排序,让数组接近有序,等到与排序之后 数组大多是有序的状态,大致上是有序数组,可进行插入排序。

void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//gap>1时是预排列 gap==1时相当有序排列for (int i = 0; i < n - gap; i += gap)//把间隔为gap的元素进行插入排序{int end = i;int tmp = arr[end + gap];while (end >= 0){if (tmp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}int main()
{int arr[] = { 1,2,4,5,6,7,8,9,3 };int n = (sizeof(arr) / sizeof(arr[0]));InsertSort(arr, n);for (int i = 0; i < n; i++){printf("%d ", arr[i]);}return 0;
}

在这里插入图片描述

相关文章:

数据结构与算法系列之插入排序

&#x1f497; &#x1f497; 博客:小怡同学 &#x1f497; &#x1f497; 个人简介:编程小萌新 &#x1f497; &#x1f497; 如果博客对大家有用的话&#xff0c;请点赞关注再收藏 &#x1f31e; 什么是插入排序 有一个已经有序的数据序列&#xff0c;要求在这个已经排好的数…...

Text to image论文精读ALR-GAN:文本到图像合成的自适应布局优化

ALR-GAN是北京工业大学学者提出的一种自适应布局优化生成对抗网络&#xff0c;其可以在没有任何辅助信息的情况下自适应地优化合成图像的布局。 文章发表于2023年&#xff0c;IEEE Transactions on Multimedia&#xff08;TMM&#xff09;期刊&#xff08;CCF B&#xff0c;JCR…...

windows版 redis在同一局域网下互联

项目场景&#xff1a; 同一局域网下各个主机互相连接同一个redis 问题描述 无法连接 原因分析&#xff1a; 没有放行对方的地址 解决方案&#xff1a; 修改配置文件 最重要的一步如下 然后把 redis.windows.conf的文件也照上面的修改一下保持一致 然后安装一下redis服务这…...

Near-Optimal Bayesian Online Assortment of Reusable Resources

摘要 受租赁服务在电子商务中的应用的激励&#xff0c;我们考虑为不同类型的到达消费者提供可重复使用资源的在线分类的收入最大化。我们针对贝叶斯环境中的最优在线策略设计了具有竞争力的在线算法&#xff0c;其中类型随时间独立于已知的异构分布绘制。在初始库存最小值cmin…...

数据库复习2

一. 简答题&#xff08;共1题&#xff0c;100分&#xff09; 1. (简答题) 存在数据库test&#xff0c;数据库中有如下表&#xff1a; 1.学生表 Student(Sno,Sname,Sage,Ssex) --Sno 学号,Sname 学生姓名,Sage 出生年月,Ssex 学生性别 主键Sno 2.教师表 Teacher(Tno,Tname) --T…...

公众号运营之竞品分析,教你拆解公众号

知己知彼&#xff0c;百战不殆&#xff0c;公众号运营亦是如此。 当运营者只关注自己账号的时候&#xff0c;很容易陷入某个误区中出不来。这个时候就要拓宽我们的视野&#xff0c;多去看看“外面的世界”&#xff0c;不要只局限于自己的一片小天地中。 看看同领域优秀公众号…...

python常见问题详解

Python python 没有多态&#xff0c;而是鸭子类型 多继承&#xff0c;没有接口&#xff0c;可通过语法糖实现接口的作用 lambda中只能有一句 "/"表示之前的参数是必须是位置参数&#xff0c;”**“表示是后面的必须是关键字参数 Python多进程 Python 多线程是伪多线…...

MyBatis-常用SQL操作

一、动态SQL 1.概述】 1.1动态SQL&#xff1a; 是 MyBatis 的强大特性之一&#xff0c;解决拼接动态SQL时候的难题&#xff0c;提高开发效 1.2分类&#xff1a; if choose(when,otherwise) trim(where,set) foreach 2.if 2.1 做 where 语句后面条件查询的,if 语句是可以…...

DSPE-PEG-TCO;磷脂-聚乙二醇-反式环辛烯科研用化学试剂简介

中文名称 磷脂-聚乙二醇-反式环辛烯 英文名称 DSPE-PEG-TCO 外观&#xff1a;粉末或半固体&#xff0c;取决于分子量。 溶剂&#xff1a;溶于大部分有机溶剂&#xff0c;如&#xff1a;DCM、DMF、DMSO、THF等等。在水中有很好的溶解性 稳定性&#xff1a;冷藏保存&#xff…...

华为OD机试真题Java实现【最小施肥机能效】真题+解题思路+代码(20222023)

最小施肥机能效 某农场主管理了一大片果园,fields[i]表示不同果林的面积,单位:( m 2 m^2 m2),现在要为所有的果林施肥且必须在 n 天之内完成,否则影响收成。 小布是果林的工作人员,他每次选择一片果林进行施肥,且一片果林施肥完后当天不再进行施肥作业。 假设施肥机的…...

【问题记录】【排查问题的方法总结】vue3中数据失去响应式?为什么数据变了,视图只更新了一次就不再更新了?

一、问题概述&#xff1a; 持续请求的数据变动之后&#xff0c;控制台输出绑定的响应式变量 mapObj 的确变了&#xff0c;但是视图上只更新了一次&#xff0c;后续就不再更新了。 二、排查过程&#xff1a; PC上用定时器setInterval模拟数据(全是小于0的数据)更新&#xff0…...

基于遗传算法的柔性生产调度研究(Matlab代码实现)

&#x1f468;‍&#x1f393;个人主页&#xff1a;研学社的博客&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5;&#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密…...

Heroku的12条准则

I. Codebase One codebase tracked in revision control, many deploys 要有代码仓库&#xff0c;多版本控制&#xff0c;如使用git来管理代码仓库。 II. Dependencies Explicitly declare and isolate dependencies 明确声明依赖&#xff0c;隔离依赖。强依赖往往会导致连…...

Qt图片定时滚动

目录参考结构PicturePlay.promain.cpppictureplay.hpictureplay.cpppictureplay.ui效果参考 Qt图片浏览器 QT制作一个图片播放器 Qt中自适应的labelpixmap充满窗口后&#xff0c;无法缩小只能放大 可以显示jpg、jpeg、png、bmp。可以从电脑上拖动图到窗口并显示出来或者打开文件…...

深度学习引言

动手学深度学习pytorch版-笔记原文链接日常生活中的机器学习机器学习中的关键组件数据模型目标函数优化算法各种机器学习问题监督学习回归分类标记问题搜索推荐系统序列学习无监督学习与环境互动强化学习特点小结原文链接 动手学深度学习pytorch中文版 日常生活中的机器学习 …...

ESP32 WIFI使用介绍

ESP32 WIFI 概述 WIFI 库支持配置及监控 ESP32 WIFI 连网功能。支持配置 station 模式&#xff08;即 STA 模式或 WIFI 客户端模式&#xff09;&#xff0c;此时 ESP32 连接到接入点&#xff08;AP&#xff09;。AP 模式&#xff08;即 soft-AP 模式或接入点模式&#xff09;&…...

JavaEE简单实例——MyBatis的一对一映射的嵌套查询的简单介绍和基础配置

简单介绍&#xff1a; 在前一章我们介绍了关于MyBatis的多表查询的时候的对应关系&#xff0c;其中有三种对应关系&#xff0c;分别是一对一&#xff0c;一对多&#xff0c;多对多的关系。如果忘记了这三种方式的对应形式可以去前面看看&#xff0c;一定要记住这三种映射关系的…...

详解指针(进阶版)(1)

前言&#xff1a;总篇章分为&#xff08;1&#xff09;和&#xff08;2&#xff09;&#xff0c;本篇内容包括&#xff1a;指针数组&#xff0c;数组指针&#xff0c;&数组名与数组名的区分 数组传参 &#xff0c;函数指针&#xff0c;函数指针数组 part 1&#xff1a;指…...

【OJ】盐荒子孙

&#x1f4da;Description: 盐体图 盐是对人类生存具有重要意义的物质之一。当中国古人从肉食为主转向谷食为主的时候&#xff0c;吃盐的需求就发生了&#xff0c;因为动物血肉里面包含有足够人体所需的盐分&#xff0c;而谷 物本身不包含盐分。在长达几十万年的旧石器时代&…...

Java数据结构 —— 手写线性结构(稀疏数组、栈、队列、链表)

目录 稀疏数组 顺序表 链表 单向顺序链表 双向链表 双向循环链表求解约瑟夫环&#xff08;Joseph&#xff09; 栈 顺序栈 队列 顺序队列 顺序循环队列 稀疏数组 当一个数组中大部分值为0,或者相同时&#xff0c;可以采用稀疏数组的方式来保存&#xff0c;从而节约存储…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...

【java】【服务器】线程上下文丢失 是指什么

目录 ■前言 ■正文开始 线程上下文的核心组成部分 为什么会出现上下文丢失&#xff1f; 直观示例说明 为什么上下文如此重要&#xff1f; 解决上下文丢失的关键 总结 ■如果我想在servlet中使用线程&#xff0c;代码应该如何实现 推荐方案&#xff1a;使用 ManagedE…...