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


扫一扫关注最新编程教程