快速排序 - python
2021/7/29 22:36:00
本文主要是介绍快速排序 - python,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
快速排序
学习来源:b站 python分享站
快速排序:首先,让列表第一个元素归位。如图,一个列表,两个箭头分别表示left和right,
把5拿出来,right从右往左遍历把比5小的值移到左边,当right指向2时,2比5小,移到左边空位,然后left从左往右遍历,
left指向7时,7比5大,移到右边空位,right开始左移,
依次遍历,直到 left = right,即重合,
此时把5放到重合处,左边的数都比5小,右边的数都比5大。
5归位之后,列表同样分别对5的左右两部分进行归位,比如把2,1,4,3看作一个列表,同理把2进行归位处理,依次递归即可。
代码如下:
# 快速排序 def partition(li, left, right): tmp = li[left] while left < right: while left < right and li[right] >= tmp: # 从右面找比tmp小的数 right -= 1 # 往左走一步 li[left] = li[right] # 把右边的值写在左边空位上 # print(li) while left < right and li[left] <= tmp: # 从左面找比tmp大的数 left += 1 # 往右走一步 li[right] = li[left] # 把左边的值写在右边空位上 # print(li) li[left] = tmp return left def _quick_sort(li, left, right): if left < right: # 至少两个元素 mid = partition(li, left, right) _quick_sort(li, left, mid - 1) _quick_sort(li, mid + 1, right) # @cal_time def quick_sort(li): _quick_sort(li, 0, len(li) - 1) li = [4, 5, 2, 9, 3, 6, 7, 8] print(li) quick_sort(li, 0, len(li)-1) print(li)
注:考虑到加装饰器@cal_time在每次递归时都会打印运行时间的情况,给加了个马甲,只在最后一层才会调用到装饰器。
这篇关于快速排序 - python的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-24Python编程基础详解
- 2024-11-21Python编程基础教程
- 2024-11-20Python编程基础与实践
- 2024-11-20Python编程基础与高级应用
- 2024-11-19Python 基础编程教程
- 2024-11-19Python基础入门教程
- 2024-11-17在FastAPI项目中添加一个生产级别的数据库——本地环境搭建指南
- 2024-11-16`PyMuPDF4LLM`:提取PDF数据的神器
- 2024-11-16四种数据科学Web界面框架快速对比:Rio、Reflex、Streamlit和Plotly Dash
- 2024-11-14获取参数学习:Python编程入门教程