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!=0
和 N-i!=0
不正确,因为主元可以是数组中的任何索引。我为左右子数组创建了单独的左右索引并测试了 left_index < right_index
.
谢谢
我正在实施随机快速排序。现在我已经创建了一个函数 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!=0
和 N-i!=0
不正确,因为主元可以是数组中的任何索引。我为左右子数组创建了单独的左右索引并测试了 left_index < right_index
.
谢谢