Python 快速排序调试

Question

我已经实现了这个快速排序，但我似乎有无法修复的错误，有人介意快速浏览一下吗？

我给出的示例的输出接近答案，但有些索引放错了地方。

---

def partition(array, pivot, start, end):
# move pivot to the end
temp = array[pivot]
array[pivot] = array[end]
array[end] = temp
i = start
j = end - 1 
while(i < j):
# check from left for element bigger than pivot
while(i < j and array[end] > array[i]):
i = i + 1
# check from right for element smaller than pivot
while(i < j and array[end] < array[j]):
j = j - 1
# if we find a pair of misplaced elements swap them
if(i < j):
temp = array[i]
array[i] = array[j]
array[j] = temp
# move pivot element to its position
temp = array[i]
array[i] = array[end]
array[end] = temp
# return pivot position
return i
def quicksort_helper(array, start, end):
if(start < end):
pivot = (start + end) / 2
r = partition(array, pivot, start, end)
quicksort_helper(array, start, r - 1)
quicksort_helper(array, r + 1, end)
def quicksort(array):
quicksort_helper(array, 0, len(array) - 1)
array = [6, 0, 5, 1, 3, 4, -1, 10, 2, 7, 8, 9]
quicksort(array)
print array

---

我有一种感觉，答案是显而易见的，但我找不到它。

期望输出：

[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

实际输出：

[-1, 0, 2, 3, 1, 4, 5, 6, 7, 8, 9, 10]

Answer 1

关键修复是在内部while循环中，在那里你向对方行进i和j。 如果您只担心交换正确的非透视元素，那么您发布的逻辑很好。 但是，第一个循环需要

while(i <= j and array[end] > array[i]):
i = i + 1

以确保我有正确的值来交换枢轴元素到中间。 否则，您可以将其交换到其正确位置的左侧的一个元素，这就是排序失败的原因。

您还可以使用 Python 的多重赋值进行更干净的交换：

while(i < j):
# check from left for element bigger than pivot
while(i <= j and array[end] > array[i]):
i = i + 1
# check from right for element smaller than pivot
while(i < j and array[end] < array[j]):
j = j - 1
# if we find a pair of misplaced elements swap them
if(i < j):
array[i], array[j] = array[j], array[i]