Python大输入下的快速排序;如何修复错误码:Process finished with exit code -107

Question

我用Python编写了一个递归快速排序算法，用于对10,000个int类型的列表进行排序。我正在测试最坏情况(枢轴总是低索引，并且列表已经排序，因此快速排序的一个递归调用总是空的，而另一个总是减少1)。我知道这意味着我必须使用

增加递归极限。sys.setrecursionlimit(10000)

现在我得到错误代码

进程结束，退出代码-1073741571 (0xC00000FD)

我在别处读到我应该使用

threading.stack_size()

但是，我不知道如何使用这个函数。我尝试传递不同的值，我要么得到的大小是无效的，或相同的错误代码。有人能帮我一下吗?

Answer 1

通过在较小的分区上递归，在较大的分区上循环，可以将堆栈空间限制为O(log(n))。最坏情况下的时间复杂度仍然是O(n^2)。

def qsort(a, lo, hi):
while(lo < hi):
p = a[(lo + hi) // 2]       # pivot, any a[] except a[hi]
i = lo - 1
j = hi + 1
while(1):                   # Hoare partition
while(1):               #  while(a[++i] < p)
i += 1
if(a[i] >= p):
break
while(1):               #  while(a[--j] < p)
j -= 1
if(a[j] <= p):
break
if(i >= j):             #  if indexes met or crossed, break
break
a[i],a[j] = a[j],a[i]   #  else swap elements and loop
if((j - lo) < (hi - j)):    # recurse on smaller partition
qsort(a, lo, j)         #  loop on larger partition
lo = j+1
else:
qsort(a, j+1, hi)
hi = j