快速排序：无限循环

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

在某一时刻，您的循环在分区 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

分区似乎并没有正确地完成全部工作，它是一个两步过程。请参阅下面的示例分区定义。另外，您可以参考原始出处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

Answer 2

问题出在您 hi:

的初始化代码上

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

如果 hi 为零，则条件 not hi 为 True。

这导致quicksort(arr, 0, 0)和quicksort(arr, 1, 0)（其中一个几乎总是在排序过程中发生）尝试再次对列表的大部分进行排序，而不是结束递归.

您应该使用更具体的测试 if hi is None 而不是 if not hi。这样你就永远不会错误地重新初始化 hi 如果它是零，并且初始化代码只会运行如果 hi 是 None 因为它没有传递给函数用户。

快速排序：无限循环

Quicksort: Infinite Loop

python

sorting

quicksort

infinite-loop