python 中的随机快速排序,递归问题

Randomize quick sort in python, recursion issue

我正在实施随机快速排序。现在我已经创建了一个函数 ChoosePivot(A,N)。这 returns 一个随机枢轴及其在输入数组中的位置。然后我将随机枢轴与数组中的第一个元素切换,以便 Partition (A,l,r) 中的枢轴始终是第一个元素。现在 ChoosePivot(A,N) 也返回数组的第一个元素,但我打算稍后修改它。

以下是我的代码:

def QuickSort(A,N):
    if (N == 1):
        return
    pivot, pivot_pos = ChoosePivot(A,N)
    l = 0
    r = len(A)
    # Preprocessing, swapping pivot position with first element so that first element remains pivot always
    temp = A[0]
    A[0] = A[pivot_pos]
    A[pivot_pos] = temp

    A, i= Partition(A,l,r)
    print A,i
    # If i-1 == 0 this means that there is no left subarray
    if (i-1 != 0):
        print "Unsorted array"
        print A[0:i-1]
        QuickSort(A[0:i-1],i-1)
        print "Left call"
        print A

    if (N-i !=0): 
        print "Unsorted array"
        print A[i:N]
        QuickSort (A[i:N], N-i)
        print "Right call"
        print A

以下是我的Partition(A,l,r)

def Partition(A,l,r):
    # Now first element is the pivot
    i= l + 1
    pivot = A[l]
    for j in range(l+1, r):
        if (A[j] < pivot):
            #swap (A[j], A[i])
            temp_1 = A[i]
            A[i] = A[j]
            A[j] = temp_1
            i = i+1
    #swap (A[i-1], A[l])
    temp_2 = A[i-1]
    A[i-1] = A[l]
    A[l] = temp_2
    return A, i 

ChoosePivot(A,N) 只需 returns 数组中的第一个元素

def ChoosePivot(A, N):
    #print A
    return A[0], 0

我使用的输入数组如下:

Test_in = [3,8,2,5,1,4,7,6]
print Test_in

QuickSort(Test_in, len(Test_in))
print Test_in 

请注意,我可以看到代码在递归的低端工作。我用笔和纸干了 运行 代码,我可以通过打印语句看到它确实对子数组进行了排序,但是当最终返回数组时,它没有改变。我认为它与价值与引用调用有关,但我发现 python 通过引用调用。所以那里应该没有任何问题。 也发布输出并指出错误的确切位置。

我发现了这个错误。 问题是当我再次调用 QuickSort 时,我将原始列表切片并将其作为参数传递。当列表被切片时 python 创建一个新列表并将切片列表复制到同名的新列表中。所有更改都发生在递归深处的新列表中,因此它们不会反映回顶部。 作为解决方案,我传递了整个数组并将列表索引作为参数传递给数组。

还有一个bug。调用 QuickSort 之前的条件 i-1!=0N-i!=0 不正确,因为主元可以是数组中的任何索引。我为左右子数组创建了单独的左右索引并测试了 left_index < right_index.

谢谢