algorithm - 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

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

您还可以使用 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]