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

数据结构笔记39-48

碎碎念:想了很久,不知道数据结构这个科目最终该以什么笔记方式呈现出来,是纸质版还是电子版?后来想了又想,还是电子版吧?毕竟和计算机有关~(啊哈哈哈哈哈哈哈)

概率论已经更新完了,不出意料的话,六月末七月初会更新电子技术基础,七月中旬更新计算机组成原理


 数据结构45-4分钟搞定堆排序_哔哩哔哩_bilibili

39-48 

目录

 

排序算法

直接插入排序

折半插入排序  

​编辑

希尔排序 

快速排序

简单选择排序 

堆排序

插入元素:

删除元素:

归并排序

基数排序 


排序算法

直接插入排序

操作流程:

选取19(它是第一个数),并将其作为有序序列

第一轮:

选取35,

并与有序序列(也就是19)进行比较,

35>19,

于是在19的后面。

这样,19和35组成有序序列

 第二轮:

选取9,

并与有序序列(也就是19,35)进行比较,

9<35

9<19

于是9放在19前面。

这样9,19,35组成有序序列

 第三轮:

选取2,

并与有序序列(也就是9,19,35)进行比较,

2<<35

2<19

2<9

于是2放在9前面。

这样2,9,19,35组成有序序列

以此类推,得到最后结果

折半插入排序  

具体看这一步,如何安置15

 1.将15放到初始位置,也就是0的位置

2.low指向第一个元素

3.high指向15原来的位置

4.mid=(1+6)/2=3.5 取3,所以指向3的位置

5.15和17进行比较,15<17

6.high=mid-1,high指向2的位置

7.mid=(1+2)/2=1.5 取1 所以指向1的位置

8.15和2进行比较,2<15

9.low = mid+1,low指向2

low和high相等的时候结束了。所以15插入到后面


这些是另外一种思考方式,因为长课程那里的high不是指向元素15,而是指向元素35。

10.mid=(2+2)/2 ,mid指向2

11.15和2比较,15>2

12.low=mid+1

13.low>high,退出循环

 


希尔排序 

 1.间隔分组,这里有8个,因为为总长度的一半,因此为4组

2.进行组内排序

7<19

22>15

23<25

17>9

 3.再分组,为之前的一半,之前是4组,现在两组

3.进行组内排序

4.再分组,之前是2组,现在就1组

5.组内排序

冒泡排序

比较次数:数组元素-1

 

7和22进行比较

22和23进行比较

23和17进行比较,需要交换

23和19进行比较,需要交换

23和15进行比较,需要交换

最终23被确定,因此第二轮23不需要参与比较

7和22进行比较

22和17进行比较,需要交换

22和19进行比较,需要交换

22和15进行比较,需要交换

最终22被确定,因此第三轮22不需要参与比较

 以此类推

快速排序

1.选取中心轴,一般为首位,这里是元素19 

2.移动high指针,25>19,high指针继续移动,23>19,high指针继续移动,15<19,15拿出来,放到19原本的位置(0索引位置)

  3.移动low指针,9<19,7<19,17<19

5.当low=high时,中心轴被确定

第一轮排序结束

 第二轮:会分别产生两个low,两个high,缩小范围,以此类推进行排序

简单选择排序 

 

1. 在一堆数中找到最小的,13,然后与第一位进行交换

2.在一堆数中找到最小的,27,然后与第二位进行交换

以此类推

堆排序

 

我们调整的是大根堆,所以会把最大值放在根节点,且父节点会大于子节点

8/2-1,所以从3号位置开始调整

97>57,不用调整。

3号调整完了,就调整2号。

2号的父节点大于子节点,因此不用调整。

2号调整完了,就调整1号。

父节点小于子节点,因此取子节点中最大值放在1号位,也就是1,3号位置进行交换

1号调整完了,调整0号节点

父节点大于子节点,因此0,1号位置进行交换,

再看一眼,1号节点小于其子节点,因此将1,4号位置进行交换

最后,根节点为最大值,并且所有的父节点都大于其所拥有的子节点,即算完成

(这里的38和57还要对换一下)

插入元素:

插入85

只需要沿着这个根进行调整就好

85>38,85>76

 

删除元素:

