随机quicks中的最大递归深度误差

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

快速排序算法的一个特点是它是一个就地排序算法，即它不需要额外的空间来排序给定的列表。您可以跟踪输入列表中的索引，并交换元素以就地进行排序。 下面是一个示例解决方案

import random
def partition(arr, start, end):
    pivot = arr[end]
    ix = start
    for i in range(start, end):
        if arr[i] <= pivot:
            arr[i], arr[ix] = arr[ix], arr[i]
            ix += 1
    arr[ix], arr[end] = arr[end], arr[ix]
    return ix

def quick_sort(arr, start, end):
    if start > end: return
    rand_num = random.randint(start, end)
    arr[rand_num], arr[end] = arr[end], arr[rand_num]
    ix = partition(arr, start, end)
    quick_sort(arr, start, ix-1)
    quick_sort(arr, ix+1, end)

arr = [2,4,7,8,9,1,3,5,6,12,32]
quick_sort(arr, 0, len(ans)-1)

output:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 32]

Answer 2

这实际上非常接近，但我建议自己测试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混淆）。这使得它很难阅读，而且不熟悉您的代码的人很难看到正在发生的事情。你知道吗