数据结构与算法

目录

数据结构与算法

为什么要学习数据结构和算法?

常见的数据结构

常用算法

插入排序

一、概念及其介绍

二、适用说明

三、过程图示

希尔排序

一、概念及其介绍

二、适用说明

三、过程图示

归并排序

一、概念及其介绍

二、适用说明

三、过程图示

随机化快速排序

一、概念及其介绍

二、适用说明

三、过程图示

双路快速排序

一、概念及其介绍

二、适用说明

三、过程图示

三路排序算法

一、概念及其介绍

二、适用说明

排序算法衍生问题

(1)归并排序和快速排序都使用了分治算法。

(2)逆序对的定义

(3)取数组中第 n 大的元素

 Reference Source:


数据结构与算法

数据结构(英语:data structure)是计算机中存储、组织数据的方式。

数据结构是一种具有一定逻辑关系,在计算机中应用某种存储结构,并且封装了相应操作的数据元素集合。它包含三方面的内容,逻辑关系、存储关系及操作。

不同种类的数据结构适合于不同种类的应用,而部分甚至专门用于特定的作业任务。例如,计算机网络依赖于路由表运作,B 树高度适用于数据库的封装。

为什么要学习数据结构和算法?

随着应用程序变得越来越复杂和数据越来越丰富,几百万、几十亿甚至几百亿的数据就会出现,而对这么大对数据进行搜索、插入或者排序等的操作就越来越慢,数据结构就是用来解决这些问题的。 

常见的数据结构

  • 栈(Stack):栈是一种特殊的线性表,它只能在一个表的一个固定端进行数据结点的插入和删除操作。
  • 队列(Queue):队列和栈类似,也是一种特殊的线性表。和栈不同的是,队列只允许在表的一端进行插入操作,而在另一端进行删除操作。
  • 数组(Array):数组是一种聚合数据类型,它是将具有相同类型的若干变量有序地组织在一起的集合。
  • 链表(Linked List):链表是一种数据元素按照链式存储结构进行存储的数据结构,这种存储结构具有在物理上存在非连续的特点。
  • 树(Tree):树是典型的非线性结构,它是包括,2 个结点的有穷集合 K。
  • 图(Graph):图是另一种非线性数据结构。在图结构中,数据结点一般称为顶点,而边是顶点的有序偶对。
  • 堆(Heap):堆是一种特殊的树形数据结构,一般讨论的堆都是二叉堆。
  • 散列表(Hash table):散列表源自于散列函数(Hash function),其思想是如果在结构中存在关键字和T相等的记录,那么必定在F(T)的存储位置可以找到该记录,这样就可以不用进行比较操作而直接取得所查记录。

常用算法

数据结构研究的内容:就是如何按一定的逻辑结构,把数据组织起来,并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。算法研究的目的是为了更有效的处理数据,提高数据运算效率。数据的运算是定义在数据的逻辑结构上,但运算的具体实现要在存储结构上进行。一般有以下几种常用运算:

  • 检索:检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值,找具有该字段值的节点。
  • 插入:往数据结构中增加新的节点。
  • 删除:把指定的结点从数据结构中去掉。
  • 更新:改变指定节点的一个或多个字段的值。
  • 排序:把节点按某种指定的顺序重新排列。例如递增或递减。

插入排序

一、概念及其介绍

插入排序(InsertionSort),一般也被称为直接插入排序。

对于少量元素的排序,它是一个有效的算法。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增 1 的有序表

。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动。

二、适用说明

插入排序的平均时间复杂度也是 O(n^2),空间复杂度为常数阶 O(1),具体时间复杂度和数组的有序性也是有关联的。

插入排序中,当待排序数组是有序时,是最优的情况,只需当前数跟前一个数比较一下就可以了,这时一共需要比较 N-1 次,时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的,此时需要比较次数最多,最坏的情况是 O(n^2)。

三、过程图示

假设前面 n-1(其中 n>=2)个数已经是排好顺序的,现将第 n 个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。

按照此法对所有元素进行插入,直到整个序列排为有序的过程,称为插入排序。

从小到大的插入排序整个过程如图示:

第一轮:从第二位置的 6 开始比较,比前面 7 小,交换位置。

第二轮:第三位置的 9 比前一位置的 7 大,无需交换位置。

第三轮:第四位置的 3 比前一位置的 9 小交换位置,依次往前比较。

第四轮:第五位置的 1 比前一位置的 9 小,交换位置,再依次往前比较。

......

就这样依次比较到最后一个元素。

希尔排序

一、概念及其介绍

希尔排序(Shell Sort)是插入排序的一种,它是针对直接插入排序算法的改进。

希尔排序又称缩小增量排序,因 DL.Shell 于 1959 年提出而得名。

