算法之快速排序(python)
2021/12/21 12:49:41
本文主要是介绍算法之快速排序(python),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原理
归位
代码实现
def partition(li, left, right): # 将第一个数归位,即该数左边均小于它,右边均大于它 tmp = li[left] # 取出该值,当作该位置为空位 while left < right: # 左右交替查找直到重合,重合位置就是归位的位置 while left < right and li[right] >= tmp: # 从右往左查找直到出现小于该数的值 right -= 1 li[left] = li[right] #将小于该数的值填到左边空位,右边变成空位 while left < right and li[left] <= tmp: # 从左往右查找指导出现大于该数的值 left += 1 li[right] = li[left] # 将大于该数的值填到右边空位,左边变成空位 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) # 另一部分都是大于第一个数,再递归进行归位 li = [5,7,4,6,3,1,2,9,8] print(li) quick_sort(li,0,len(li)-1) print(li)
快排时间复杂度:O(nlogn)
快排最坏情况及解决办法
最快情况是:逆序列表,例如:[9,8,7,6,5,4,3,2,1]
解决办法:随机找列表中的一个数与第一个数交换位置,再进行归位。
快排最坏情况时间复杂度:O(n²)
这篇关于算法之快速排序(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