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

【DAY11 软考中级备考笔记】数据结构 查找和排序

数据结构 查找和排序 3月12日 – 天气:晴

1. 顺序查找

在这里插入图片描述

顺序查找就是简单的从头一个一个的进行比较,注意它的平均查找长度

2. 折半查找

在这里插入图片描述

折半查找和二叉排序树一致:

优点:查找效率很高

缺点:要求必须是循序存储并且表中元素必须有序

3. 分块查找

image-20240312204445143

分块查找实际上是结合了折半查找和顺序查找两种方式。

注意ASL的计算方式

优点:查找效率高于顺序查找,低于折半查找

4. 哈希表

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

使用取余的方法,需要注意取余的值:

取余的那个值 大于等于元素个数,小于等于比当前个数大的第一个质数。假设元素个数为9,则m的取值范围为【9,11】

image-20240312205703780

image-20240312205738937

image-20240312205720498

image-20240312205751411

采用链地址法的优点和不足:

  • 优点:平均查找长度短
  • 缺点:需要存储大量的指针,导致空间的浪费

image-20240312205855799

5. 直接插入排序

image-20240312210000626

  • 思想:直接插入排序的思想是向序列分为有序序列和无序序列。每次都从无序序列中取出一个值,然后跟有序序列的值一次进行比较,找到和事的位置进行插入。

  • 确定性:因此插入排序中在未完成时,没有一个元素的值时确定的。

  • 稳定性:稳定的

  • 时间复杂度:最好的情况下,只需要比较n-1次,最坏的情况是n^2

  • 空间复杂度:1

6. 希尔排序

image-20240312210356091

image-20240312211410777

  • 思想:希尔排序是直接插入排序的改进。它首先将元素进行分组,在组内进行直接插入排序,随着增量的逐渐减小,最终使得整个序列都有序
  • 确定性:不确定
  • 稳定性:不稳定
  • 时间复杂度:n^1.3
  • 空间复杂度:1

希尔排序最后一次排序为直接插入排序

7. 冒泡排序

image-20240312211543453

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

  • 思想:两两比较元素,将如果次序相反,则交换。这样每一轮排序都会选出最大的或者最小的元素,直到所有的元素都有序
  • 稳定性:稳定
  • 确定性:确定,每一次都会选择出最大的元素,且该元素的位置不会再次发生变化
  • 时间复杂度 n^2
  • 空间复杂度 1

8. 快速排序

image-20240312212009856

image-20240312212031166

  • 思想:在序列中任意选择一个元素,然后以这个元素为基准,将小于它的元素都放在它的左边,大于它的都放在右边。然后生成两个子序列。然后这两个子序列再一次执行上述操作。直到序列中只有一个元素
  • 稳定性:不稳定
  • 确定性:每次所选择的这个元素的位置是固定的
  • 时间复杂度:nlog
  • 空间复杂度:log (递归)

9. 简单选择排序

image-20240312212827496

image-20240312213156022

  • 思想:每次从带排序的序列中找到最小的元素,然后放在有序序列末尾。这里注意和直接插入排序区分。直接插入的思想是每一次都从未排序的序列中选择一个元素,然后放到已经排序序列里面的合适的位置
  • 稳定性:不稳定
  • 确定性:确定
  • 时间复杂度 n^2
  • 空间复杂度:1

相关文章:

【DAY11 软考中级备考笔记】数据结构 查找和排序

数据结构 查找和排序 3月12日 – 天气:晴 1. 顺序查找 顺序查找就是简单的从头一个一个的进行比较,注意它的平均查找长度 2. 折半查找 折半查找和二叉排序树一致: 优点:查找效率很高 缺点:要求必须是循序存储并且表中…...

华为机考:HJ102 字符统计

华为机考&#xff1a;HJ102 字符统计 描述 方法1 先将所有字符计算数量&#xff0c;在对比其中字符的assic码 #include<iostream> #include<vector> #include<algorithm> #include<string> using namespace std; bool cmp(pair<char, int> a,…...

安装配置HBase

HBase集群需要整个集群所有节点安装的HBase版本保持一致&#xff0c;并且拥有相同的配置&#xff0c;具体配置步骤如下&#xff1a; 1. 解压缩HBase的压缩包 2. 配置HBase的环境变量 3. 修改HBase的配置文件&#xff0c;HBase的配置文件存放在HBase安装目录下的conf中 4. 首…...

【更新】数字金融与企业ESG表现:效应、机制与“漂绿”检验数据集(2011-2022年)

参照温亚东&#xff08;2024&#xff09;的做法&#xff0c;本团队对来自统计与决策《数字金融与企业ESG表现&#xff1a;效应、机制与"漂绿"检验》一文中的基准回归部分进行复刻 一、数据介绍 数据名称&#xff1a;数字金融与企业ESG表现 参考期刊&#xff1a;《统…...

手写简易操作系统(五)--获得物理内存容量

前情提要 上一章中我们进入了保护模式&#xff0c;并且跳转到了32位模式下执行。这一章较为简单&#xff0c;我们来获取物理内存的实际容量。 一、获得内存容量的方式 在Linux中有多种方法获取内存容量&#xff0c;如果一种方法失败&#xff0c;就会试用其他方法。其本质上是…...

机器学习之DeepSequence软件使用学习3-预测突变效应

import theano import numpy as np import sys import pandas as pd import scipy #scipy 模块是 Python 中用于科学计算和数据分析的重要模块之一。它包含了许多高级的数学函数和工具&#xff0c;包括数值积分、优化、线性代数、统计等。 from scipy.stats import spearmanr #…...

Linux文件与文件系统的压缩

