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

Question

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

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)

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

Answer 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混淆)。这让不熟悉您的代码的人难以阅读和了解正在发生的事情。