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

数据结构---排序算法

个人介绍

hello hello~ ,这里是 code袁~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹
在这里插入图片描述
🦁作者简介:一名喜欢分享和记录学习的在校大学生
💥个人主页:code袁
💥 个人QQ:2647996100
🐯 个人wechat:code8896

专栏导航

code袁系列专栏导航
1.毕业设计与课程设计:本专栏分享一些毕业设计的源码以及项目成果。🥰🥰🥰
2.微信小程序开发:本专栏从基础到入门的一系开发流程,并且分享了自己在开发中遇到的一系列问题。🤹🤹🤹
3.vue开发系列全程线路:本专栏分享自己的vue的学习历程。

非常期待和您一起在这个小小的互联网世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨ 

在这里插入图片描述

在这里插入图片描述

排序算法学习笔记

1. 冒泡排序(Bubble Sort)

算法原理:冒泡排序是一种简单直观的排序算法,重复地遍历要排序的列表,依次比较相邻的两个元素,如果顺序不对则交换它们。
在这里插入图片描述

代码示例

def bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("排序后的列表:", arr)
  1. 时间复杂度
    若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值:Cmin = N - 1, Mmin = 0。所以,冒泡排序最好时间复杂度为O(N)。

    但是上述代码,不能扫描一趟就完成排序,它会进行全扫描。所以一个改进的方法就是,当冒泡中途发现已经为正序了,便无需继续比对下去。改进方法一会儿介绍。

    若初始文件是反序的,需要进行 N -1 趟排序。每趟排序要进行 N - i 次关键字的比较(1 ≤ i ≤ N - 1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:

    Cmax = N(N-1)/2 = O(N^2)

    Mmax = 3N(N-1)/2 = O(N^2)

    冒泡排序的最坏时间复杂度为O(N^2)。

    因此,冒泡排序的平均时间复杂度为O(N^2)。

    总结起来,其实就是一句话:当数据越接近正序时,冒泡排序性能越好。

算法稳定性假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。

2. 快速排序(Quick Sort)

算法原理:快速排序是一种分治算法,通过选择一个基准值,将列表分割成两部分,小于基准值的放在左边,大于基准值的放在右边,然后递归地对左右两部分进行排序。
在这里插入图片描述
快速排序的图例
在这里插入图片描述

代码示例

def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = quick_sort(arr)
print("排序后的列表:", sorted_arr)

3.2 时间复杂度
当数据有序时,以第一个关键字为基准分为两个子序列,前一个子序列为空,此时执行效率最差。
而当数据随机分布时,以第一个关键字为基准分为两个子序列,两个子序列的元素个数接近相等,此时执行效率最好。
所以,数据越随机分布时,快速排序性能越好;数据越接近有序,快速排序性能越差
3.3 时间复杂度
快速排序在每次分割的过程中,需要 1 个空间存储基准值。而快速排序的大概需要 logN次的分割处理,所以占用空间也是 logN 个。

3.4 算法稳定性在快速排序中,相等元素可能会因为分区而交换顺序,所以它是不稳定的算法。

3. 归并排序(Merge Sort)

算法原理
归并排序是一种分治算法,将列表分成两个子列表,分别对子列表进行排序,然后合并两个有序子列表。
算法思想
该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。
在这里插入图片描述

代码示例

def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])return merge(left, right)def merge(left, right):result = []i = j = 0while i < len(left) and j < len(right):if left[i] < right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1result += left[i:]result += right[j:]return result# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = merge_sort(arr)
print("排序后的列表:", sorted_arr)

3.2 时间复杂度
归并排序的形式就是一棵二叉树,它需要遍历的次数就是二叉树的深度,而根据完全二叉树的可以得出它的时间复杂度是O(n*log2n)。
3.3 空间复杂度
由前面的算法说明可知,算法处理过程中,需要一个大小为n的临时存储空间用以保存合并序列。
3.4 算法稳定性
在归并排序中,相等的元素的顺序不会改变,所以它是稳定的算法。
3.5 归并排序和堆排序、快速排序的比较
若从空间复杂度来考虑:首选堆排序,其次是快速排序,最后是归并排序。
若从稳定性来考虑,应选取归并排序,因为堆排序和快速排序都是不稳定的。
若从平均情况下的排序速度考虑,应该选择快速排序。

堆的

堆(Heap)是一种特殊的树形数据结构,通常用于实现优先队列。堆分为最大堆和最小堆,最大堆中父节点的值大于或等于任何一个子节点的值,最小堆中父节点的值小于或等于任何一个子节点的值。以下是关于堆的学习笔记,包括堆的性质、实现方式和应用场景:

堆的性质

  1. 堆是一个完全二叉树。
  2. 在最大堆中,父节点的值大于或等于任何一个子节点的值。
  3. 在最小堆中,父节点的值小于或等于任何一个子节点的值。

