欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

快速排序的python实现

程序员文章站 2022-07-02 22:56:26
快速排序的python实现快速排序的时间复杂度为O(n log(n)),可以用这种办法来记忆算法:将当前排列的数字中选出一个数字(例如第一个)为基准flag, 剩下的数字分为两组, 比flag大的, 比flag小的(这部分时间复杂度为O(n)). 再对剩下的部分执行同样操作(这部分时间复杂度为O(n log(n)))[因为采用了二分法]需要注意的是何时可以结束递归: 排列的长度为0, 1时都可以, 这里要仔细分析代码实现def qsort (L): if len(L):...

快速排序的python实现

快速排序的时间复杂度为O(n log(n)),可以用这种办法来记忆算法:
将当前排列的数字中选出一个数字(例如第一个)为基准flag, 剩下的数字分为两组, 比flag大的, 比flag小的(这部分时间复杂度为O(n)). 再对剩下的部分执行同样操作(这部分时间复杂度为O(n log(n)))[因为采用了二分法]

需要注意的是何时可以结束递归: 排列的长度为0, 1时都可以, 这里要仔细分析

代码实现

def qsort (L):
    if len(L):
        l_min = [x for x in L[1:] if x < L[0]]
        l_max = [x for x in L[1:] if x >= L[0]]
        return qsort(l_min) + [L[0]] + qsort(l_max)
    else:
        return []

本文地址:https://blog.csdn.net/albert_fifth/article/details/110455611