在python中将快速排序随机化，递归问题

Question

我正在实施随机快速排序。现在，我已经创建了一个函数ChoosePivot(A,N)。这将返回随机枢轴及其在输入数组中的位置。然后，我用数组中的第一个元素切换该随机枢轴，以便枢轴输入Partition (A,l,r)始终是第一个元素。For NowChoosePivot(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) 现在只需返回数组中的第一个元素

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是通过引用调用的。因此，那里应该没有任何问题。还要发布输出，并指出错误的确切位置。

Answer 1

我发现了错误。问题是当我QuickSort再次调用时，我将原始列表切成薄片并将其作为参数传递。切片列表时，python创建一个新列表，并将切片列表复制到具有相同名称的新列表中。所有更改都发生在递归内的新列表中，因此不会反映到顶部。作为解决方案，我传递了整个数组，并将列表索引作为参数传递给了数组。还有另一个错误。调用之前的状况QuickSort是i-1!=0和N-i!=0不正确的，因为支点可以在阵列中的任何指标。我为左右子数组创建了单独的左右索引并进行了测试left_index < right_index。