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循环，在这里行军我和Ĵ朝向彼此。如果所有你担心的是交换正确的非主元素，那么你发布的逻辑是好的。然而，第一环路需要是

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]