我写了一个递归随机快速排序函数如下：
def randomized_quick_sort(a, l, r):
if l >= r:
return
k = random.randint(l, r)
a[l], a[k] = a[k], a[l]
m1, m2 = partition3(a, l, r)
randomized_quick_sort(a,l,m1-1)
randomized_quick_sort(a,m2+1,r)
下面给出了使用的分区函数，它将列表划分为三个部分，小于pivot、等于pivot和大于pivot，其中pivot是输入列表中的第一个元素。
def partition3(a, l, r):
x = a[l]
less, equal, greater = [], [], []
for val in a[l:r+1]:
if val < x:
less.append(val)
if val == x:
equal.append(val)
if val > x:
greater.append(val)
a[l:r+1] = less + equal + greater
m1 = len(less)
m2 = m1 + len(equal) - 1
return m1, m2
如果我在一个简单的输入上多次运行这个快速排序函数，例如
a = [2,2,3,3]
randomized_quick_sort(a,0,len(a)-1)
经过几次试验，我得到了一个“超过最大递归深度”的错误。请帮忙！
这实际上非常接近，但我建议自行测试def分区3（a， l，r）。您会发现它返回的值实际上没有意义。
但是，只要稍作改动，我们就可以让它工作：
m1 = len(less)
应该是：
m1 = len(less) + l # l for left, not 1 for one
您不希望m1只是less中项目的长度，因为如果您一直在比较第9个和第11个项目，那么当您打算返回10时，您将返回1。
另外，一般来说，尽量避免使用单字母变量名（尤其是l很容易混淆为1）。这使得不熟悉您的代码的人很难阅读并且很难看到发生了什么。
快速排序算法的特性之一是它是一种就地排序算法，即它不需要额外的空间来对给定列表进行排序。您可以跟踪输入列表中的索引并交换元素以进行就地排序。这是一个示例解决方案
import random
def partition(arr, start, end):
pivot = arr[end]
ix = start
for i in range(start, end):
if arr[i] <= pivot:
arr[i], arr[ix] = arr[ix], arr[i]
ix += 1
arr[ix], arr[end] = arr[end], arr[ix]
return ix
def quick_sort(arr, start, end):
if start > end: return
rand_num = random.randint(start, end)
arr[rand_num], arr[end] = arr[end], arr[rand_num]
ix = partition(arr, start, end)
quick_sort(arr, start, ix-1)
quick_sort(arr, ix+1, end)
arr = [2,4,7,8,9,1,3,5,6,12,32]
quick_sort(arr, 0, len(ans)-1)
output:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 32]
