【算法练习】30:快速排序学习笔记

一、快速排序的算法思想

        原理:快速排序基于分治策略。它的基本思想是选择一个元素作为“基准”,将待排序序列划分为两个子序列,使得左边的子序列中的所有元素都小于基准,右边的子序列中的所有元素都大于基准。这个划分操作被称为分区。然后,对左右两个子序列分别递归地执行快速排序,直到整个序列有序。

        分区操作的关键在于确定基准元素在最终排序位置上,而它两侧的元素满足上述大小关系。实现时,可以通过一次遍历,将小于基准的元素交换至基准左侧,大于基准的元素交换至其右侧。这样,基准元素自然就落在了正确的位置上。

        时间复杂度:最好情况是当每次分区都能均匀划分数组,即每次划分后左右子数组的长度相差不大时,快速排序的时间复杂度为 O(n log n)。平均情况时间复杂度也为 O(n log n)最坏情况下当待排序数组已经是有序或接近有序时,每次分区只能得到一个子数组为空、另一个包含所有元素的情况,此时时间复杂度退化为O(n^2)

        空间复杂度:快速排序是一种递归算法,递归调用过程中需要使用栈来保存中间状态。在最坏情况下,递归深度为 n (完全不平衡的划分),因此空间复杂度为 O(n)。然而,实际应用中通过合理选择基准值和采用尾递归优化,递归深度往往远小于 n,平均空间复杂度接近 O(log n)

        稳定性:不稳定,在分区过程中,相等的元素可能会因为与基准元素的相对位置改变而发生相对顺序的改变,导致排序后相等元素的顺序与原始顺序不一致。

二、快速排序的算法步骤

  1. 选择基准:从待排序序列中选择一个元素作为基准。通常可以选择数组的第一个元素、最后一个元素、中间元素或随机元素。

  2. 分区:遍历待排序序列,将所有小于基准的元素交换到基准之前,所有大于基准的元素交换到基准之后。最后将基准元素放置在其最终位置上,此时基准左侧元素均小于基准,右侧元素均大于基准。

  3. 递归排序:对基准左侧(小于基准的子序列)和右侧(大于基准的子序列)分别递归执行快速排序。

三、基于Python的快速排序实现

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = 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 quicksort(left) + middle + quicksort(right)

# 示例
arr = [5, 2, 4, 6, 1, 3]
sorted_arr = quicksort(arr)
print(sorted_arr)  # 输出: [1, 2, 3, 4, 5, 6]

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Python函数和类3/6】函数的返回值

目录 知识回顾 目标 函数的返回值 Tips 练习 ​编辑return的其它特性 任意类型的返回值 返回多个值 return的位置 小结 局部变量 局部变量的作用域 全局变量 全局变量的作用域 同名变量 pi的作用域 总结 知识回顾 在上篇博客中&#xff0c;我们学习给函数设置参…

集群开发学习(一)(安装GO和MySQL,K8S基础概念)

完成gin小任务 参考文档&#xff1a; https://www.kancloud.cn/jiajunxi/ginweb100/1801414 https://github.com/hanjialeOK/going 最终代码地址&#xff1a;https://github.com/qinliangql/gin_mini_test.git 学习 1.安装go wget https://dl.google.com/go/go1.20.2.linu…

玩机进阶教程------手机定制机 定制系统 解除系统安装软件限制的一些步骤解析

定制机 在于各工作室与商家合作定制rom中有一些定制机。限制用户私自安装第三方软件。或者限制解锁 。无法如正常机登陆账号等等。定制机一般用于固定行业或者一些部门。专机专用。例如很多巴枪扫描机型等等。或者一些小牌机型。对于没有官方包的机型首先要导出各个分区来制作…

【OpenVINO™】使用 OpenVINO™ C# API 部署 YOLOv9 目标检测和实例分割模型(上篇)

YOLOv9模型是YOLO系列实时目标检测算法中的最新版本&#xff0c;代表着该系列在准确性、速度和效率方面的又一次重大飞跃。它通过引入先进的深度学习技术和创新的架构设计&#xff0c;如通用ELAN&#xff08;GELAN&#xff09;和可编程梯度信息&#xff08;PGI&#xff09;&…

复合数据类型

在C语言中&#xff0c;复合数据类型是指那些可以包含多个简单数据类型的数据类型。以下是一些常见的C语言复合数据类型以及相关的例子&#xff1a; 1. 数组&#xff08;Arrays&#xff09;&#xff1a; 数组是一种可以存储多个相同类型数据的数据结构。例如&#xff1a; #in…

从像素游戏到 3A 大作的游戏引擎/框架

Bevy —— Rust 构建的游戏引擎 Bevy 是一款由 Rust 语言构建且简单明了的数据驱动的游戏引擎&#xff0c;并将永远保持开源且免费。 Mach —— Zig 游戏引擎和图形工具包 Mach 是一个 Zig 游戏引擎和图形工具包&#xff0c;用于构建高性能、真正跨平台、健壮且模块化的游戏&…

日程安排组件DHTMLX Scheduler v7.0新版亮点 - 拥有多种全新的主题

DHTMLX Scheduler是一个类似于Google日历的JavaScript日程安排控件&#xff0c;日历事件通过Ajax动态加载&#xff0c;支持通过拖放功能调整事件日期和时间&#xff0c;事件可以按天、周、月三个种视图显示。 备受关注的DHTMLX Scheduler 7.0版本日前正式发布了&#xff0c;如…

