algorithm - 是否是原地（就地）命令式快速排序？

Question

快速排序通常被描述为原位（就地）算法，尽管它需要 O(log n) 堆栈空间。那么原位是否意味着“需要少于 O(n) 的额外空间”，或者堆栈空间通常不算作空间复杂度（但为什么会这样呢？），或者 Quicksort 实际上不是原位算法？

Answer 1

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

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

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

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

Answer 2

维基百科提供以下定义：

在计算机科学中，就地算法（或拉丁语中的原位算法）是一种使用具有少量恒定额外存储空间的数据结构来转换输入的算法。

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

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

一个算法有时被非正式地就地调用，只要它用它的输出覆盖它的输入。实际上，这还不够（如快速排序的例子所示），也没有必要；输出空间可能是恒定的，甚至可能不被计算在内，例如，如果输出是流。

和

快速排序通常被描述为一种就地算法，但实际上并非如此。大多数实现需要 O(log n) 空间来支持其分而治之的递归。

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