Python算法——快速排序
快速排序(Quick Sort)是一种高效的分治排序算法,它选择一个基准元素,将数组分成两个子数组,小于基准的放在左边,大于基准的放在右边,然后递归地排序子数组。快速排序通常比冒泡排序和选择排序更高效,特别适用于大型数据集。本文将详细介绍快速排序的工作原理和Python实现。
快速排序的工作原理
快速排序的基本思想是:
- 选择一个基准元素(通常是数组中的某个元素)。
- 将数组分成两个子数组,一个包含小于基准的元素,另一个包含大于基准的元素。
- 递归地对两个子数组进行排序。
分治的关键在于如何选择基准元素以及如何分割数组。一种常见的方法是选择数组中间的元素作为基准,然后将数组分成两部分,一部分包含小于基准的元素,另一部分包含大于基准的元素。然后,递归地对这两部分进行排序。
下面是一个示例,演示快速排序的过程:
原始数组:[6, 5, 3, 1, 8, 7, 2, 4]
- 选择基准元素(通常选择中间元素,如 3)。
- 分割数组,小于 3 的元素在左边,大于 3 的元素在右边:[2, 1, 3, 5, 8, 7, 6, 4]
- 递归地对左边的子数组进行排序,结果为 [1, 2, 3]。
- 递归地对右边的子数组进行排序,结果为 [4, 5, 6, 7, 8]。
- 合并两个子数组,得到排序后的数组:[1, 2, 3, 4, 5, 6, 7, 8]。
Python实现快速排序
下面是Python中的快速排序实现:
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 是待排序的数组。
- 如果数组长度小于等于 1,则已经有序,直接返回。
- 选择基准元素 pivot,通常选择中间元素。
- 使用列表推导式将数组分成三部分:小于 pivot、等于 pivot 和大于 pivot 的元素。
- 递归地对左右两部分进行排序,然后合并结果。
示例代码
下面是一个使用Python进行快速排序的示例代码:
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 = [6, 5, 3, 1, 8, 7, 2, 4]
sorted_arr = quick_sort(arr)
print("排序后的数组:", sorted_arr)
时间复杂度
快速排序的平均时间复杂度为 O(n log n),其中 n 是数组的长度。它是一种高效的排序算法,通常优于冒泡排序和选择排序。然而,在最坏情况下,时间复杂度可能达到 O(n^2)。
总之,快速排序是一种高效的排序算法,通过选择基准元素和分割数组,递归地对子数组进行排序,实现了对数组的快速排序。了解快速排序有助于理解排序算法的高效性,并为大型数据集的排序提供了一个强大的工具。
相关文章:
Python算法——快速排序
快速排序(Quick Sort)是一种高效的分治排序算法,它选择一个基准元素,将数组分成两个子数组,小于基准的放在左边,大于基准的放在右边,然后递归地排序子数组。快速排序通常比冒泡排序和选择排序更…...
操作系统备考学习 day12 (第五章)
操作系统备考学习 day12 第五章 (输入/输出)I/O管理5.1 I/O管理概述5.1.1 I/O设备I/O设备的分类 5.1.2 I/O控制器I/O设备的电子部件 5.1.3 I/O控制方式程序直接控制方式中断驱动方式DMA方式DMA控制器通道控制方式 5.1.4 I/O软件层次结构用户层软件设备独…...
Elasticsearch删除映射类型
一 前言 官方解释:https://www.elastic.co/guide/en/elasticsearch/reference/6.0/removal-of-types.html 在elasticsearch6.0.0或更高的版本中创建索引仅能包含单个映射类型。在具有多种映射类型的5.x版本中创建的索引将继续像以前一样在elasticsearch6.x中运行。类型将在e…...
网络工程师进阶课:华为HCIP认证课程介绍
微思网络HCIP VIP试听课程:DHCP协议原理与配置https://www.bilibili.com/video/BV1cy4y1J7yg/?spm_id_from333.999.0.0 【赠送】IT技术视频教程,白拿不谢!思科、华为、红帽、数据库、云计算等等 https://xmws-it.blog.csdn.net/article/det…...
单行自动横向滚动——css实现
效果 封装组件 <template><div ref"container" class"scroll-area"><divref"content":class"[isScroll ? scroll : no-scroll]":style"{ color: fontColor }">{{ content }}</div></div> &…...
多线程基础
1. 线程创建的几种方式 2. 锁的类型 在学习JUC之前,加锁、等待、唤醒 分别使用的是 (synchronized、lock)、wait、notify在学习JUC开始,学会使用lock接口的其他实现类来进行上述操作,比如 ReentrantLock 3. 线程池 …...
贝锐向日葵亮相阿里云“云栖大会”:独创专利算法赋能全新云桌面
2023年10月31日-11月2日,一年一度的云栖大会如期举办,国产远程连接服务创领者贝锐受邀参与。活动现场,贝锐CTO张小峰进行了分享,宣布贝锐旗下国民级远程控制品牌“贝锐向日葵”与无影展开合作,同时全新的“云桌面”将于…...
QT在线安装5.15之前的版本(下载速度飞快)
使用最新的QT在线安装器,安装QT版本时只能安装5.15以及之后的版本,安装QT5.15之前的版本只能通过离线安装的方式,离线安装后还要自己去配置QT,离线安装还有个问题的,后续维护比较麻烦,QT的维护工具还要自己…...
零日漏洞预防
零日漏洞,是软件应用程序或操作系统(OS)中的意外安全漏洞,负责修复该漏洞的一方或供应商不知道该漏洞,它们仍然未被披露和修补,为攻击者留下了漏洞,而公众仍然没有意识到风险。 零日攻击是如何…...
企业内部外网向内网传输文件如何实现高效安全?
随着信息技术的发展,企业内部外网隔离已成为一种常见的网络安全措施,旨在防止外部攻击者入侵内部网络,保护企业的核心数据和业务系统。然而,企业内外网隔离也带来了一些问题,其中之一就是如何实现内外网之间的文件传输…...
C++--二叉搜索树初阶
前言:二叉搜索树是一种常用的数据结构,支持快速的查找、插入、删除操作,C中map和set的特性也是以二叉搜索树作为铺垫来实现的,而二叉搜索树也是一种树形结构,所以,在学习map和set之前,我们先来学…...
Type List(C++ 模板元编程)
定义 类型列表,字面意思就是一个存储类型的列表,例如std::tuple<int, float, double, std::string>就是一个类型列表。 template<typename ...Ts> struct type_list {};基础操作 操作约束:对于所有操作,均要求参数…...
使用老北鼻CharGPT对话查询 Qt/C++ 使用gumbo-parse解析加载的html全过程
记下使用老北鼻CharGPT对话查询 Qt/C解析html网页全过程。 [gumbo-parse] Gumbo是HTML5解析算法作为纯C99库实现,没有外部依赖性。它被设计为其他工具和库的构建模块,比如linters、验证器、模板语言、重构和分析工具。详细说明参考original-README.md 目…...
iOS App Store上传项目报错 缺少隐私政策网址(URL)解决方法
一、问题如下图所示: 二、解决办法:使用Google浏览器(翻译成中文)直接打开该网址 https://www.freeprivacypolicy.com/free-privacy-policy-generator.php 按照要求填写APP信息,最后将生成的网址复制粘贴到隐私…...
设计模式第一课-单例模式(懒汉模式和饿汉模式)
单例模式 个人理解:单例模式实际就是通过类加载的方式获取到一个对象,并且保证这个对象在使用中只有一个,不允许再次被创建 一、懒汉模式 1、懒汉模式的基础写法 代码解释: (1)、编写LazySingleton类的…...
Yaml文件详解
目录 1、Yaml文件详解 2、详解k8s中的port 3、Service yaml 4、Deployment yaml文件详解 5、Pod yaml文件详解 1、Yaml文件详解 Kubernetes 支持 YAML 和 JSON 格式管理资源对象 JSON 格式:主要用于 api 接口之间消息的传递 YAML 格式:用于配置和管…...
【题解 线段树】[蓝桥杯 2022 省 A] 选数异或
题目描述: [蓝桥杯 2022 省 A] 选数异或 题目描述 给定一个长度为 n n n 的数列 A 1 , A 2 , ⋯ , A n A_{1}, A_{2}, \cdots, A_{n} A1,A2,⋯,An 和一个非负整数 x x x, 给定 m m m 次查询, 每次询问能否从某个区间 [ l , r ] [l, r] [l,r] 中选择两…...
宠物喂食器方案智能开发设计
现在年轻人特别是在一、二、三线城市的,工作节奏快、加班、出差、旅游成常态,无法经常在宠物身边照看,宠物智能自动喂食机能够解放宠主的双手和解决不能长时间在处的无奈,很好地满足了年轻宠物主照顾宠物的需求。宠物主和宠物都需…...
chatgpt综述阅读理解
Summary of ChatGPT-Related research and perspective towards the future of large language models 摘要 本文总结了语言模型在遵循指令和人类反馈方面的相关工作,包括训练语言模型来理解指令并按照指令执行任务,以及提高语言模型的性能和理解能力的…...
XCTF-RSA-2:baigeiRSA2、 cr4-poor-rsa
baigeiRSA2 题目描述 import libnum from Crypto.Util import number from functools import reduce from secret import flagn 5 size 64 while True:ps [number.getPrime(size) for _ in range(n)]if len(set(ps)) n:breake 65537 n reduce(lambda x, y: x*y, ps) m …...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
Bean 作用域有哪些?如何答出技术深度?
导语: Spring 面试绕不开 Bean 的作用域问题,这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开,结合典型面试题及实战场景,帮你厘清重点,打破模板式回答,…...
给网站添加live2d看板娘
给网站添加live2d看板娘 参考文献: stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下,文章也主…...
书籍“之“字形打印矩阵(8)0609
题目 给定一个矩阵matrix,按照"之"字形的方式打印这个矩阵,例如: 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为:1,…...
怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)
+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...