删除堆顶元素97

将最末尾的38放在堆顶,将97拿出来,然后从上到下进行调整

对换的原则是要使得父节点大于子节点

38和其子节点相比,85更大,85和38进行对掉

38和76对掉

38和57对换

归并排序

 

两两进行比较,7和22,23和17,19和15,25和9

然后再进行7和22和23和17的比较,19和15和25和9的比较 

最后进行7和22和23和17和9和15和25和9的比较 

基数排序 

 

第一轮,按个位排 

 第二轮,按十位排

第三轮,按百位排,第三轮就是最后结果

 

相关文章:

数据结构笔记39-48

碎碎念&#xff1a;想了很久&#xff0c;不知道数据结构这个科目最终该以什么笔记方式呈现出来&#xff0c;是纸质版还是电子版&#xff1f;后来想了又想&#xff0c;还是电子版吧&#xff1f;毕竟和计算机有关~&#xff08;啊哈哈哈哈哈哈哈&#xff09; 概率论已经更新完了&…...

2-3 基于matlab的NSCT-PCNN融合和创新算法(NSCT-ML-PCNN )图像融合

基于matlab的NSCT-PCNN融合和创新算法&#xff08;NSCT-ML-PCNN &#xff09;图像融合。NSSCTest.m文件&#xff1a;用于查看利用NSSC算法分解出的图像并保存。其中的nlevel可调test.m文件&#xff1a;用于产生融合结果&#xff0c;其中一个参数需要设置&#xff1a;Low_Coeffs…...

机器学习笔记 - LoRA:大型语言模型的低秩适应

一、简述 1、模型微调 随着大型语言模型 (LLM) 的规模增加到数千亿,对这些模型进行微调成为一项挑战。传统上,要微调模型,我们需要更新所有模型参数。这也称为完全微调 (FFT) 。下图详细概述了此方法的工作原理。 完全微调FFT 的计算成本和资源需求很大,因为更新每…...

基于python实现视频和音频长度对齐合成并添加字幕

在许多视频编辑任务中&#xff0c;我们常常需要将视频和音频进行对齐&#xff0c;并添加字幕。本文将详细介绍如何使用Python实现这一功能&#xff0c;并在视频中添加中文字幕。我们将使用OpenCV处理视频帧&#xff0c;使用MoviePy处理音频和视频的合成&#xff0c;使用PIL库绘…...

爬虫-模拟登陆博客

import requests from bs4 import BeautifulSoupheaders {user-agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/76.0.3809.132 Safari/537.36 } # 登录参数 login_data {log: codetime,pwd: shanbay520,wp-submit: …...

【深度学习】【NLP】Bert理论,代码

论文 &#xff1a; https://arxiv.org/abs/1810.04805 文章目录 一、Bert理论BERT 模型公式1. 输入表示 (Input Representation)2. 自注意力机制 (Self-Attention Mechanism)3. Transformer 层 (Transformer Layer) 二、便于理解Bert的代码1. 自注意力机制2. Transformer 层3. …...

element table 点击某一行中按钮加载

在Element UI中&#xff0c;实现表格&#xff08;element-table&#xff09;中的这种功能通常涉及到数据处理和状态管理。当你点击某一行的按钮时&#xff0c;其他行的按钮需要动态地切换为加载状态&#xff0c;这可以通过以下步骤实现&#xff1a; 1.表格组件&#xff1a;使用…...

Linux开机自启/etc/init.d和/etc/rc.d/rc.local

文章目录 /etc/init.d和/etc/rc.d/rc.local的区别/etc/init.dsystemd介绍 /etc/init.d和/etc/rc.d/rc.local的区别 目的不同&#xff1a; /etc/rc.d/rc.local&#xff1a;用于在系统启动后执行用户自定义命令&#xff0c;适合简单的启动任务。 /etc/init.d&#xff1a;用于管理…...

DP:两个数组的dp问题

解决两个数组的dp问题的常用状态表示&#xff1a; 1、选取第一个字符串[0-i]区间以及第二个字符串[0,j]区间作为研究对象 2、根据题目的要求确定状态表示 字符串dp的常见技巧 1、空串是有研究意义的&#xff0c;引入空串可以帮助我们思考虚拟的边界如何进行初始化。 2、如…...