文章目录 Linux文件与文件系统的压缩Linux系统常见的压缩命令gzip&#xff0c;zcat/zmore/zless/zgrepbzip2&#xff0c;bzcat/bzmore/bzless/bzgreppxz&#xff0c;xzcat/xzmore/xzless/xzgrepgzip&#xff0c;bzip2&#xff0c;xz压缩时间对比打包命令&#xff1a;tar打包命令…...

ubuntu 中进入python 编辑如何退出到命令行

文章目录 在Python解释器&#xff08;交互式命令行&#xff09;中&#xff0c;你可以使用 exit()函数或 CtrlD&#xff08;在Unix/Linux/macOS上&#xff09;或 CtrlZ然后输入 Enter&#xff08;在Windows上&#xff09;来退出Python解释器并返回到命令行。 以下是具体的步骤&a…...

2024.3.12 C++

1.思维导图 2.自己封装一个矩形类(Rect)&#xff0c;拥有私有属性:宽度(width)、高度(height),定义公有成员函数: 初始化函数:void init(int w, int h)更改宽度的函数:set_w(int w)更改高度的函数:set_h(int h) 输出该矩形的周长和面积函数:void show() #include <iostream…...

飞塔防火墙开局百篇——002.FortiGate上网配置——透明模式配置(Transparent)

透明模式配置 开启透明模式创建策略 在不改变现有网络拓扑前提下&#xff0c;将防火墙NGFW以透明模式部署到网络中&#xff0c;放在路由器和交换机之间&#xff0c;防火墙为透明模式&#xff0c;对内网网段192.168.1.0/24的上网进行4~7层的安全防护。 登陆FortiGate防火墙界面&…...

代码随想录算法训练营第52天|300.最长递增子序列 674.最长连续递增序列 718.最长重复子数组

300.最长递增子序列 这道题还挺简单的&#xff0c;咱们设置dp[i]表示到第i个数字时的递增子序列的最长的值&#xff0c;那么dp[i]就要遍历从0到i-1的数&#xff0c;也就是看看当前这个数字是否比前面的数字大&#xff0c;如果大的话就看看现在的子序列长度是否会长于前面那个数…...

分享一些开源的游戏仓库

1.CnC_Remastered_Collection 红色警戒95版本 https://github.com/electronicarts/CnC_Remastered_Collection gitee仓库分流&#xff1a;https://gitee.com/loswdarmy/CnC_Remastered_Collection 2.Far-Cry-1-Source-Full 孤岛惊魂1 https://github.com/StrongPC123/Far-Cry-…...

Java详解:单列 | 双列集合 | Collections类

○ 前言&#xff1a; 在开发实践中&#xff0c;我们需要一些能够动态增长长度的容器来保存我们的数据&#xff0c;java中为了解决数据存储单一的情况&#xff0c;java中就提供了不同结构的集合类&#xff0c;可以让我们根据不同的场景进行数据存储的选择&#xff0c;如Java中提…...

Centos7 使用docker来部署mondb

参考官方手册&#xff1a; https://www.mongodb.com/docs/manual/tutorial/install-mongodb-community-with-docker/#std-label-docker-mongodb-community-install 使用脚本快速安装docker curl -fsSL https://get.docker.com -o get-docker.sh | bash get-docker.sh使用 Doc…...

Java SE入门及基础(35)

接口 1. 概念 在软件工程中&#xff0c;软件与软件的交互很重要&#xff0c;这就需要一个约定。每个程序员都应该能够编写实现这样的约定。接口就是对约定的描述。 In the Java programming language, an interface is a reference type, similar to a class, that can con…...

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的常见车型识别系统(Python+PySide6界面+训练代码)

摘要&#xff1a;本文深入探讨了如何应用深度学习技术开发一个先进的常见车型识别系统。该系统核心采用最新的YOLOv8算法&#xff0c;并与早期的YOLOv7、YOLOv6、YOLOv5等版本进行性能比较&#xff0c;主要评估指标包括mAP和F1 Score等。详细解析了YOLOv8的工作机制&#xff0c…...

Sqoop 学习

参考视频 大数据Sqoop教程丨从零开始讲解大数据业务及数据采集和迁移需求_哔哩哔哩_bilibili 介绍 Sqoop是Hadoop生态体系和RDBMS&#xff08;关系型数据库&#xff09;体系之间传送数据的一种工具 Hadop生态系统&#xff1a;HDFS&#xff0c;Hbase&#xff0c;Hive等 RDBMS包…...

Ollama 只安装 Ollama,本地快速部署谷歌开源大模型Gemma(基于Ollama)

参考&#xff1a;本地快速部署谷歌开源大模型Gemma(基于Ollama) - 知乎 确保系统更新: Bash sudo apt update && sudo apt upgrade 需要先下载Ollama&#xff0c;版本要求0.1.26及以上 运行curl -fsSL https://ollama.com/install.sh | sh 监听 Ollama API 接…...

一条 sql 语句可能导致的表锁和行锁以及死锁检测

锁 MDL 当对一个表做增删改查操作的时候&#xff0c;加 MDL 读锁&#xff1b;当要对表做结构变更操作的时候&#xff0c;加 MDL 写锁 ALTER TABLE tbl_name NOWAIT add column ... ALTER TABLE tbl_name WAIT N add column ... …...

prometheus 原理(架构,promql表达式,描点原理)

大家好&#xff0c;我是蓝胖子&#xff0c;提到监控指标&#xff0c;不得不说prometheus&#xff0c;今天这篇文章我会对prometheus 的架构设计&#xff0c;promql表达式原理和监控图表的绘图原理进行详细的解释。来让大家对prometheus的理解更加深刻。 架构设计 先来看看&am…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...

SpringAI实战:ChatModel智能对话全解

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

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...