它通过比较相距一定间隔的元素来进行,各趟比较所用的距离随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。

二、适用说明

希尔排序时间复杂度是 O(n^(1.3-2)),空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ,因此对中等大小规模表现良好,但对规模非常大的数据排序不是最优选择,总之比一般 O(n^2 ) 复杂度的算法快得多。

三、过程图示

希尔排序目的为了加快速度改进了插入排序,交换不相邻的元素对数组的局部进行排序,并最终用插入排序将局部有序的数组排序。

在此我们选择增量 gap=length/2,缩小增量以 gap = gap/2 的方式,用序列 {n/2,(n/2)/2...1} 来表示。

如图示例:

(1)初始增量第一趟 gap = length/2 = 4

(2)第二趟,增量缩小为 2

(3)第三趟,增量缩小为 1,得到最终排序结果

归并排序

一、概念及其介绍

归并排序(Merge sort)是建立在归并操作上的一种有效、稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

二、适用说明

当有 n 个记录时,需进行 logn 轮归并排序,每一轮归并,其比较次数不超过 n,元素移动次数都是 n,因此,归并排序的时间复杂度为 O(nlogn)。归并排序时需要和待排序记录个数相等的存储空间,所以空间复杂度为 O(n)。

归并排序适用于数据量大,并且对稳定性有要求的场景。

三、过程图示

归并排序是递归算法的一个实例,这个算法中基本的操作是合并两个已排序的数组,取两个输入数组 A 和 B,一个输出数组 C,以及三个计数器 i、j、k,它们初始位置置于对应数组的开始端。

A[i] 和 B[j] 中较小者拷贝到 C 中的下一个位置,相关计数器向前推进一步。

当两个输入数组有一个用完时候,则将另外一个数组中剩余部分拷贝到 C 中。

自顶向下的归并排序,递归分组图示:

对第三行两个一组的数据进行归并排序

对第二行四个一组的数据进行归并排序

整体进行归并排序

 

随机化快速排序

一、概念及其介绍

快速排序由 C. A. R. Hoare 在 1960 年提出。

随机化快速排序基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

二、适用说明

快速排序是一种比较快速的排序算法,它的平均运行时间是 O(nlogn),之所以特别快是由于非常精练和高度优化的内部循环,最坏的情形性能为 O(n^2)。像归并一样,快速排序也是一种分治的递归算法。从空间性能上看,快速排序只需要一个元素的辅助空间,但快速排序需要一个栈空间来实现递归,空间复杂度也为O(logn)。

三、过程图示

在一个数组中选择一个基点,比如第一个位置的 4,然后把4挪到正确位置,使得之前的子数组中数据小于 4,之后的子数组中数据大于 4,然后逐渐递归下去完成整个排序。

如何和把选定的基点数据挪到正确位置上,这是快速排序的核心,我们称为 Partition。

过程如下所示,其中 i 为当前遍历比较的元素位置:

如果是对近乎有序的数组进行快速排序,每次分区后子数组大小极不平衡,容易退化成 O(n^2) 的时间复杂度算法。我们需要对上述代码进行优化,随机选择一个基点做为比较,称为随机化快速排序算法。只需要在上述代码前加上下面一行,随机选择数组中一数据和基点数据进行交换。

swap( arr, l , (int)(Math.random()*(r-l+1))+l );

双路快速排序

一、概念及其介绍

双路快速排序算法是随机化快速排序的改进版本,partition 过程使用两个索引值(i、j)用来遍历数组,将 <v 的元素放在索引i所指向位置的左边,而将 >v 的元素放在索引j所指向位置的右边,v 代表标定值。

二、适用说明

时间和空间复杂度同随机化快速排序。 对于有大量重复元素的数组,如果使用上一节随机化快速排序效率是非常低的,导致 partition 后大于基点或者小于基点数据的子数组长度会极度不平衡,甚至会退化成 O(n*2) 时间复杂度的算法,对这种情况可以使用双路快速排序算法。

三、过程图示

使用两个索引值(i、j)用来遍历我们的序列,将 <=v 的元素放在索引 i 所指向位置的左边,而将 >=v 的元素放在索引 j 所指向位置的右边,平衡左右两边子数组。

三路排序算法

一、概念及其介绍

三路快速排序是双路快速排序的进一步改进版本,三路排序算法把排序的数据分为三部分,分别为小于 v,等于 v,大于 v,v 为标定值,这样三部分的数据中,等于 v 的数据在下次递归中不再需要排序,小于 v 和大于 v 的数据也不会出现某一个特别多的情况),通过此方式三路快速排序算法的性能更优。

二、适用说明

时间和空间复杂度同随机化快速排序。

