在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_inQuickSort(Test_in, len(Test_in))print Test_in 请注意，我可以看到代码在递归的低端运行。我用笔和纸进行了空运行代码，通过打印语句可以看到它确实对子数组进行了排序，但是当数组最终返回时，它并没有改变。我认为它与值与引用调用有关，但是我发现python是通过引用调用的。因此，那里应该没有任何问题。还要发布输出，并指出错误的确切位置。

Answer 1

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

还有另一个错误。调用之前的状况QuickSort是i-1!=0和N-i!=0不正确的，因为支点可以在阵列中的任何指标。我为左右子数组创建了单独的左右索引并进行了测试left_index < right_index。