Python爲什麼這個quicksort沒有正確排序？

Question

我一直試圖在過去的三週裏使用python來實現quicksort函數，但是我總是得到這一點，並且它主要是排序的，但是有一些項目不合適。

我不認爲我的理解正確快速排序，所以如果你能看到從我的代碼爲什麼請解釋。

我所選擇的樞軸是在列表中的第一個目的，「低」，然後將其進行比較，以列表的其餘部分。如果列表索引「low」處的對象大於列表索引「i」（在我的for循環中），那麼我將「i」替換爲「E」（最初索引爲「low + 1」項）開關，「E」遞增。即使它不切換，「我」也會增加（因爲for循環）。

一旦我的循環結束後，我遞減「E」（索引它在列表中比我的支點低次數最多的），然後用「低」（支點指數）

我那麼快速排序其切換列表的左右兩半使用「E」來確定列表分割的位置。 - 這似乎是代碼無法排序的地方。

我相信這是快速排序是如何工作的，但我一直無法使它發揮作用。如果你知道我錯過了什麼，或者如果它只是我的一行，請告訴我。任何有關這個問題的幫助將不勝感激。

（PS。「主」功能只是路過20長度0-19值的變量列表到我的快速排序和Python的內置的排序）

import random 


def quick(A, low, high): 
    if high <= low: 
     return 
    elif high > low: 
     E = low+1 
     for i in range(E, high): 
      if A[low] > A[i]: 
       A[i], A[E] = A[E], A[i] 
       E +=1 
     E -= 1 
     A[low], A[E] = A[E], A[low] 
     quick(A, low, E-1) 
     quick(A, E+1, high) 


def main(): 
    listA = [] 
    listB = [] 
    for i in range(20): 
     int = random.randrange(0, 19) 
     listA.append(int) 
    for i in range(len(listA)): 
     listB.append(listA[i]) 
    print("List A (before sort)" + str(listA)) 
    print("List B (before sort)" + str(listB)) 
    quick(listA, 0, len(listA)-1) 
    print("\nList A (after sort)" + str(listA)) 
    print("List B (before sort)" + str(listB)) 
    listB.sort() 
    print("\nList A (after sort)" + str(listA)) 
    print("List B (after sort)" + str(listB)) 


main() 

Answer 1

你的問題是你每次拆分都忽略一個數字。 range(min, max)給出了包括min但不max，結束而上max-1

quick(listA, 0, len(listA)-1)

應該

quick(listA, 0, len(listA))，列表

和

quick(A, low, E-1)

應是

quick(A, low, E)。