Skip to main content
 首页 » 编程设计

python之随机快速排序中的最大递归深度误差

2024年12月31日11xing901022

我写了一个递归随机快速排序函数如下:

def randomized_quick_sort(a, l, r): 
    if l >= r: 
        return 
    k = random.randint(l, r) 
 
    a[l], a[k] = a[k], a[l] 
 
    m1, m2 = partition3(a, l, r) 
    randomized_quick_sort(a,l,m1-1) 
    randomized_quick_sort(a,m2+1,r) 

下面给出了使用的分区函数,它将列表分为三个部分,小于 pivot、等于 pivot 和大于 pivot,其中 pivot 是输入列表中的第一个元素。

def partition3(a, l, r): 
    x = a[l] 
    less, equal, greater = [], [], [] 
    for val in a[l:r+1]: 
        if val < x:  
            less.append(val) 
        if val == x:  
            equal.append(val) 
        if val > x:  
            greater.append(val) 
 
    a[l:r+1] = less + equal + greater 
    m1 = len(less) 
    m2 = m1 + len(equal) - 1 
    return m1, m2 

如果我在一个简单的输入上多次运行这个快速排序函数,例如

a = [2,2,3,3] 
randomized_quick_sort(a,0,len(a)-1) 

仅经过几次试验后,我收到“超出最大递归深度”错误。请帮忙!

请您参考如下方法:

这实际上非常接近,但我建议单独测试 def partition3(a, l, r)。您会发现它返回的值实际上没有意义。

然而,通过一个小改动,我们可以让它工作:

m1 = len(less) 

应该是:

m1 = len(less) + l # l for left, not 1 for one 

您不希望 m1 只是 less 中项目的长度,因为如果您一直在比较第 9 项和第 11 项,那么当您打算返回 10 时,您会返回 1。

另外,一般情况下,尽量避免使用单字母变量名(尤其是l,容易与1混淆)。这让不熟悉您的代码的人难以阅读和了解正在发生的事情。