def quick_sort(array):
if len(array) <=1:
return array
pivot = array[-1]
array.pop()
less = []
greater = []
for num in array:
if num > pivot:
greater.append(num)
else:
less.append(num)
return quick_sort(less) + [pivot] + quick_sort(greater)
这种快速排序实现的空间复杂度是多少？我只是选择最后一个元素作为枢轴，创建了一个元素更大和更小的元素数组，并相应地移动它们。然后，我递归地对较小和较大的数组执行此操作。所以最后，我会有 [枢轴] + [枢轴] + [枢轴]...全部按排序顺序排列。现在我对空间的复杂性有点困惑。我有两个子数组用于较小和较大的数组，还有递归调用堆栈。你觉得怎么样？
在最坏的情况下，实现快速排序的空间复杂度为 Θ(n2(，平均为 Θ(n(。
下面介绍了如何看待这一点。想象一下，为您的算法绘制完整的递归树。在任何一个时间点，算法都在其中一个递归调用中，需要空间来存储来自该递归调用的所有数据，以及它上面的递归调用的所有空间。这是因为在任何一个时间点，调用堆栈都是从某个回调到根调用的路径。因此，空间复杂度是从递归树中的叶子返回到根的任何路径上使用的最大空间量。
想象一下，你碰巧在每一步都选择了绝对最差的枢轴——比如说，你总是选择最小或最大的元素。然后你的递归树本质上是一个巨大的链表，其中根保存一个长度为 n 的数组，下面是一个长度为 n-1 的数组，下面是一个长度为 n-2 的数组，依此类推，直到你下降到一个长度为 1 的数组。空间使用量为 1+2+3+...+n，即 Θ(n2(。那不是很好。
另一方面，假设您正在查看一个更"典型"的快速排序运行，其中您通常会获得良好的枢轴。在这种情况下，您会期望，大约一半的时间，您会在阵列的中间 50% 处获得一个枢轴。通过一些数学计算，您可以证明这意味着，根据预期，在数组大小下降到其先前大小的 75% 之前，您将有大约两次拆分。这使得递归树的深度为O(log n(。然后，您将有大约两层，数组大小约为 n，大约两层数组大小约为 .75n，大约两层大小约为 (.75(2n，依此类推。这使您的空间使用率大致高
2(n + .75n + (.75(2n + ...(
= 2n(1 + .75 +(.75(2+ ...(
= θ(n(。
最后一步是因为它是一个几何级数的总和，它收敛到某个常数。
为了提高空间利用率，您需要避免在每个级别为较小和较大的元素创建新数组。请考虑使用就地分区算法就地修改数组。如果你很聪明，你可以使用这种方法，最终得到O(log n(总空间使用量。
希望这有帮助！