Roa*_*oam 6 sorting algorithm complexity-theory quicksort data-structures
的空间复杂度Quicksort为。 O(logn)
然而 -Quicksort可以在不使用任何额外内存的情况下进行处理：在每次迭代时，在分区过程中，条目最终会根据所使用的主元交换到左分区和右分区中。这种递归交换并由此形成分区可以在列表本身上完成，而不会在一级递归调用中存在分区干扰，并且不会在不同级别的调用中进行快速排序干扰。
额外的内存有什么用Quicksort？
TIA。
//============================
编辑：
同意评论/答案中的堆栈空间——错过了这一点。
仍然，
O(nlogn)快速排序在预期情况下及时执行——通过在每个递归级别形成（几乎）相同大小的分区。
使用的堆栈空间是二叉树，在最佳情况下是完整的树，高度为log n。该树上的每个节点都是递归调用，本例中的堆栈空间约为n-- not log n。有O(n)这棵树上对左右分区的递归调用是同时进行的——调用树在某个执行点已满。
所以-平均情况空间复杂度应该是O(n)--不是O(logn)（？）
它也与归并排序的空间复杂度相矛盾。合并排序空间复杂度被列出为O(n)并且处理类似。
小智 2
快速排序通常使用 O(log n) 额外内存，存储在堆栈中。这不是 O(n)，因为二叉树在内存中从来不是显式的，我们只是对其进行后序遍历（即：在给定时间只存储树中的一条路径）。
归并排序被列为 O(n)，因为我们通常将合并的结果复制到新数组中。根据维基百科，就地排序是可能的，但时间复杂度增加到 O(n log 2 n)。它仍然会使用 O(log n) 进行递归。