python实现快速排序
2021/6/5 20:51:06
本文主要是介绍python实现快速排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
# 快速排序 # 将元素放到自己应有的位置,左边的数都比它小,右边的数都比它大 # 递归完成 ''' 时间复杂度,O(n*log(n)) (一般情况) 快速排序的问题 最坏情况 排一个倒叙的列表 解决方法,在列表中随机找一个数与第一个数进行交换 递归 容易超过递归的最大深度 ''' import random # import sys # sys.setrecursionlimit(10000) 该表最大递归深度 ''' 快速排序 快速排序思路 取一个元素p(第一个元素),使元素p归位 列表被p分为两个部分,左变都比p小右边都比pda 递归完成排序 ''' def partition(li, left, right): # 将最左边的元素给tmp tmp = li[left] while left < right: while left < right and li[right]>=tmp: # 从右面找出比tmp小的数 right -= 1 li[left] = li[right] # 将右边第一个小于tmp的数放到左边的空位上 while left < right and li[left] <= tmp: # 从左边找出比tmp大的数 left += 1 li[right] = li[left] # 将左边第一个大于tmp的数放到右边刚才腾出来的空位上 li[left] = tmp # 将tmp归位,放到了左边全比它小,右面全比它大的位置,也就是它最后应在的位置 return left # 这个left代表的就是tmp位置的索引 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) li = list(range(10000)) random.shuffle(li) quick_sort(li, 0, len(li)-1) print(li)
这篇关于python实现快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08有遇到过吗?同样的规则 Excel 中 比Python 结果大
- 2024-03-30开始python成长之路
- 2024-03-29python optparse
- 2024-03-29python map 函数
- 2024-03-20invalid format specifier python
- 2024-03-18pool.map python
- 2024-03-18threads in python
- 2024-03-14python Ai 应用开发基础训练,字符串,字典,文件
- 2024-03-13id3 algorithm python
- 2024-03-13sum array elements python