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

第六章:数据结构与算法-part3:数据结构算法提升

文章目录

  • 一、排序算法
    • 1.1 插入排序
      • 1、直接插入排序
        • 2、折半插入排序
        • 3、希尔排序
    • 1.2、交换排序法
      • 1、起泡排序
      • 2、快速排序
    • 1.3 选择类排序
      • 1、简单选择排序
  • 二、业务逻辑算法设计
    • 2.1 基本概念和术语
    • 2.2 静态查找表
    • 2.3、有序表的查找

一、排序算法

排序是数据处理过程中经常使用的一种重要的运算,排序的方法有很多种,本节主要讨论内排序的各种算法,并对每个排序算法的时间和空间复杂性以及算法的稳定性等进行讨论。

1、什么是排序?

排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如:将下列关键字序列:49,38,65,97,76,13, 27,49,调整为13,27,38,49,49, 65, 76, 97

2、排序算法的稳定性

排序算法的稳定性: 如果在对象序列中有两个对象r[i]和r[j],它们的关键字 k[i] == k[j],且在排序之前,对象r[i]排在r[j]前面。如果在排序之后,对象rr 仍在对象rr;的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。(值相同的两个不同位置上的数,在排序后,如果前后位置发生变化就不稳定。)
在这里插入图片描述

3、排序算法分类

按排序过程中使用到的存储介质来分,可以将排序分成两大类序和外排序。内排序是指在排序过程中所有数据均放在内存中处理,不需要使用外存的排序方法。而对于数据量很大的文件,在内存不足的情况下,则还需要使用外存,这种排序方法称为外排序。
内部排序:

  • 分类:插入排序,交换排序,选择排序,归并排序,基数排序
    在这里插入图片描述
    在这里插入图片描述

1.1 插入排序

基本思想:每一轮比较值在有序序列R中的位置
在这里插入图片描述
1、实现”一趟插入排序“可分三步进行:
在这里插入图片描述

1、直接插入排序

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
代码实现:
在这里插入图片描述
直接插入排序的时间复杂度:
在这里插入图片描述

2、折半插入排序

对于数据量不大时可以用直接插入排序,对于数据量较大时,选择折半插入排序。
折半插入排序基本思想是: 设在顺序表中有一 个对象序列 71],…, v[n-1]。其中,1],…, v[i-l] 是已经排好序的对象。在插入 i 时,利用折半搜索法寻找 vij的插入位置
在这里插入图片描述

3、希尔排序

基本思想:对待排记录序列先作“宏观”调整,再作“微观”调整。所谓“宏观”调整,指的是,“跳跃式”的插入排序。
具体做法:
在这里插入图片描述
在这里插入图片描述
例:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

1.2、交换排序法

交换排序是通过交换进行排序的方法,基本思想是两两比较待排序对象的关键字,如果发生逆序(即排列顺序与排序后的次序正好相反),则交换之,直到所有对象都排好序为止。

1、起泡排序

起泡排序的基本方法是:设待排序对象序列中的对象个数为n。最多作 n-1 趟排序。在第 i 趟中顺次两两比较r[j-1].Key和r[j].Key,j = i,i+1,…,n-i-1。如果发生逆序,则交换r[j-1]r[j]
在这里插入图片描述

起泡排序的过程

  • 起泡排序的结束条件为,最后一趟没有进行“交换记录
  • 一般情况下,每经过一趟“起泡”,“i 减一”.(但并不是每趟都如此)
    在这里插入图片描述在这里插入图片描述

2、快速排序

一趟快速排序 (一次划分)。
目标:找一个记录R[i],以它的关键字作为“枢轴”’,凡其关键字小于枢轴的记录均移动至该记录之前,反之,凡关键字大于枢轴的记录均移动至该记录之后
在这里插入图片描述
例:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
具体实现:
在这里插入图片描述
在这里插入图片描述
快速排序的效率:
当数据量较大时,效率较高,数据量较小时反而慢。
在这里插入图片描述

1.3 选择类排序

1、简单选择排序

在这里插入图片描述
在这里插入图片描述
效率分析:
在这里插入图片描述

二、业务逻辑算法设计

2.1 基本概念和术语

1、查找表:
在这里插入图片描述

2、关键字
在这里插入图片描述
3、查找
在这里插入图片描述
在这里插入图片描述
4、平均查找长度(Average Search Length):
在这里插入图片描述

