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

算法题:快速排序

一、快速排序

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、快速排序总结 快速排序是一种高效的排序算法&#xff0c;基于分治法的思想。 分区操作是快速排序的核心&#xff0c;将数组分为两部分。 原地分区可以减少空间复杂度&#xff0c;提高效率。 快速排序的平均时间复杂度为 O(n log n)&#xff0c;但在最坏情况…...

Python的那些事第三十六篇:基于 Vega 和 Vega-Lite 的数据可视化解决方案,Altair 声明式可视化库

Altair 声明式可视化库:基于 Vega 和 Vega-Lite 的数据可视化解决方案 摘要 在数据科学和分析领域,有效的数据可视化是理解数据、发现模式和传达见解的关键。Python 作为数据科学的主要编程语言之一,提供了多种数据可视化库。其中,Altair 是一个基于 Vega 和 Vega-Lite 的…...

aws(学习笔记第三十课) 练习使用transit gateway

aws(学习笔记第三十课) 使用transit gateway 学习内容&#xff1a; 什么是transit gateway构造两个vpc&#xff0c;并且使用session manager访问private subnet的ec2练习使用transit gateway 1. 什么是transit gateway Transit Gateway的概念 Transit Gateway就是VPC和OnPro…...

Phpstudy中的MySQL无法正常启动或启动后自动暂停,以及sqlilab环境搭建出现的问题解决方法

【解决方法】 无法启动的原因是Phpstudy中的MySQL与本地的mysql重名&#xff0c;导致无法正常启动&#xff1b;所以这时我们就需要将本地的MySQL进行修改名称&#xff1b; 或者修改phpstudy中数据库的端口号&#xff0c;但是我觉得还是不是很好解决这种问题 最后一个方法&#…...

【Android】安卓付款密码输入框、支付密码输入框

如图 代码部分&#xff1a; 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&#xff1a;从模型调用到Prompt模板与输出解析的完整指南 02-玩转 LangChain Memory 模块&#xff1a;四种记忆类型详解及应用场景全覆盖 03-全面掌握 LangChain&#xff1a;从核心链条构建到动态任务分配的实战指南 04-玩转 LangChai…...

【AVL树】—— 我与C++的不解之缘(二十三)

什么是AVL树&#xff1f; AVL树发明者是G. M. Adelson-Velsky和E. M. Landis两个前苏联科学家&#xff0c;他们在1962年论文《An algorithm for the organization of information》中发表了AVL树。AVL树是最先发明的自平衡二叉搜索树&#xff0c;说白了就是能够自己控制平衡结构…...

用大白话解释日志处理Log4j 是什么 有什么用 怎么用

Log4j是什么&#xff1f; Log4j就像程序的“黑匣子”&#xff0c;专门用来记录软件运行时的各种信息&#xff0c;比如哪里报错、性能如何、用户操作轨迹等。它是Java领域最常用的日志框架之一&#xff0c;可以灵活控制日志内容、输出位置&#xff08;控制台、文件、数据库等&a…...

无人机遥控器的亮度 和 两个工作频率

工作频率 2.4000-2.4835 GHz &#xff0c; 5.725-5.850 GHz 1.这是一个无人机的遥控器的两个工作频率&#xff0c;为什么会有两个工作频率&#xff1f; 无人机的遥控器采用双频段设计&#xff08;2.4GHz 和 5.8GHz&#xff09;&#xff0c;主要是为了解决以下问题并优化性…...

【Linux】命令行参数 | 环境变量(四)

目录 前言&#xff1a; 一、命令行参数&#xff1a; 1.main函数参数 2.为什么有它&#xff1f; 二、环境变量&#xff1a; 1.main函数第三个参数 2.查看shell本身环境变量 3.PATH环境变量 4.修改PATH环境变量配置文件 5.HOME环境变量 6.SHELL环境变量 7.PWD环境变…...

算法002——复写零

力扣——复写零点击即可跳转 这道题还是运用 双指针&#xff0c;我们从左往右开始&#xff0c;让 cur 0&#xff0c;dest 0,当我们循环时&#xff0c;会覆盖后面的值&#xff0c;所以从左到右无法实现&#xff0c;我们运用 从右到左的方式。 以示例一数组为例&#xff0c;从…...

