快速排序实现，数组不排序

Question

##我在python中实现了quicksort，但我的数组在结果上没有改变，我不知道算法是错误的还是我返回数组的方式不正确。请帮助##

def partition(array, left, right):
x = array[right]
left_pointer = left
for right_pointer in range(left, right):
if array[right_pointer] <= x:
swap(array[right_pointer], array[left_pointer])
left_pointer += 1
swap(array[left_pointer], array[right])
return left_pointer

def swap(x, y):
x, y = y, x
return x, y

def quicksort(arr, left, right):
# print(left, right)
if left < right:
pivot = partition(arr, left, right)
quicksort(arr, left, pivot - 1)
quicksort(arr, pivot + 1, right)
return array

array = [2, 6, 5, 3, 8, 7, 1, 0]
n = len(array) - 1
print(array)
print(quicksort(array, 0, n))

Answer 1

错误在swap函数中。您正在传递值，这些值被交换，然后被丢弃。

重写如下：

def swap(a, l, r):
a[l], a[r] = a[r], a[l]
swap(array, right_pointer, left_pointer)
swap(array, left_pointer, right)

Answer 2

无需使用交换函数，在您的分区函数中使用此代码来交换数据
下面，i=您的第一个指针，j="for loop"的变量

# swapping element at left with element at right
(array[i], array[j]) = (array[j], array[i])

# swap the pivot element with the greater element specified by i
(array[i + 1], array[right]) = (array[right], array[i + 1])

当您在分区函数中使用此代码时，无需在quicksort函数中比较数据。在快速排序功能中，设置枢轴元素。

Answer 3

非常感谢您的解决方案。我意识到我没有在数组上调用quicksort函数，于是我去掉了swap函数。代码现在运行良好

def partition(array, left, right):
x = array[right]
left_pointer = left
for right_pointer in range(left, right):
if array[right_pointer] <= x:
array[right_pointer], array[left_pointer] = array[left_pointer], array[right_pointer]
left_pointer += 1
array[left_pointer], array[right] = array[right], array[left_pointer]
return left_pointer

def quicksort(arr, left, right):
# print(left, right)
if left < right:
pivot = partition(arr, left, right)
quicksort(arr, left, pivot - 1)
quicksort(arr, pivot + 1, right)
return arr

array = [2, 6, 5, 4, 3, 8, 7, 1, 0]
print(quicksort(array, 0, len(array)-1))