三路快速排序算法是使用三路划分策略对数组进行划分,对处理大量重复元素的数组非常有效提高快速排序的过程。它添加处理等于划分元素值的逻辑,将所有等于划分元素的值集中在一起。

三、过程图示

我们分三种情况进行讨论 partiton 过程,i 表示遍历的当前索引位置:

(1)当前处理的元素 e=V,元素 e 直接纳入蓝色区间,同时i向后移一位。

(2)当前处理元素 e<v,e 和等于 V 区间的第一个位置数值进行交换,同时索引 lt 和 i 都向后移动一位

(3)当前处理元素 e>v,e 和 gt-1 索引位置的数值进行交换,同时 gt 索引向前移动一位。

最后当 i=gt 时,结束遍历,同时需要把 v 和索引 lt 指向的数值进行交换,这样这个排序过程就完成了,然后对 <V 和 >V 的数组部分用同样的方法再进行递归排序。

排序算法衍生问题

本小节对本教程的排序算法做一个总结。

(1)归并排序和快速排序都使用了分治算法。

顾名思义,就是将原问题分割查能同等结构的子问题,之后将子问题逐一解决后,原问题也就得到了解决。

(2)逆序对的定义

如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j],则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对。我们可以使用本教程的归并思想求逆序对的数量。

(3)取数组中第 n 大的元素

并不需要对整个数组进行排序,使用快速排序的思路求数组中第 n 大元素算法复杂度为 O(n)。

 Reference Source:

数据结构与算法 | 菜鸟教程

 

 

 

 

 

 

 

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

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

相关文章

python抓取网页视频

1. 喜马拉雅音频 1-1 喜马拉雅 import requests import json import time import random import hashliburl https://www.ximalaya.com/revision/play/v1/audio?id46103875&ptype1headers { user-agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.3…

【量化】量化原理浅析

前言 模型在端侧运行时&#xff0c;会追求模型保持原有精度的同时&#xff0c;让模型的运行速度更快。基本方向为模型压缩和加速&#xff0c;着力于减少网络参数量、降低计算复杂度。可通过以下方式实现&#xff1a; 针对网络结构本身进行改进&#xff0c;常用的3x3的卷积的叠加…

从零搭建开发脚手架 顺应潮流开启升级 - SpringBoot 从2.x 升级到3.x

文章目录 涉及升级项导入包修改SpringBoot3.x中spring.factories功能被移除 涉及升级项 升级JDK 8 -> JDK17 Spring Boot 2.3.7 -> Spring Boot 3.1.3 Mysql5.7.x -> Mysql8.x Mybatis-Puls 3.4.2 -> 3.5.3 knife4j 2.x -> 4.3.x sa-token 1.24.x -> 1.…

基于Xilinx UltraScale+ MPSOC(ZU9EG/ZU15EG)的高性能PCIe数据预处理平台

PCIE707是一款基于PCIE总线架构的高性能数据预处理FMC载板&#xff0c;板卡具有1个FMC&#xff08;HPC&#xff09;接口&#xff0c;1路PCIe x4主机接口、1个RJ45千兆以太网口、2个QSFP 40G光纤接口。板卡采用Xilinx的高性能UltraScale MPSOC系列FPGA作为实时处理器&#xff0c…

vue3 - 使用 xlsx 库将数据导出到 Excel 文件

