Quicksort in place Python

Question

我對Python非常陌生，我正在嘗試使用算法。我只是在使用快速排序算法對數組進行排序時嘗試了我的雙手。

以下是我的代碼。當我運行這個有一個無限循環作爲輸出。任何人都可以通過代碼，讓我知道我的錯在哪裏邏輯：

def quicksort(arr,start,end): 
    if start < end: 
     pivot = arr[int(start + (end - start)/2)] 
     while end > start: 
      while arr[start] < pivot: 
       start = start + 1 
      while arr[end] > pivot: 
       end = end - 1 
      if start <= end: 
       arr[start],arr[end] = arr[end],arr[start] 
       start = start + 1 
       end = end - 1 


     quicksort(arr,0,end) 
     quicksort(arr,start,len(arr) - 1) 
    else:  
     return 



arr = list(map(int,input().split(" "))) 
quicksort(arr,0,len(arr) - 1) 

print ("The final sorted array:",arr) 

感謝您的任何幫助提前。

Answer 1

您的遞歸是錯誤的。做霍爾分區後，你應該做的：

• 調用快速排序從開始（的數據進行排序）從端運行指標，並從最終
• 調用快速排序（數據的被排序），以從一開始就運行的索引

因此，您必須在參數旁邊創建新變量以維護在分區中相互移動的開始，結束和索引。

爲了在不改變很多你的代碼，我建議你改變參數

def quicksort(arr,left,right): 
    start = left 
    end = right 

，並在遞歸

quicksort(arr,left,end) 
quicksort(arr,start,right)