在终端上运行的Python快速排序递归错误

Question

有人会知道为什么我在quicksort上遇到以下递归错误吗？不知道为什么会收到“ RecursionError：比较中超出最大递归深度”的信息。我问过其他人，他们说我的递归不应超过：

这里是代码：

def Quicksort1(array, index, low, high):

    if high > low:
        Partition(array, low, high, index)
        Quicksort1(array, index, low, index + 1)
        Quicksort1(array, index, index + 1, high)


def Partition(array, index, low, high):

    firstitem = array[low]
    j = low

    for i in range(low+1, high):

        if array[i] < firstitem:
            j+=1
            array[j], array[i] = array[i], array[j]

    index = j
    array[low], array[index] = array[index], array[low]     



array = [10, 3, 4, 8, 1, 7]
Quicksort1(array, 0, 0, len(array)-1)
for j in range(n): 
    print ("%d" %arr[j])

和错误

(base) b98-aruba1-guest-10-110-7-206:desktop ericadamian$ python Quicksort1.py
Traceback (most recent call last):
  File "Quicksort1.py", line 26, in <module>
    Quicksort1(array, 0, 0, len(array)-1)
  File "Quicksort1.py", line 5, in Quicksort1
    Quicksort1(array, index, low, index + 1)
  File "Quicksort1.py", line 5, in Quicksort1
    Quicksort1(array, index, low, index + 1)
  File "Quicksort1.py", line 5, in Quicksort1
    Quicksort1(array, index, low, index + 1)
  [Previous line repeated 993 more times]
  File "Quicksort1.py", line 4, in Quicksort1
    Partition(array, low, high, index)
  File "Quicksort1.py", line 14, in Partition
    for i in range(low+1, high):
RecursionError: maximum recursion depth exceeded in comparison
(base) b98-aruba1-guest-10-110-7-206:desktop ericadamian$

Answer 1

注释中指出的问题。

def Quicksort1(array, low, high):               #fix

    if high > low:
        index = Partition(array, low, high)     #fix
        Quicksort1(array, low, index - 1)       #fix
        Quicksort1(array, index + 1, high)      #fix

def Partition(array, low, high):                #fix

    firstitem = array[low]
    j = low
    for i in range(low+1, high+1):              #fix
        if array[i] < firstitem:
            j+=1
            array[j], array[i] = array[i], array[j]
    index = j
    array[low], array[index] = array[index], array[low]     
    return index                                #fix

array = [10, 3, 4, 8, 1, 7]
Quicksort1(array, 0, len(array)-1)              #fix
for j in range(len(array)):                     #fix
    print ("%d" %array[j])                      #fix