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]