这是一个问题标题： 快速排序算法是否是原地排序？

Question

快速排序通常被描述为一种就地（in-place）算法，尽管它需要O(log n)的堆栈空间。那么，就地是指“需要少于O(n)的额外空间”，还是堆栈空间通常不计入空间复杂度（但为什么会这样呢？），或者说快速排序实际上不是一种就地算法？

- fredoverflow

---

这个问题之前已经被问过了：http://cstheory.stackexchange.com/q/9563/6586。基本上，它是一个燃眉之急，有很多互相矛盾的论点。 - jpalecek

请注意，这实际上取决于您如何定义原地排序。如果您只是比较排序算法，那么不考虑快速排序是原地排序可能会非常挑剔，但如果您有一个更正式的定义（带有理由），那么停止忽略小的O(log n)细节是有意义的。 - hugomg

这只是“O(log n)可能是一个相当大的常数”的特殊情况，不是吗？原则上，快速排序使用O(log n)的额外空间。在实践中，通常将其实现为以数组作为参数的形式。在大多数语言中，数组具有基于用于地址和/或索引的固定宽度类型的自然上限大小，并且Quicksort仅需要在每个“log n”深度存储几个地址。因此，对于您实际编写和使用的任何Quicksort实现，堆栈使用都是恒定的，即使对于“理想”版本也是如此。 - Steve Jessop

... 因此，剩下的问题就是关于“原地”定义的适当性的争论了 - Quicksort 的属性很简单，但例如 C 的 qsort 具有这样的属性，即其任何良好的实现都具有固定的最大堆栈使用量。 - Steve Jessop

@Jason：当然会有争议，因为定义只有在它们有用的范围内才有意义。如果你只是将快速排序与归并排序等算法进行比较，那么认为快速排序是原地排序是完全可以接受的。只有在定义复杂度类或进行类似正式的工作时，才需要给出精确的O(1)原地排序定义。 - hugomg

Answer 1

快速排序算法其实并不是原地排序算法吗？

它的标准实现不是原地排序算法，这是一个常见的错误观点，但正如你所正确指出的那样，由于堆栈空间的消耗，这种看法是错误的。

我之所以说“标准实现”是因为人们已改进了算法，使其成为一个O(1)-空间算法。以下是一个例子：无需堆栈的快速排序。

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

- jason

Answer 2

维基百科提供了以下定义：定义：

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

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

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

只要算法用其输出覆盖其输入，它就被非正式地称为原地。但实际上这是不够的（如快速排序的情况所示），也不是必需的；输出空间可以是常数，甚至不需要计数，例如如果输出是到流。

而且

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

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

- NPE