命令式快速排序是否在原地(就地)？

Question

Quicksort通常被描述为原位(就地)算法，尽管它需要O(log )堆栈空间。那么，原位表示“所需的额外空间小于O(n)”，还是堆栈空间一般不算空间复杂性(但为什么会这样？)，还是快速排序实际上不是一种原位算法？

Answer 1

快速排序实际上不是一种原位算法吗？

它的标准实现是而不是在原地。这是一个非常普遍的误解，但是你可以正确地注意到，由于堆栈空间的消耗，这个概念是错误的。

我说它的“标准实现”是因为人们对算法进行了修改，使其成为O(1)-space算法。这里有一个例子：没有堆栈的快速排序。

当然，与经典的时空权衡一致，这种快速排序版本的性能不如标准实现。

Answer 2

维基百科提供以下定义

在计算机科学中，就地算法(或拉丁文原位算法)是一种使用数据结构转换输入的算法，该算法具有较小的、恒定的额外存储空间。

根据这个定义，典型的基于堆栈的快速排序显然不是一个原位算法.

事实上，维基百科的文章明确地讨论了这一点：

一个算法有时被非正式地称为就地，只要它用输出覆盖它的输入。实际上，这是不够的(快速排序的例子是)，也不是必要的；输出空间可能是常数，甚至可能不被计算，例如，如果输出是流的话。

和

快速排序通常被描述为就地算法，但实际上不是。大多数实现都需要O(log )空间来支持其分治递归。

然而，正如@Jason在他出色的答案中指出的那样，似乎存在着快速排序的变体，只需要额外的O(1)空间。任何这样的算法都将在原地考虑。