算法题:快速排序
一、快速排序
1、快速排序总结
-
快速排序是一种高效的排序算法,基于分治法的思想。
-
分区操作是快速排序的核心,将数组分为两部分。
-
原地分区可以减少空间复杂度,提高效率。
-
快速排序的平均时间复杂度为 O(n log n),但在最坏情况下(如输入数组已经排序)会退化到 O(n²)。
2、快速排序的基本思路
-
选择基准值(Pivot):
-
从数组中选择一个元素作为基准值。基准值的选择可以是数组的第一个元素、最后一个元素、中间元素,或者随机选择。
-
-
分区操作(Partition):
-
将数组分为两部分:
-
一部分包含小于基准值的元素。
-
另一部分包含大于基准值的元素。
-
-
基准值最终会放在它最终的位置上。
-
-
递归排序:
-
对小于基准值的部分递归调用快速排序。
-
对大于基准值的部分递归调用快速排序。
-
-
合并结果:
-
由于分区操作已经将数组分为两部分,递归排序后,数组自然有序,无需额外的合并操作。
-
3、快速排序和冒泡排序的区别
-
冒泡排序:
-
优点:实现简单,代码量少。
-
缺点:效率低,时间复杂度为 O(n²),不适用于大规模数据。
-
-
快速排序:
-
优点:效率高,平均时间复杂度为 O(n log n),适合大规模数据。
-
缺点:实现相对复杂,不稳定排序算法。
-
二、代码
def quick_sort(arr):# 如果数组长度小于等于1,直接返回if len(arr) <= 1:return arr# 选择基准值(这里选择最后一个元素)pivot = arr[-1]# 分区操作left = [x for x in arr[:-1] if x <= pivot] # 小于等于基准值的元素right = [x for x in arr[:-1] if x > pivot] # 大于基准值的元素# 递归排序左右两部分,并拼接结果return quick_sort(left) + [pivot] + quick_sort(right)# 示例
nums = [3, 2, 1, 5, 6, 4]
sorted_nums = quick_sort(nums)
print(sorted_nums) # 输出:[1, 2, 3, 4, 5, 6]相关文章:
算法题:快速排序
一、快速排序 1、快速排序总结 快速排序是一种高效的排序算法,基于分治法的思想。 分区操作是快速排序的核心,将数组分为两部分。 原地分区可以减少空间复杂度,提高效率。 快速排序的平均时间复杂度为 O(n log n),但在最坏情况…...
Python的那些事第三十六篇:基于 Vega 和 Vega-Lite 的数据可视化解决方案,Altair 声明式可视化库
Altair 声明式可视化库:基于 Vega 和 Vega-Lite 的数据可视化解决方案 摘要 在数据科学和分析领域,有效的数据可视化是理解数据、发现模式和传达见解的关键。Python 作为数据科学的主要编程语言之一,提供了多种数据可视化库。其中,Altair 是一个基于 Vega 和 Vega-Lite 的…...
aws(学习笔记第三十课) 练习使用transit gateway
aws(学习笔记第三十课) 使用transit gateway 学习内容: 什么是transit gateway构造两个vpc,并且使用session manager访问private subnet的ec2练习使用transit gateway 1. 什么是transit gateway Transit Gateway的概念 Transit Gateway就是VPC和OnPro…...
Phpstudy中的MySQL无法正常启动或启动后自动暂停,以及sqlilab环境搭建出现的问题解决方法
【解决方法】 无法启动的原因是Phpstudy中的MySQL与本地的mysql重名,导致无法正常启动;所以这时我们就需要将本地的MySQL进行修改名称; 或者修改phpstudy中数据库的端口号,但是我觉得还是不是很好解决这种问题 最后一个方法&#…...
【Android】安卓付款密码输入框、支付密码输入框
如图 代码部分: public class PayPasswordDialog extends AppCompatDialogFragment {private String mPayPass "";private String mTitle, mMoney;private final TextView[] mPayPassTextViewArray new TextView[6];private List<Integer> mPayP…...
Python异常处理:从入门到精通的实用指南
Langchain系列文章目录 01-玩转LangChain:从模型调用到Prompt模板与输出解析的完整指南 02-玩转 LangChain Memory 模块:四种记忆类型详解及应用场景全覆盖 03-全面掌握 LangChain:从核心链条构建到动态任务分配的实战指南 04-玩转 LangChai…...
【AVL树】—— 我与C++的不解之缘(二十三)
什么是AVL树? AVL树发明者是G. M. Adelson-Velsky和E. M. Landis两个前苏联科学家,他们在1962年论文《An algorithm for the organization of information》中发表了AVL树。AVL树是最先发明的自平衡二叉搜索树,说白了就是能够自己控制平衡结构…...
用大白话解释日志处理Log4j 是什么 有什么用 怎么用
Log4j是什么? Log4j就像程序的“黑匣子”,专门用来记录软件运行时的各种信息,比如哪里报错、性能如何、用户操作轨迹等。它是Java领域最常用的日志框架之一,可以灵活控制日志内容、输出位置(控制台、文件、数据库等&a…...
无人机遥控器的亮度 和 两个工作频率
工作频率 2.4000-2.4835 GHz , 5.725-5.850 GHz 1.这是一个无人机的遥控器的两个工作频率,为什么会有两个工作频率? 无人机的遥控器采用双频段设计(2.4GHz 和 5.8GHz),主要是为了解决以下问题并优化性…...
【Linux】命令行参数 | 环境变量(四)
目录 前言: 一、命令行参数: 1.main函数参数 2.为什么有它? 二、环境变量: 1.main函数第三个参数 2.查看shell本身环境变量 3.PATH环境变量 4.修改PATH环境变量配置文件 5.HOME环境变量 6.SHELL环境变量 7.PWD环境变…...
算法002——复写零
力扣——复写零点击即可跳转 这道题还是运用 双指针,我们从左往右开始,让 cur 0,dest 0,当我们循环时,会覆盖后面的值,所以从左到右无法实现,我们运用 从右到左的方式。 以示例一数组为例,从…...
例子 DQN + CartPole: 深入思考一下,强化学习确实是一场智能冒险之旅!
强化学习的概念 在技术人员眼里,深度学习、强化学习,或者是大模型,都只是一些算法。无论是简单,还是复杂,我们都是平静的看待。当商业元素日益渗透进技术领域,人人言必称大模型的时候。技术人该反思一下&a…...
java 实现xxl-job定时任务自动注册到调度中心
xxl-job 自动注册(执行器和任务) 前言 xxl-job是一个功能强大、简单易用、高可用且可扩展性强的分布式定时任务框架/分布式任务调度平台。它适用于各种需要定时任务调度的场景,并可根据业务需求进行灵活配置和扩展。 xxl-job简介 xxl-job是一个开源的分布式定时任务框架,…...
esp32串口通信
1、线路图 2、打开电脑的串口终端 3、eps32通过串口往电脑的串口终端输出信息: from machine import UART, Pin import time# 初始化UART0,波特率设置为115200 uart UART(0, baudrate115200, tx1, rx3)# 主循环 while True:# 要发送的消息#某些串口终…...
蓝桥杯备赛-前缀和-可获得的最小取值
问题描述 妮妮学姐手头有一个长度为 nn 的数组 aa,她想进行 kk 次操作来取出数组中的元素。每次操作必须选择以下两种操作之一: 取出数组中的最大元素。取出数组中的最小元素和次小元素。 妮妮学姐希望在进行完 kk 次操作后,取出的数的和最…...
UniApp 中封装 HTTP 请求与 Token 管理(附Demo)
目录 1. 基本知识2. Demo3. 拓展 1. 基本知识 从实战代码中学习,上述实战代码来源:芋道源码/yudao-mall-uniapp 该代码中,通过自定义 request 函数对 HTTP 请求进行了统一管理,并且结合了 Token 认证机制 请求封装原理ÿ…...
边缘计算+多模态感知:户外监控核心技术解析与工程部署实践!户外摄像头监控哪种好?户外摄像头监控十大品牌!格行视精灵VS海康威视VS大华横评!
一、核心参数解析与选型逻辑 1.环境适应性设计 极端天气防护:优先选择IP66/67防护等级的设备,例如格行视精灵通过IP67防水防尘设计可应对暴雨、沙尘暴等复杂环境,其密封轴承结构可有效防止水汽侵蚀内部电路。 温度耐受范围:北方…...
Spring项目-抽奖系统(实操项目)(ONE)
^__^ (oo)\______ (__)\ )\/\ ||----w | || || 一:前言: 随着互联网技术的快速发展,线上营销活动已成为企业吸引用户、…...
STM32-智能小车项目
项目框图 ST-link接线 实物图: 正面: 反面: 相关内容 使用L9110S电机模块 电机驱动模块L9110S详解 | 良许嵌入式 测速模块 语音模块SU-03T 网站:智能公元/AI产品零代码平台 一、让小车动起来 新建文件夹智能小车项目 在里面…...
Python:字符串常见操作
find(子字符串,开始位置下标,结束位置下标) 注意:开始位置和结束位置下标可以省略,表示在整个字符串中查找 stasdfghjkl print(st.find(a))#输出结果为0,表明a在第一个位置默认从零开始,找不到则返回-1 …...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南 背景介绍完整操作步骤1. 创建Docker容器环境2. 验证GUI显示功能3. 安装ROS Noetic4. 配置环境变量5. 创建ROS节点(小球运动模拟)6. 配置RVIZ默认视图7. 创建启动脚本8. 运行可视化系统效果展示与交互技术解析ROS节点通…...
C++--string的模拟实现
一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现,其目的是加强对string的底层了解,以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量,…...
聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇
根据 QYResearch 发布的市场报告显示,全球市场规模预计在 2031 年达到 9848 万美元,2025 - 2031 年期间年复合增长率(CAGR)为 3.7%。在竞争格局上,市场集中度较高,2024 年全球前十强厂商占据约 74.0% 的市场…...
GAN模式奔溃的探讨论文综述(一)
简介 简介:今天带来一篇关于GAN的,对于模式奔溃的一个探讨的一个问题,帮助大家更好的解决训练中遇到的一个难题。 论文题目:An in-depth review and analysis of mode collapse in GAN 期刊:Machine Learning 链接:...