嵌入式Linux:格式化I/O

目录 1、格式化输出函数 1.1、printf()函数 1.2、fprintf()函数 1.3、dprintf()函数 1.4、sprintf()函数 1.5、snprintf()函数 2、格式化输入函数 2.1、scanf()函数 2.2、fscanf()函数 2.3、sscanf()函数 在Linux中&#xff0c;格式化I/O&#xff08;formatted I/O&a…...

【elementui源码解析】如何实现自动渲染md文档-第二篇

目录 1.概要 2.引用文件 1&#xff09;components.json 2&#xff09;json-template/string 3&#xff09;os.EOL 3.变量定义 4.模版填充 5.MAIN_TEMPLATE填充 6.src下的index.js文件 1&#xff09;install 2&#xff09;export 7.总结 1.概要 今天看第二个命令no…...

热门开源项目OpenHarmony

目录 1.概述 1.1.开源项目的意义 1.2.开源项目对软件行业的促进作用 1.3.小结 2.OpenHarmony 2.1.技术架构 2.2.分布式软总线 2.2.1.架构 2.2.2.代码介绍 2.2.2.1.代码目录 2.2.2.2.说明 2.2.2.3.发现组网和传输 2.2.2.3.1.发现 2.2.2.3.2.组网 2.2.2.3.3.传输…...

NewspaceAi之GPT使用新体验

GPT功能 使用地址&#xff1a;https://newspace.ai0.cn/ 上车 挂挡 踩油门&#xff0c;一脚到底&#xff0c;开始你的表演 问题1&#xff1a;你能做什么详细告诉我&#xff1f; 下面内容是GPT的回答 当然&#xff01;作为一个基于GPT-4架构的AI&#xff0c;我能够在许多方面为…...

详解红黑树

红黑树规则 节点是红色或黑色。根节点是黑色。每个叶子节点都是黑色的空节点&#xff08;NIL节点&#xff09;。每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 红黑树…...

探索JavaScript逆向工程与风控等级

探索JavaScript逆向工程与风控等级 在当今的网络安全领域&#xff0c;JavaScript逆向工程&#xff08;简称JS逆向&#xff09;已成为许多开发者和安全专家关注的焦点。JS逆向主要涉及对JavaScript代码的分析与理解&#xff0c;以发现其内部逻辑、数据流及潜在漏洞。这种技术常用…...

C++ 22 之 立方体案例

c22立方体案例.cpp #include <iostream> #include <string>using namespace std;class Cube{ private:int cube_l; // 长int cube_w; // 宽int cube_h; // 高public:// 设置长void set_l(int l){cube_l 1;}// 设置宽void set_w(int w){cube_w w;}// 设置高void …...

vue2使用antv/g6-editor实现可拖拽流程图

依赖下载 照着这个引入就好&#xff0c;然后npm install 源码 <template><div id"vue-g6-editor"><el-row><el-col :span"24"></el-col></el-row><!-- 工具栏 --><el-row><el-col :span"24&qu…...

springboot学习小结

背景 业务上需要开发&#xff0c;组里一位前辈给我指路 spring基础 什么是spring spring提供一个容器称为spring应用上下文&#xff0c;容器里可以创建和管理组件&#xff0c;组件会在容器里装配好&#xff0c;组件也可以叫bean。 装配不由组件创建他依赖的组件&#xff0…...

vue聊天发送Emoji表情

在用web端写聊天发送表情的功能中&#xff0c;使用web端有系统自带的unicode表情会出现每端不统一的情况&#xff0c;不好用不能统一&#xff0c;在这里我想到了一个非常好的思路&#xff0c;可以解决这个问题&#xff01; 那就是发送表情用图片的形式呈现&#xff0c;然后发给…...

360数字安全:2024年4月勒索软件流行态势分析报告

勒索软件传播至今&#xff0c;360 反勒索服务已累计接收到数万勒索软件感染求助。随着新型勒索软件的快速蔓延&#xff0c;企业数据泄露风险不断上升&#xff0c;勒索金额在数百万到近亿美元的勒索案件不断出现。勒索软件给企业和个人带来的影响范围越来越广&#xff0c;危害性…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...