Quicksort 的空间复杂度是listed as O(登录)。
但是 - Quicksort 可以在不使用任何额外内存的情况下进行处理:
在每次迭代中，在分区过程中，
这些条目最终被交换到
基于所使用的枢轴的左右分区。
这种递归交换并因此形成分区
可以在列表本身上完成而无需
在递归调用干扰的一级分区
并且不会在不同级别的调用干扰中进行快速排序。
Quicksort 中的额外内存有什么用？
TIA。
//============================
编辑:
同意评论/答案中的堆栈空间——错过了。
还是，
在 预期情况 中，Quicksort 的执行时间为 O(nlogn) --
通过在每个递归级别形成(几乎)大小相等的分区。
使用的堆栈空间是二叉树，在最佳情况下是满树，高度为 log n。
这棵树上的每个节点都是一个递归调用，堆栈空间
在这种情况下是 n 的顺序——而不是 log n。这棵树上有 O(n) 个节点。向左和向右的递归调用
分区是同时进行的——调用树在某个执行点已满。
所以 - 平均情况空间复杂度应该是 O(n)-- 而不是 O(logn) (?)
这也与归并排序的空间复杂度矛盾。
合并排序空间复杂度列为 O(n) 并且处理类似。
最佳答案
Quicksort 通常使用 O(log n) 额外内存，存储在堆栈上。它不是 O(n)，因为二叉树在内存中永远不会显式，我们只是对其进行后序遍历(即:树中只有一个路径曾经存储在给定的位置时间)。
Mergesort 被列为 O(n) 因为我们通常将合并的结果复制到一个新数组中。根据维基百科，就地排序是可能的，但将时间复杂度增加到 O(n log2 n)。它仍然会使用 O(log n) 进行递归。
关于algorithm - 快速排序的内存复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29738135/