我正在阅读“Cracking the Coding Interview”一书，遇到了一个问题“编写一个程序以按升序对堆栈进行排序。您可以使用额外的堆栈来保存项目，但您不能将元素复制到任何其他数据结构中（如数组）。栈支持以下操作：push、pop、peek、isEmpty。
这本书给出了 O(n^2) 时间复杂度和 O(n) 空间的答案。
但是，我遇到了这个博客，它使用快速排序方法提供了 O(n log n) 时间复杂度的答案。
我想知道的是空间复杂度 O(n^2) 吗？由于对该方法的每次调用都涉及初始化另外两个堆栈，以及另外两个递归调用。
我对空间复杂性仍然有点动摇。我不确定这是否是 O(n^2) 空间，每个递归调用产生的新堆栈小于上一级的堆栈。
如果有人可以在他们的答案背后给出一点解释，那就太好了。
在平均情况下，空间复杂度也是 O(n log n)。如果空间复杂度恰好是 O(n^2)，那么时间复杂度怎么可能是 O(n log n)，因为分配的每个空间都需要至少一次访问。
因此，在平均情况下，假设每次将堆栈分成两半，在第 i个递归深度，数组的大小变为 O(n/2 ^ i)，在第 i个深度有 2 ^ i 个递归分支。所以在第 i个深度
上分配的总大小是O(n/2^i) *2 ^ i = O(n)。
由于最大深度为 log n，因此整体空间复杂度为 O(n log n)。
然而，在最坏的情况下，空间复杂度为 O(n^2)。
在这种快速排序方法中，空间复杂度将完全遵循时间复杂度——原因很简单。您正在递归地划分子堆栈（使用枢轴），直到每个元素都位于大小为 1 的堆栈中。这导致 x 子堆栈（log n 深度）的 (2^x = n) 划分，最后你有 n 个堆栈，每个堆栈大小为 1。因此，总空间复杂度将为 O(n*log n)。
请记住，在这种情况下，空间复杂度将完全遵循时间复杂度，就像我们在每次迭代中实际占用新空间一样。因此，在最坏的情况下，空间复杂度将为 O(n^2)。