2.2 静态查找表

使用线性表表示静态查找表。可用顺序或链式存储结构实现查找操作。
1、查找表的定义
在这里插入图片描述
2、基本操作
在这里插入图片描述
3、算法实现
在这里插入图片描述
4、算法“好”还是“坏”衡量?

  • 讨论各种查找算法时,常以算法的效率和存储开销来衡量查找算法的优劣。然而,效率和存储开销常常是相互制约的,很难两者兼顾。
  • 效率只是相对的,通常把对关键字的最多比较次数平均比较次数作为两个基本的技术指标,前者叫做最大查找长度(MSLMaximum Search Length),后者叫做平均查找长度(ASL,AverageSearch Length)
    在这里插入图片描述

2.3、有序表的查找

  • 上述顺序查找表中的查找算法简单,但平均查找长度较大,特别不适用于表长较大的查找表。
  • 若以有序表表示静态查找表,则查找过程可以基于“折半”进行

1、折半查找
在这里插入图片描述
写在最后:
课看完了,只能说质量不高,全程PPT,没意思,就当记录笔记吧。。。。

相关文章:

第六章:数据结构与算法-part3:数据结构算法提升

文章目录 一、排序算法1.1 插入排序1、直接插入排序2、折半插入排序3、希尔排序 1.2、交换排序法1、起泡排序2、快速排序 1.3 选择类排序1、简单选择排序 二、业务逻辑算法设计2.1 基本概念和术语2.2 静态查找表2.3、有序表的查找 一、排序算法 排序是数据处理过程中经常使用的…...

keras深度学习框架通过卷积神经网络cnn实现手写数字识别

昨天通过keras构建简单神经网络实现手写数字识别,结果在最后进行我们自己的手写数字识别的时候,准确率堪忧,只有60%。今天通过卷积神经网络来实现手写数字识别。 构建卷积神经网络和简单神经网络思路类似,只不过这里加入了卷积、池…...

Springboot启动异常 Command line is too long

Springboot启动异常 Command line is too long Springboot启动时直接报异常 Command line is too long. Shorten command line for xxxxxApplication or also for Spring Boot default解决方案: 修改 SystemApplication 的 Shorten command line,选择 JAR manife…...

PXE 装机(五十)

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 一、PXE是什么 二、PXE的组件 三、配置vsftpd 四、配置tftp 五、准备pxelinx.0文件、引导文件、内核文件 ​六、配置dhcp 七、创建default文件 八、配置pxe无人值守…...

C++ 虚函数与纯虚函数

目录 1. 虚函数 2. 纯虚函数 C 中的虚函数和纯虚函数都是实现多态的重要机制。多态可以让不同的对象以相同的方式进行操作,从而简化代码的编写和维护。 1. 虚函数 虚函数是一种在基类中声明的函数,可以在派生类中进行重写。在运行时,根据对…...

警告:Provides transitive vulnerable dependency maven:org.yaml:snakeyaml:1.30

1. 警告 SpringBoot 的 validation 依赖包含有易受攻击的依赖 snakeyaml。 警告信息如下: Provides transitive vulnerable dependency maven:org.yaml:snakeyaml:1.30 意思是:提供了可传递的易受攻击依赖 maven:org.yaml:snakeyaml:1.30 2. 警告示例 …...

中文命名实体识别

