Python教程

算法之快速排序(python)

本文主要是介绍算法之快速排序(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)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!