堆的实现

堆通常使用数组来表示,数组中的元素按照特定顺序排列以满足堆的性质。通过一些操作(如插入、删除、调整)来维护堆的性质。

堆的操作

  1. 插入(Insert):将新元素插入到堆中,并保持堆的性质。
  2. 删除最大元素(Delete Max):从最大堆中删除最大元素,并保持堆的性质。
  3. 调整(Heapify):将一个无序数组调整为堆结构。

在这里插入图片描述

代码示例

以下是一个使用Python实现最大堆的示例代码:

import heapqclass MaxHeap:def __init__(self):self.heap = []def push(self, val):heapq.heappush(self.heap, -val)def pop(self):return -heapq.heappop(self.heap)# 示例
max_heap = MaxHeap()
max_heap.push(5)
max_heap.push(2)
max_heap.push(9)
print(max_heap.pop())  # 输出:9

堆的应用场景

  1. 实现优先队列:堆可以高效地实现优先队列,保证每次取出的元素是优先级最高的。
  2. 堆排序:利用堆的性质进行排序,时间复杂度为O(nlogn)。

参考文章

🎉写在最后

🍻伙伴们,如果你已经看到了这里,觉得这篇文章有帮助到你的话不妨点赞👍或 Star ✨支持一下哦!手动码字,如有错误,欢迎在评论区指正💬~

你的支持就是我更新的最大动力💪~
在这里插入图片描述

相关文章:

数据结构---排序算法

个人介绍 hello hello~ &#xff0c;这里是 code袁~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f981;作者简介&#xff1a;一名喜欢分享和记录学习的…...

UE4 RPC进行网络同步

说明 基于UE本身提供的RPC同步机制 RPC远程过程调用允许客户端或服务器通过网络连接相互发送消息&#xff1a; 使用时需要注意&#xff1a; 1、必须从 Actor 上调用 2、Actor 必须被复制&#xff0c;注意勾选BP中Replicates&#xff0c;或使变量bReplicates true 3、注意如…...

HTML(6)——表单

目录 input标签基本使用 input标签占位 单选框radio 上传文件file 下拉菜单 文本域 label标签 按钮 input标签基本使用 input标签type属性值不同&#xff0c;则功能不同 <input type"..."> type属性值说明text文本框&#xff0c;用于输入单行文本p…...

Go基础编程 - 08 - 结构体

结构体 1. 自定义类型、类型别名1.1. 自定义类型1.2. 类型别名1.3. 类型定义和类型别名的区别 2. 结构体定义3. 结构体初始化4. 指针类型结构体5. 构造函数6. 方法和接收者6.1. 方法定义6.2. 方法调用6.3. 值方法和指针方法6.4. 指针方法使用场景6.5. 任意类型添加方法 7. 结构…...

基于Verilog表达的FSM状态机

基于Verilog表达的FSM状态机 1 FSM1.1 Intro1.2 Why FSM?1.3 How to do 在这里聚焦基于Verilog的三段式状态机编程&#xff1b; 1 FSM 1.1 Intro 状态机是一种代码实现功能的范式&#xff1b;一切皆可状态机&#xff1b; 状态机编程四要素&#xff1a;– 1.状态State&#…...

给一家银行做的数据中台系统架构方案书(DAMM)招投标用,虽然有内定潜规则,但是方案都是要的,不一定就是价格低就能中标,毕竟是上百万以上的单子

目录 概述需求分析系统架构DAMM设计思路数据治理数据安全实施计划维护和运营 1. 概述 1.1 项目背景 在数字化转型的浪潮中&#xff0c;银行业面临着越来越多的数据挑战与机遇。为了更好地利用数据资产&#xff0c;提升服务质量和运营效率&#xff0c;建立一个高效、灵活的数…...

【设计模式深度剖析】【6】【行为型】【中介者模式】

&#x1f448;️上一篇:迭代器模式 | 下一篇:观察者模式&#x1f449;️ 设计模式-专栏&#x1f448;️ 文章目录 中介者模式定义英文原文直译如何理解&#xff1f; 中介者模式的角色1. 中介者&#xff08;Mediator&#xff09;2. 具体中介者&#xff08;ConcreteMediato…...

金额转换但是接收对象类型未知时,金额转换公共方法囊括当对象为String\Integer\Number三种类型的转换方法