GitHub Demo 地址 在线预览 xlsx是由SheetJS开发的一个处理excel文件的JavaScript库。它可以读取、编写和操作 Excel 文件 安装xlsx npm install xlsx --save实现一个通过的数据导出工具类 import * as XLSX from xlsx/*** description: 导出excel* param {any} dataList* p…

公司新招了个字节拿36K的人,让我见识到了什么才是测试扛把子......

5年测试&#xff0c;应该是能达到资深测试的水准&#xff0c;即不仅能熟练地开发业务&#xff0c;而且还能熟悉项目开发&#xff0c;测试&#xff0c;调试和发布的流程&#xff0c;而且还应该能全面掌握数据库等方面的技能&#xff0c;如果技能再高些的话&#xff0c;甚至熟悉分…

枚举enum

使用enum关键字定义提供枚举类的对象&#xff0c;多个对象用逗号分开&#xff0c;结尾用分号结束提供构造方法&#xff0c;给属性赋值使用public statiac final来修饰是属性提供get方法提供toString方法 public enum Season {SPRING("春天", "春暖花开"),…

linux下解决tomcat错误问题

错误一&#xff1a; Linux下Tomcat启动报错&#xff1a;Neither the JAVA_HOME nor the JRE_HOME environment variable is defined 原因&#xff1a;可能是Linux环境变了&#xff0c;需要在catalina.sh文件里指定JDK路径 解决方式&#xff1a; 在/bin/catalina.sh配置文件中加…

CSS详细基础(二)文本样式

插播一条CSS的工作原理&#xff1a; CSS是一种定义样式结构如字体、颜色、位置等的语言&#xff0c;被用于描述网页上的信息格式化和显示的方式。CSS样式可以直接存储于HTML网页或者单独的样式单文件。无论哪一种方式&#xff0c;样式单包含将样式应用到指定类型的元素的规则。…

mySQL 安装

一、windows安装包下载 mysql官网提供了两种安装方式&#xff0c;一个是zip安装&#xff0c;另一个是msi安装&#xff0c;这里简绍第一种安装方式&#xff0c;第二种简单&#xff0c;不再简绍 官网下载&#xff0c;根据自己需要选择版本&#xff1a;MySQL :: MySQL Community…

C#设置自动关机

功能&#xff1a;自动设置电脑关机时间&#xff0c;可取消 创建一个shutdown函数&#xff0c;bool isCancle&#xff0c;传入值为ture就取消关机&#xff0c;interval间隔时间&#xff0c;unit不带符号的整型 private static void ShutdownPC(bool isCancel, uint interval){P…

【Java 进阶篇】数据定义语言(DDL)详解

数据定义语言&#xff08;DDL&#xff09;是SQL&#xff08;结构化查询语言&#xff09;的一部分&#xff0c;它用于定义、管理和控制数据库的结构和元素。DDL允许数据库管理员、开发人员和其他用户创建、修改和删除数据库对象&#xff0c;如表、索引、视图等。在本文中&#x…

数据备份文件生成--根据表名生成对应的sql语句文件

最近客户有个需求&#xff0c;希望在后台增加手动备份功能&#xff0c;将数据导出下载保存。 当然&#xff0c;此方法不适用于海量数据的备份&#xff0c;这只适用于少量数据的sql备份。 这是我生成的sql文件&#xff0c;以及sql文件里的insert语句&#xff0c;已亲测&#x…

Oracle物化视图(Materialized View)

与Oracle普通视图仅存储查询定义不同&#xff0c;物化视图&#xff08;Materialized View&#xff09;会将查询结果"物化"并保存下来&#xff0c;这意味着物化视图会消耗存储空间&#xff0c;物化的数据需要一定的刷新策略才能和基表同步&#xff0c;在使用和管理上比…

Fortinet 2023上半年全球威胁态势研究报告:勒索软件检测成下降趋势,针对性攻击持续升温

近日&#xff0c;专注于推动网络与安全融合的全球网络安全领导者Fortinet&#xff08;NASDAQ&#xff1a;FTNT&#xff09;&#xff0c;发布《2023上半年全球威胁态势研究报告》。报告显示&#xff0c;2023 年上半年勒索软件检出数量继续下降、高级持续性威胁&#xff08;APT&a…

秋招面经记录

秋招面经记录 MySQLRedis项目分布式框架java网络数据结构设计模式HR手撕 MySQL Mysql中有1000万条数据&#xff0c;每次查询10条&#xff0c;该如何优化&#xff08;答&#xff1a;Limit子查询优化&#xff09; select t.* from t_topic t LIMIT 90000,10; 对上面的mysql语句说…

距离矢量路由协议RIP(含Cisco模拟器实验命令配置)

距离矢量路由协议RIP(含Cisco模拟器实验命令配置) 简介 距离矢量路由协议&#xff08;Routing Information Protocol, RIP&#xff09;是一种内部网关协议&#xff0c;它位于应用层&#xff0c;使用520 UDP端口。RIP基于距离矢量算法&#xff08;Bellham-Ford&#xff09;根据…

Linux socket 字节序

socket介绍 字节序 验证什么字节序 #include<stdio.h> int main() {union {short value;char btypes[sizeof(short)];} test;test.value 0x0102;if(test.btypes[0] 1 && test.btypes[1] 2) {printf("大端字节序\n");}else{printf("小端字节序…

服务网关Gateway_微服务中的应用

没有服务网关 问题&#xff1a; 地址太多安全性管理问题 为什么要使用服务网关 网关是微服务架构中不可或缺的部分。使用网关后&#xff0c;客户端和微服务之间的网络结构如下。 注意&#xff1a; 网关统一向外部系统&#xff08;如访问者、服务&#xff09;提供REST API。在Sp…

Unity中Shader用到的向量的乘积

文章目录 前言一、向量的乘法1、点积2、差积 二、点积&#xff08;结果是一个标量&#xff09;1、数学表示法2、几何表示法 三、叉积1、向量叉积的结果 与 两个相乘的向量互相垂直2、判断结果正负方向的方法&#xff1a;右手法则 前言 Unity中Shader用到的向量的点积 一、向量…