快速排序：無限循環

Question

下實現QuickSort運行進入無限循環

def partition(arr, lo, hi): 
    pivot = lo 
    for i in range(lo+1, hi+1): 
     if arr[i] <= arr[lo]: 
      pivot += 1 
      arr[i], arr[pivot] = arr[pivot], arr[i] 
    arr[lo], arr[pivot] = arr[pivot], arr[lo] 
    return pivot 

def quickSort(arr, lo=0, hi=None): 
    if not hi: hi = len(arr) - 1 
    if lo >= hi: return 

    pivot = partition(arr, lo, hi) 
    quickSort(arr, lo, pivot-1) 
    quickSort(arr, pivot+1, hi) 


arr = [5,3,2,-9,1,6,0,-1,9,6,2,5] 
quickSort(arr) 
print(arr) 

我推測partition功能是罪魁禍首。無法弄清楚這個錯誤。

謝謝

Answer 1

問題是與你的初始化代碼爲hi：

if not hi: hi = len(arr) - 1 

條件not hi是True如果hi爲零。

這會導致quicksort(arr, 0, 0)和quicksort(arr, 1, 0)（其中一個幾乎總是會在排序過程中發生）嘗試重新排序大多數列表，而不是結束遞歸。

你應該使用更具體的測試if hi is None，而不是if not hi。這樣，如果它不爲零，則永遠不會不正確地重新初始化hi，並且僅當hi爲None時，初始化代碼纔會運行，因爲它沒有被用戶傳遞給該函數。

Answer 2

在某一點上，你的循環從不在分區def中工作。看下面

[5, 3, 2, -9, 1, 6, 0, -1, 9, 6, 2, 5] 
lo 0 hi 11 
pivot 8 
[5, 3, 2, -9, 1, 0, -1, 2, 5, 6, 6, 9] 
lo 0 hi 7 
pivot 7 
[2, 3, 2, -9, 1, 0, -1, 5, 5, 6, 6, 9] 
lo 0 hi 6 
pivot 5 
[-1, 2, -9, 1, 0, 2, 3, 5, 5, 6, 6, 9] 
lo 0 hi 4 
pivot 1 
[-9, -1, 2, 1, 0, 2, 3, 5, 5, 6, 6, 9] 
lo 0 hi 11 
pivot 0 
[-9, -1, 2, 1, 0, 2, 3, 5, 5, 6, 6, 9] 
lo 1 hi 11 

分區似乎並沒有做好整個工作，並且是正確的，這是一個兩步過程。請參閱下面的示例分區def。此外，您還可以參考原來的源here：

def partition(alist,first,last): 
    pivotvalue = alist[first] 

    leftmark = first+1 
    rightmark = last 

    done = False 
    while not done: 

     while leftmark <= rightmark and alist[leftmark] <= pivotvalue: 
      leftmark = leftmark + 1 

     while alist[rightmark] >= pivotvalue and rightmark >= leftmark: 
      rightmark = rightmark -1 

     if rightmark < leftmark: 
      done = True 
     else: 
      temp = alist[leftmark] 
      alist[leftmark] = alist[rightmark] 
      alist[rightmark] = temp 

    temp = alist[first] 
    alist[first] = alist[rightmark] 
    alist[rightmark] = temp 


    return rightmark