JS原生DOM操作 - 获得元素/网页大小/元素宽高

文章目录 获得元素的方法获取页面元素位置宽高概念方法获得网页/元素宽高clientHeight和clientWidth&#xff1a;scrollHeight和scrollWidth&#xff1a;window.innerWidth&#xff1a;element.style.width&#xff1a; offsetXXX 获得网页元素的宽高和相对父元素位置&#xff…

有道词典网页版接口分析与爬虫研究

说明&#xff1a;仅供学习使用&#xff0c;请勿用于非法用途&#xff0c;若有侵权&#xff0c;请联系博主删除 作者&#xff1a;zhu6201976 一、目标站点 有道词典网页版&#xff1a;网易有道 二、目标接口 url&#xff1a;https://dict.youdao.com/jsonapi_s?doctypejson&…

通过8种加锁情况来弄懂加锁对于线程执行顺序的影响

1个资源类对象&#xff0c;2个线程&#xff0c;2个同步方法&#xff0c;第二个线程等待1s后开启。 //资源类 public class Example {//2个同步方法public synchronized void method1(){System.out.println("线程1正在执行...");}public synchronized void method2()…

(2022级)成都工业学院数据库原理及应用实验三:数据定义语言DDL

唉&#xff0c;用爱发电连赞都没几个&#xff0c;博主感觉没有动力了 想要完整版的sql文件的同学们&#xff0c;点赞评论截图&#xff0c;发送到2923612607qq,com&#xff0c;我就会把sql文件以及如何导入sql文件到navicat的使用教程发给你的 基本上是无脑教程了&#xff0c;…

Banana Pi BPI-M7 RK3588开发板运行RKLLM软件堆AI大模型部署

关于Banana Pi BPI-M7 Banana Pi BPI-M7 采用Rockchip RK3588&#xff0c;板载8/16/32G RAM内存和 64/128G eMMC存储&#xff0c;支持无线wifi6和蓝牙5.2。2x2.5G网络端口&#xff0c;1个HDMIout标准 输出口&#xff0c;2x USB3.0&#xff0c;2xTYPE-C&#xff0c;2x MIPI CSI…

Day96:云上攻防-云原生篇Docker安全系统内核版本漏洞CDK自动利用容器逃逸

目录 云原生-Docker安全-容器逃逸&系统内核漏洞 云原生-Docker安全-容器逃逸&docker版本漏洞 CVE-2019-5736 runC容器逃逸(需要管理员配合触发) CVE-2020-15257 containerd逃逸(启动容器时有前提参数) 云原生-Docker安全-容器逃逸&CDK自动化 知识点&#xff1…

Vue3基础语法

在这个章节中&#xff0c;简单的看下Vue3的基础语法&#xff0c;有了这些基础后&#xff0c;对写vue3单页也就没有什么问题了。 模板语法 在写html时&#xff0c;我们希望在某个节点绑定一个动态值时&#xff0c;是使用dom操作执行的&#xff0c;如下&#xff1a; <!DOCT…

(Java)数据结构——排序(第一节)堆排序+PTA L2-012 关于堆的判断

前言 本博客是博主用于复习数据结构以及算法的博客&#xff0c;如果疏忽出现错误&#xff0c;还望各位指正。 堆排序&#xff08;Heap Sort&#xff09;概念 堆排序是一种基于堆数据结构的排序算法&#xff0c;其核心思想是将待排序的序列构建成一个最大堆&#xff08;或最小…

大模型+交通治理,高德地图“评诊治”系统迎来全新升级

近日&#xff0c;由中国道路交通安全协会主办的第十四届中国国际道路交通安全产品博览会暨公安交警警用装备展(以下简称交博会)在厦门国际会展中心开幕&#xff0c;会上高德地图发布了全新升级的城市交通“评诊治”智能决策SaaS系统&#xff0c;以助力城市交通的可持续、精细化…

spring boot 集成rocketMq + 基本使用

1. RocketMq基本概念 1. NameServer 每个NameServer结点之间是相互独立&#xff0c;彼此没有任何信息交互 启动NameServer。NameServer启动后监听端口&#xff0c;等待Broker、Producer、Consumer连接&#xff0c; 相当于一个路由控制中心。主要是用来保存topic路由信息&#…

知识图谱与人工智能:携手共进

知识图谱与人工智能&#xff1a;携手共进 一、引言&#xff1a;知识图谱与人工智能的融合 在这个数据驱动的时代&#xff0c;知识图谱与人工智能&#xff08;AI&#xff09;之间的融合不仅是技术发展的必然趋势&#xff0c;也是推动各行各业创新的关键。知识图谱&#xff0c;作…

windows下pycharm中配置conda虚拟环境

目录 一&#xff1a;背景 二&#xff1a;安装conda环境 三&#xff1a;pycharm配置环境 四&#xff1a;注意问题 一&#xff1a;背景 在使用python的过程中&#xff0c;我们可能需要在一个windows环境中创建多个版本的python和安装不同的库去做一些开发任务。 使用conda&a…

TQ15EG开发板教程:在MPSOC上运行ADRV9371

首先需要在github上下载两个文件&#xff0c;本例程用到的文件以及最终文件我都会放在网盘里面&#xff0c; 地址放在本文最后。首先在github搜索hdl选择第一个&#xff0c;如下图所示 GitHub网址&#xff1a;https://github.com/analogdevicesinc/hdl/releases 点击releases…