Quicksort 通常被描述为一种原位(就地)算法，尽管它需要 O(log n) 堆栈空间。那么 in situ 是否意味着“需要少于 O(n) 的额外空间”，或者堆栈空间通常不算作空间复杂度(但为什么会这样？)，或者 Quicksort 实际上不是原位算法？
最佳答案
is Quicksort actually not an in situ algorithm?
它的标准实现不是就地。这是一个非常普遍的误解，但由于堆栈空间消耗，您正确地注意到，这个概念是错误的。
我说它的“标准实现”是因为人们修改了算法使其成为 O(1) 空间算法。这是一个例子:Quicksort without a stack .
当然和经典一致space-time tradeoff ，此类版本的快速排序的性能低于标准实现。
关于algorithm - 命令式 Quicksort 是否就地(in-place)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9096787/