快速排序：无限循环

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