Python实现快速排序（python快速排序算法）
off999 2024-10-04 00:36 28 浏览 0 评论
'''
快速排序原理：对于给定的一组序列，选择一个基准数，通过一论排序后，将原序列分为两部分，
使得前面的比后面的小，然后再依次对前后进行拆分并排序，递归该过程，直到序列中所有数据均有序为止。
算法过程如下：1.拆分：将序列拆分成2个非空子序列2.递归求解：通过递归调用快速分别对2个子序列进行排序3.合并：把排序好的2个子序列进行合并
例如数组：{49,38,65,97,76,13,27,49}，具体排序过程如下：
第一次排序过程：
初始化：[49,38,65,97,76,13,27,49]
第1次交换：[27,38,65,97,76,13,49,49]
第2次交换：[27,38,49,97,76,13,65,49]
第3次交换：[27,38,13,97,76,49,65,49]
第4次交换：[27,38,13,49,76,97,65,49]
整个排序过程：
初始化：[49,38,65,97,76,13,27,49]
第1次排序后：[27 38 13] 49 [76 97 65 49]
第2次排序后：[13] 27 [38] 49 [49 65] 76 [97]
第3次排序后：13 27 38 49 49 [65] 76 97
最后排序结果：13 27 38 49 49 65 76 97
'''
#代码实现
def quick_sort(arrays,left,right):
if left>=right:
return list
key=arrays[left]
low=left
high=right
while left<right:
while left < right and arrays[right]>= key:
right-=1
arrays[left]=arrays[right]
while left < right and arrays[left]<=key:
left+=1
arrays[right]=arrays[left]
arrays[right]=key
quick_sort(arrays,low,left-1)
quick_sort(arrays,left+1,high)
return arrays
if __name__=="__main__":
arrays=[49,38,65,97,76,13,27,49]
print("排序前：" + str(arrays))
print("排序后："+str(quick_sort(arrays,0,len(arrays)-1)))
排序结果如下：
时间复杂度：最坏的情况下，每次划分将问题分解后，基准元素的一侧没有元素，其中一侧为规模为n-1的子问题， 递归求解该子问题，所需时间为递归求解该子问题，所需时间为T(n-1),合并：因为是原地排序，合并不需要时间复杂度，所以时间复杂度为 O(n2)理想的情况下，每次划分将问题分解为两个规模为n/2的子问题，递归求解两个规模的子问题， 所需时间为2T(n/2) 合并：因为是原地排序，合并不需要时间复杂度，所以时间复杂度为 O(nlogn) 空间复杂度：O(logn)
欢迎大家关注我的微信公众号
相关推荐
- 使用 python-fire 快速构建 CLI_如何搭建python项目架构
-
命令行应用程序是开发人员最好的朋友。想快速完成某事？只需敲击几下键盘，您就已经拥有了想要的东西。Python是许多开发人员在需要快速组合某些东西时选择的第一语言。但是我们拼凑起来的东西在大多数时候并...
- Python 闭包:从底层逻辑到实战避坑，附安全防护指南
-
一、闭包到底是什么？你可以把闭包理解成一个"带记忆的函数"。它诞生时会悄悄记下自己周围的变量，哪怕跑到别的地方执行，这些"记忆"也不会丢失。就像有人出门时总会带上...
- 使用Python实现九九乘法表的打印_用python打印一个九九乘法表
-
任务要求九九乘法表的结构如下：1×1=11×2=22×2=41×3=32×3=63×3=9...1×9=92×9=18...9×9=81使用Python编写程序，按照上述格式打印出完整的九...
- 吊打面试官(四)--Java语法基础运算符一文全掌握
-
简介本文介绍了Java运算符相关知识，包含运算规则，运算符使用经验，特殊运算符注意事项等，全文5400字。熟悉了这些内容，在运算符这块就可以吊打面试官了。Java运算符的规则与特性1.贪心规则（Ma...
- Python三目运算基础与进阶_python三目运算符判断三个变量
-
#头条创作挑战赛#Python中你学会了三步运算，你将会省去很多无用的代码，我接下来由基础到进阶的方式讲解Python三目运算基础在Python中，三目运算符也称为条件表达式。它可以通过一行代码实现条...
- Python 中 必须掌握的 20 个核心函数——set()详解
-
set()是Python中用于创建集合的核心函数，集合是一种无序、不重复元素的容器，非常适合用于成员检测、去重和数学集合运算。一、set()的基本用法1.1创建空集合#创建空集合empty_se...
- 15个让Python编码效率翻倍的实用技巧
-
在软件开发领域，代码质量往往比代码数量更重要。本文整理的15个Python编码技巧，源自开发者在真实项目中验证过的工作方法，能够帮助您用更简洁的代码实现更清晰的逻辑。这些技巧覆盖基础语法优化到高级特性...
- 《Python从小白到入门》自学课程目录汇总(和猫妹学Python)
-
小朋友们好，大朋友们好！不知不觉，这套猫妹自学Python基础课程已经结束了，猫妹体会到了水滴石穿的力量。水一直向下滴，时间长了能把石头滴穿。只要坚持不懈，细微之力也能做出很难办的事。就比如咱们的学习...
- 8÷2(2+2) 等于1还是16?国外网友为这道小学数学题吵疯了……
-
近日，国外网友因为一道小学数学题在推特上争得热火朝天。事情的起因是一个推特网友@pjmdoll发布了一条推文，让他的关注者解答一道数学题：Viralmathequationshavebeen...
- Python学不会来打我(21)python表达式知识点汇总
-
在Python中，表达式是由变量、运算符、函数调用等组合而成的语句，用于产生值或执行特定操作。以下是对Python中常见表达式的详细讲解：1.1算术表达式涉及数学运算的表达式。例如：a=5b...
- Python运算符:数学助手，轻松拿咧
-
Python中的运算符就像是生活中的数学助手，帮助我们快速准确地完成这些计算。比如购物时计算总价、做家务时分配任务等。这篇文章就来详细聊聊Python中的各种运算符，并通过实际代码示例帮助你更好地理解...
- Python学不会来打我(17)逻辑运算符的使用方法与使用场景
-
在Python编程中，逻辑运算符（LogicalOperators）是用于组合多个条件表达式的关键工具。它们可以将多个布尔表达式连接起来，形成更复杂的判断逻辑，并返回一个布尔值（True或Fa...
- Python编程基础:运算符的优先级_python中的运算符优先级问题
-
多个运算符同时出现在一个表达式中时，先执行哪个，后执行哪个，这就涉及运算符的优先级。如数学表达式，有+、-、×、÷、()等，优先级顺序是()、×、÷、+、-，如5+(5-3)×4÷2，先计算(5-3)...
- Python运算符与表达式_python中运算符&的功能
-
一、运算符分类总览1.Python运算符全景图2.运算符优先级表表1.3.1Python运算符优先级（从高到低）优先级运算符描述结合性1**指数右→左2~+-位非/一元加减右→左3*//...
- Python操作Excel:从基础到高级的深度实践
-
Python凭借其丰富的库生态系统，已成为自动化处理Excel数据的强大工具。本文将深入探讨五个关键领域，通过实际代码示例展示如何利用Python进行高效的Excel操作，涵盖数据处理、格式控制、可视...
欢迎 你 发表评论:
- 一周热门
- 最近发表
-
- 使用 python-fire 快速构建 CLI_如何搭建python项目架构
- Python 闭包:从底层逻辑到实战避坑，附安全防护指南
- 使用Python实现九九乘法表的打印_用python打印一个九九乘法表
- 吊打面试官(四)--Java语法基础运算符一文全掌握
- Python三目运算基础与进阶_python三目运算符判断三个变量
- Python 中 必须掌握的 20 个核心函数——set()详解
- 15个让Python编码效率翻倍的实用技巧
- 《Python从小白到入门》自学课程目录汇总(和猫妹学Python)
- 8÷2(2+2) 等于1还是16?国外网友为这道小学数学题吵疯了……
- Python学不会来打我(21)python表达式知识点汇总
- 标签列表
-
- python计时 (73)
- python安装路径 (56)
- python类型转换 (93)
- python进度条 (67)
- python吧 (67)
- python的for循环 (65)
- python格式化字符串 (61)
- python静态方法 (57)
- python列表切片 (59)
- python面向对象编程 (60)
- python 代码加密 (65)
- python串口编程 (77)
- python封装 (57)
- python写入txt (66)
- python读取文件夹下所有文件 (59)
- python操作mysql数据库 (66)
- python获取列表的长度 (64)
- python接口 (63)
- python调用函数 (57)
- python多态 (60)
- python匿名函数 (59)
- python打印九九乘法表 (65)
- python赋值 (62)
- python异常 (69)
- python元祖 (57)