本文通过people_daily_ner数据集,介绍两段式训练过程,第一阶段是训练下游任务模型,第二阶段是联合训练下游任务模型和预训练模型,来实现中文命名实体识别任务。 一.任务和数据集介绍 1.命名实体识别任务 NER(Named En…...

WPF CommunityToolkit.Mvvm Messenger通讯

文章目录 环境WeakReferenceMessenger方法介绍无回调订阅发送Token区分有回调订阅发送 环境 CommunityToolkit.Mvvm Messenger 十月的寒流: 如何使用 CommunityToolkit.Mvvm 中的 Messenger 来进行 ViewModel 之间的通信 WeakReferenceMessenger 我这里只讲简单的弱Messenger…...

【杂言】写在研究生开学季

这两天搬进了深研院的宿舍,比中南的本科宿舍好很多,所以个人还算满意。受台风 “苏拉” 的影响,原本的迎新计划全部打乱,导致我现在都还没报道。刚开学的半个月将被各类讲座、体检以及入学教育等活动占满,之后又是比较…...

渗透测试漏洞原理之---【任意文件读取漏洞】

文章目录 1、概述1.1、漏洞成因1.2、漏洞危害1.3、漏洞分类1.4、任意文件读取1.4.1、文件读取函数1.4.2、任意文件读取 1.5、任意文件下载1.5.1、一般情况1.5.2、PHP实现1.5.3、任意文件下载 2、任意文件读取攻防2.1、路径过滤2.1.1、过滤../ 2.2、简单绕过2.2.1、双写绕过2.2.…...

合宙Air724UG LuatOS-Air LVGL API控件-图片 (Image)

图片 (Image) 图片IMG是用于显示图像的基本对象类型,图像来源可以是文件,或者定义的符号。 示例代码 -- 创建图片控件 img lvgl.img_create(lvgl.scr_act(), nil) -- 设置图片显示的图像 lvgl.img_set_src(img, "/lua/luatos.png") -- 图片…...

仿京东 项目笔记2(注册登录)

这里写目录标题 1. 注册页面1.1 注册/登录页面——接口请求1.2 Vue开发中Element UI的样式穿透1.2.1 ::v-deep的使用1.2.2 elementUI Dialog内容区域显示滚动条 1.3 注册页面——步骤条和表单联动 stepsform1.4 注册页面——滑动拼图验证1.5 注册页面——element-ui组件Popover…...

Spark与Flink的区别

分析&回答 (1)设计理念 1、Spark的技术理念是使用微批来模拟流的计算,基于Micro-batch,数据流以时间为单位被切分为一个个批次,通过分布式数据集RDD进行批量处理,是一种伪实时。 2、Flink是基于事件驱动的,是面向流的处理框架, Flink基于…...

未来智造:珠三角引领人工智能产业集群

原创 | 文 BFT机器人 产业集群是指产业或产业群体在地理位置上集聚的现象,产业集群的研究对拉动区域经济发展,提高区域产业竞争力具有重要意义。 从我国人工智能产业集群形成及区域布局来看,我国人工智能产业发展主要集聚在京津冀、长三角、…...

【Unity db】sqlite

背景 最近使用unity,需要用到sqlite,记录下使用过程 需要的动态库 Mono.Data.Sqlite.dll,这个文件下载参考下面链接 SqliteConnection的Close和Open 连接的概念: 在数据库编程中,连接是一个重要的概念&#xff0c…...

Linux 指令心法(四)`touch` 创建一个新的空文件

文章目录 命令的概述和用途命令的用法命令行选项和参数的详细说明命令的示例命令的注意事项或提示 命令的概述和用途 touch 是一个用于在 Linux 和 Unix 系统中创建空文件或更改现有文件的访问和修改时间的命令。如果指定的文件不存在,touch会创建一个新的空文件&a…...

分类算法系列②:KNN算法

目录 KNN算法 1、简介 2、原理分析 数学原理 相关公式及其过程分析 距离度量 k值选择 分类决策规则 3、API 4、⭐案例实践 4.1、分析 4.2、代码 5、K-近邻算法总结 🍃作者介绍:准大三网络工程专业在读,努力学习Java,涉…...

12. 微积分 - 梯度积分

Hi,大家好。我是茶桁。 上一节课,我们讲了方向导数,并且在最后留了个小尾巴,是什么呢?就是梯度。 我们再来回看一下但是的这个式子: [ f x f y...

Large Language Models and Knowledge Graphs: Opportunities and Challenges

本文是LLM系列的文章,针对《Large Language Models and Knowledge Graphs: Opportunities and Challenges》的翻译。 大语言模型和知识图谱:机会与挑战 摘要1 引言2 社区内的共同辩论点3 机会和愿景4 关键研究主题和相关挑战5 前景 摘要 大型语言模型&…...

Python操作Excel教程(图文教程,超详细)Python xlwings模块详解,

「作者主页」:士别三日wyx 「作者简介」:CSDN top100、阿里云博客专家、华为云享专家、网络安全领域优质创作者 「推荐专栏」:小白零基础《Python入门到精通》 xlwings模块详解 1、快速入门1、打开Excel2、创建工作簿2.1、使用工作簿2.2、操作…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

MySQL:分区的基本使用

目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区&#xff08;Partitioning&#xff09;是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分&#xff08;分区&#xff09;可以独立存储、管理和优化&#xff0c;…...

算法—栈系列

一&#xff1a;删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...