例子 DQN + CartPole: 深入思考一下,强化学习确实是一场智能冒险之旅!

强化学习的概念 在技术人员眼里&#xff0c;深度学习、强化学习&#xff0c;或者是大模型&#xff0c;都只是一些算法。无论是简单&#xff0c;还是复杂&#xff0c;我们都是平静的看待。当商业元素日益渗透进技术领域&#xff0c;人人言必称大模型的时候。技术人该反思一下&a…...

java 实现xxl-job定时任务自动注册到调度中心

xxl-job 自动注册(执行器和任务) 前言 xxl-job是一个功能强大、简单易用、高可用且可扩展性强的分布式定时任务框架/分布式任务调度平台。它适用于各种需要定时任务调度的场景,并可根据业务需求进行灵活配置和扩展。 xxl-job简介 xxl-job是一个开源的分布式定时任务框架,…...

esp32串口通信

1、线路图 2、打开电脑的串口终端 3、eps32通过串口往电脑的串口终端输出信息&#xff1a; from machine import UART, Pin import time# 初始化UART0&#xff0c;波特率设置为115200 uart UART(0, baudrate115200, tx1, rx3)# 主循环 while True:# 要发送的消息#某些串口终…...

蓝桥杯备赛-前缀和-可获得的最小取值

问题描述 妮妮学姐手头有一个长度为 nn 的数组 aa&#xff0c;她想进行 kk 次操作来取出数组中的元素。每次操作必须选择以下两种操作之一&#xff1a; 取出数组中的最大元素。取出数组中的最小元素和次小元素。 妮妮学姐希望在进行完 kk 次操作后&#xff0c;取出的数的和最…...

UniApp 中封装 HTTP 请求与 Token 管理(附Demo)

目录 1. 基本知识2. Demo3. 拓展 1. 基本知识 从实战代码中学习&#xff0c;上述实战代码来源&#xff1a;芋道源码/yudao-mall-uniapp 该代码中&#xff0c;通过自定义 request 函数对 HTTP 请求进行了统一管理&#xff0c;并且结合了 Token 认证机制 请求封装原理&#xff…...

边缘计算+多模态感知:户外监控核心技术解析与工程部署实践!户外摄像头监控哪种好?户外摄像头监控十大品牌!格行视精灵VS海康威视VS大华横评!

一、核心参数解析与选型逻辑 1.环境适应性设计 极端天气防护&#xff1a;优先选择IP66/67防护等级的设备&#xff0c;例如格行视精灵通过IP67防水防尘设计可应对暴雨、沙尘暴等复杂环境&#xff0c;其密封轴承结构可有效防止水汽侵蚀内部电路。 温度耐受范围&#xff1a;北方…...

Spring项目-抽奖系统(实操项目)(ONE)

^__^ (oo)\______ (__)\ )\/\ ||----w | || || 一&#xff1a;前言&#xff1a; 随着互联网技术的快速发展&#xff0c;线上营销活动已成为企业吸引用户、…...

STM32-智能小车项目

项目框图 ST-link接线 实物图&#xff1a; 正面&#xff1a; 反面&#xff1a; 相关内容 使用L9110S电机模块 电机驱动模块L9110S详解 | 良许嵌入式 测速模块 语音模块SU-03T 网站&#xff1a;智能公元/AI产品零代码平台 一、让小车动起来 新建文件夹智能小车项目 在里面…...

Python:字符串常见操作

find(子字符串&#xff0c;开始位置下标&#xff0c;结束位置下标) 注意&#xff1a;开始位置和结束位置下标可以省略&#xff0c;表示在整个字符串中查找 stasdfghjkl print(st.find(a))#输出结果为0&#xff0c;表明a在第一个位置默认从零开始&#xff0c;找不到则返回-1 …...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...

Vue3 PC端 UI组件库我更推荐Naive UI

一、Vue3生态现状与UI库选择的重要性 随着Vue3的稳定发布和Composition API的广泛采用&#xff0c;前端开发者面临着UI组件库的重新选择。一个好的UI库不仅能提升开发效率&#xff0c;还能确保项目的长期可维护性。本文将对比三大主流Vue3 UI库&#xff08;Naive UI、Element …...