我正在练习使用递归来实现快速排序算法。我得到了错误：
RecursionError：相比之下超过了最大递归深度
这是错误：
In [2]: run quicksort.py
---------------------------------------------------------------------------
RecursionError Traceback (most recent call last)
~/Desktop/algo/quicksort.py in <module>()
27
28 test = QuickSort()
---> 29 print(test.partition([7, 2, 1, 8, 6, 3, 5, 4], 0, 7))
~/Desktop/algo/quicksort.py in partition(array, start, end)
20 def partition(array, start, end):
21 if start < end: # this is enough to end recursion
---> 22 pos = QuickSort.partition(array, start, end)
23 QuickSort.quickSort(array, start, pos - 1)
24 QuickSort.quickSort(array, pos + 1, end)
... last 1 frames repeated, from the frame below ...
~/Desktop/algo/quicksort.py in partition(array, start, end)
20 def partition(array, start, end):
21 if start < end: # this is enough to end recursion
---> 22 pos = QuickSort.partition(array, start, end)
23 QuickSort.quickSort(array, start, pos - 1)
24 QuickSort.quickSort(array, pos + 1, end)
RecursionError: maximum recursion depth exceeded in comparison
这是我当前的代码（我使用一个类，这样其他人就可以知道我正在实现什么算法）：
class QuickSort:
def __init__(self):
self.name = "Quick Sort"
@staticmethod
def quickSort(arr, start, end):
pivot = arr[end]
i = start-1
for x in range(start, end):
if arr[x] > pivot:
continue
else:
i += 1
arr[i],arr[x] = arr[x],arr[i]
for y in range(end, i + 1, -1):
arr[y] = arr[y-1]
arr[i + 1] = pivot
return arr.index(pivot)
@staticmethod
def partition(array, start, end):
if start < end: # this is enough to end recursion
pos = QuickSort.partition(array, start, end)
QuickSort.quickSort(array, start, pos - 1)
QuickSort.quickSort(array, pos + 1, end)
test = QuickSort()
print(test.partition([7, 2, 1, 8, 6, 3, 5, 4], 0, 7))
所以这里“快速排序”基本上执行第一个操作。之后，“分区”将使用递归来解决问题。
快速排序应该调用分区（而不是分区调用快速排序）。示例单函数代码，分区代码包含在快速排序函数中。此示例还将堆栈空间限制为O（log（n）），仅对较小的部分使用递归，对较大的部分使用迭代（循环）。最坏的情况时间复杂度仍然是O（n^2）。
class QuickSort:
def __init__(self):
self.name = "Quick Sort"
@staticmethod
def quickSort(a, lo, hi):
while(lo < hi):
pivot = a[hi] # Lomuto partition
i = lo
for j in range(lo, hi):
if a[j] < pivot:
a[i],a[j] = a[j],a[i]
i += 1
a[i],a[hi] = a[hi],a[i] # swap pivot to a[i]
# recurse on smaller part, iterate on larger part
if(i - lo <= hi - i):
QuickSort.quickSort(a, lo, i-1)
lo = i+1
else:
QuickSort.quickSort(a, i+1, hi)
hi = i-1
test = QuickSort()
a = [7, 2, 1, 8, 6, 3, 5, 4]
test.quickSort(a, 0, len(a)-1)
print(a)
