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 …...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