/** * deccription 金额转换方法 * param Object * value * return * return BigDecimal */ public BigDecimal getBigDecimal(Object value) { BigDecimal reValue new BigDecimal(0); if (value ! null) { …...

Commons-Collections篇-CC2链分析

前言 3.1-3.2.1版本中TransformingComparator并没有去实现Serializable接口&#xff0c;是不可以被序列化的&#xff0c;所以我们重新搭建一个4.0的具有漏洞的CC环境 CC2链主要使用的和CC4一样&#xff0c;但是区别在于CC2避免了使用Transformer数组&#xff0c;没有使用Insta…...

LeetCode 48.旋转图像

1.做题要求: 2.从此题我们可以看出规律为第几行要变为倒数第几列&#xff0c;所以我们最好先把二维数组存入一维数组中&#xff0c;然后先从最后一列遍历&#xff0c;把一维数组里的元素&#xff0c;依次等于遍历的元素即可: void rotate(int** matrix, int matrixSize, int*…...

Navicat导入json文件(json文件数据导入到MySQL表中)

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…...

避雷!又6本期刊被On Hold!ELSEVIER旗下影响因子高达10+SSCI上榜

【SciencePub学术】继《INFORMATION SCIENCES》被On Hold 之后&#xff0c;又新增3本SCIE期刊、3本SSCI期刊被列入On Hold名单。其中包含ELSEVIER旗下影响因子高达10的《RESOURCES POLICY》。 官方现在对期刊质量的管控越来越严格了&#xff0c;被标记为On Hold后的期刊中&…...

CSS 列表样式(ul)全面解析

CSS 列表样式是前端开发中常用的一种技术&#xff0c;用于定义无序列表&#xff08;ul&#xff09;的外观和行为。无序列表在网页布局和内容展示中扮演着重要角色&#xff0c;从导航菜单到内容清单&#xff0c;无所不在。通过CSS可以对无序列表的各个方面进行自定义&#xff0c…...

Python 库PySpark,一个超级强大的数据处理引擎

目录 01初识 PySpark 为什么选择 PySpark? 安装 PySpark 配置 PySpark 02基本操作 创建 RDD 基本 RDD 操作 03DataFrame 和 Spark SQL 创建 DataFrame 基本 DataFrame 操作 使用 Spark SQL 04机器学习与流处理 …...

UE4_材质_雨滴涟漪效果ripple effect_ben教程

学习笔记&#xff0c;不喜勿喷&#xff01;侵权立删&#xff0c;祝愿生活越来越好&#xff01; 雨水落下时会产生这些非常漂亮的同心环波纹&#xff0c;我们要做的第一件事是创建一个单个的圆环遮罩动画&#xff0c;我们希望环在开始的时候在中心很小&#xff0c;然后放大&…...

mac免费的ntfs软件哪个好 MAC读取NTFS硬盘格式

对于苹果用户来说&#xff0c;Mac电脑和移动硬盘已经成为日常工作中不可缺少的一部分&#xff0c;但有时我发现Mac打开移动硬盘只能读取无法写入&#xff0c;这是由于所连接的移动硬盘为NTFS格式。我们可以通过对硬盘格式化为Mac正常读写格式&#xff0c;或使用数据读写软件对N…...

轻兔推荐 —— who.cx

via&#xff1a;轻兔推荐 - https://app.lighttools.net/ 简介 who.cx是一个域名whois查询工具&#xff0c;界面简洁&#xff0c;可查询域名基本信息&#xff0c;注册续费价格&#xff0c;支持查看一级域名解析记录 - 对于已注册域名可以查看注册商注册时间、 过期时间等基础信…...

建筑幕墙甲级设计资质:申请条件与评分标准

建筑幕墙甲级设计资质的申请条件与评分标准可以清晰归纳如下&#xff1a; 申请条件 一、企业基本情况 独立企业法人资格&#xff1a;企业需具有独立企业法人资格。注册资本&#xff1a;注册资本不少于300万元人民币。 二、技术人员条件 主要技术负责人或总工程师&#xff…...

easy-es Map类型字段序列化问题:Unexpected character (‘n‘ (code 110)):

Data IndexName("demo") public class EasyEsDemo {IndexIdprivate String id;private String name;private int age;// 这个Map字段因为NameFilter过滤器&#xff0c;导致fastjson序列化后为{null:"value"}这种形式&#xff0c;insert报错private Map<…...

[Vue3:组件通信)子组件props接收和watch监听,emit发送父组件 (添加修改设置成绩,添加、删除选课记录)

文章目录 一&#xff1a;系统功能&#xff1a;设置成绩&#xff08;添加或修改&#xff09;交互逻辑&#xff1a;涉及页面 Page02.vue&#xff0c;ModalEdit.vue主页面Page.vue注入子页面&#xff0c;使用子页面标签属性主页面对子页面做通信&#xff0c;子页面ModalEdit接收参…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...

【51单片机】4. 模块化编程与LCD1602Debug

1. 什么是模块化编程 传统编程会将所有函数放在main.c中&#xff0c;如果使用的模块多&#xff0c;一个文件内会有很多代码&#xff0c;不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里&#xff0c;在.h文件里提供外部可调用函数声明&#xff0c;其他.c文…...