python排序方法简单(快速排序的四种python实现推荐)
python排序方法简单
快速排序的四种python实现推荐快速排序算法,简称快排,是最实用的排序算法,没有之一,各大语言标准库的排序函数也基本都是基于快排实现的。
本文用python语言介绍四种不同的快排实现。
1. 一行代码实现的简洁版本
|
quick_sort = lambda array: array if len (array) < = 1 else quick_sort([item for item in array[ 1 :] if item < = array[ 0 ]]) + [array[ 0 ]] + quick_sort([item for item in array[ 1 :] if item > array[ 0 ]]) |
2. 网上常见的快排实现
|
def quick_sort(array, left, right): if left > = right: return low = left high = right key = array[low] while left < right: while left < right and array[right] > key: right - = 1 array[left] = array[right] while left < right and array[left] < = key: left + = 1 array[right] = array[left] array[right] = key quick_sort(array, low, left - 1 ) quick_sort(array, left + 1 , high) |
由于快排是原地排序,因此不需要返回array。
array如果是个列表的话,可以通过len(array)求得长度,但是后边递归调用的时候必须使用分片,而分片执行的原列表的复制操作,这样就达不到原地排序的目的了,所以还是要传上边界和下边界的。
3.《算法导论》中的快排程序
|
def quick_sort(array, l, r): if l < r: q = partition(array, l, r) quick_sort(array, l, q - 1 ) quick_sort(array, q + 1 , r) def partition(array, l, r): x = array[r] i = l - 1 for j in range (l, r): if array[j] < = x: i + = 1 array[i], array[j] = array[j], array[i] array[i + 1 ], array[r] = array[r], array[i + 1 ] return i + 1 |
这个版本跟上个版本的不同在于分片过程不同,只用了一层循环,并且一趟就完成分片,相比之下代码要简洁的多了。
4. 用栈实现非递归的快排程序
先说两句题外话,一般意义上的栈有两层含义,一层是后进先出的数据结构栈,一层是指函数的内存栈,归根结底,函数的内存栈的结构就是一个后进先出的栈。汇编代码中,调用一个函数的时候,修改的也是堆栈指针寄存器ESP,该寄存器保存的是函数局部栈的栈顶,另外一个寄存器EBP保存的是栈底。不知道与栈存储空间相对的堆存储空间,其组织结构是否也是一个完全二叉树呢?
高级语言将递归转换为迭代,用的也是栈,需要考虑两个问题:
1)栈里边保存什么?
2)迭代结束的条件是什么?
栈里边保存的当然是需要迭代的函数参数,结束条件也是跟需要迭代的参数有关。对于快速排序来说,迭代的参数是数组的上边界low和下边界high,迭代结束的条件是low == high。
|
def quick_sort(array, l, r): if l > = r: return stack = [] stack.append(l) stack.append(r) while stack: low = stack.pop( 0 ) high = stack.pop( 0 ) if high - low < = 0 : continue x = array[high] i = low - 1 for j in range (low, high): if array[j] < = x: i + = 1 array[i], array[j] = array[j], array[i] array[i + 1 ], array[high] = array[high], array[i + 1 ] stack.extend([low, i, i + 2 , high]) |
另外,当数组下标为-1时,C++、Java等语言中会报错,但python中访问的是最后一个元素,所以如果程序写错了,可能其他语言会报错,但python会输出一个错误的结果。
以上所述是小编给大家介绍的python实现快速排序算法详解整合,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对开心学习网网站的支持!
原文链接:https://blog.csdn.net/razor87/article/details/71155518
- 在python中导入模块有哪几种方式(Python不同目录间进行模块调用的实现方法)
- python3.9.6生成的注册表(厉害了,Python也能操作注册表)
- ipython命令行查看文件夹(对IPython交互模式下的退出方法详解)
- python快速数据分类(Python基于滑动平均思想实现缺失数据填充的方法)
- python处理时间序列常用方法汇总(python整小时 整天时间戳获取算法示例)
- python同步钉钉用户(python 调用钉钉机器人的方法)
- python函数参数讲解(Python高级特性与几种函数的讲解)
- pythonselenium自动化使用教程(selenium python 实现基本自动化测试的示例代码)
- python爬虫怎么设置代理ip(python爬虫简单的添加代理进行访问的实现代码)
- python中jieba库怎么用(详解Python数据可视化编程 - 词云生成并保存jieba+WordCloud)
- python处理各种xml文件(Python使用sax模块解析XML文件示例)
- python 文件操作(Python File文件 方法整理)
- pythonftp功能介绍(使用Python操作FTP实现上传和下载的方法)
- python实用教程(Python简直是万能的,这5大主要用途你一定要知道!推荐)
- python分割字符串要用哪一个语句(python使用threading.Condition交替打印两个字符)
- python实时输出图像(Python给图像添加噪声具体操作)
- 黄渤泪目 我的痴呆父亲,我内心永远的痛(黄渤泪目我的痴呆父亲)
- 蒜苔和鱿鱼尾巴一起炒,味道特别棒,又脆又嫩,有滋又有味(蒜苔和鱿鱼尾巴一起炒)
- 鱿鱼炒蒜苔不是黑暗料理,这样做清香扑鼻,鲜美脆嫩,开胃又下饭(鱿鱼炒蒜苔不是黑暗料理)
- 蒜苔炒鱿鱼(蒜苔炒鱿鱼)
- 远离 五毛食品 洛阳80后妈妈发明的 飞行棋 成校园爆款 玩具(远离五毛食品)
- 失传的古代飞行棋游戏 六博(失传的古代飞行棋游戏)
热门推荐
- python 基于内容的推荐系统(不到40行代码用Python实现一个简单的推荐系统)
- console.table调试JSON对象或字符串
- css3旋转动画教学(css3动画效果抖动解决方法)
- plsql提示developer(PL/SQL Developer过期的两种解决方法)
- 织梦二次安装教程(重新安装织梦系统以及转移空间、上传空间的方法)
- js弹出新窗口被拦截的解决方法
- mysql中基本语句(MySQL中explain语句的基本使用教程)
- pythonselenium自动化教程(python使用selenium实现批量文件下载)
- 如何查看linq生成的sql
- 用python3.5.3实现邮件收发(Python使用POP3和SMTP协议收发邮件的示例代码)
排行榜
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9