由网友(仟陌)分享简介：快速排序通常被描述为一个的原位的（就地）算法，尽管它需要O（log n）的堆栈空间的事实。所以做的原位的意思是要求少于O（n）的额外空间，还是栈空间一般不会算作空间复杂度（但为什么会是这样的话？），或者是快速排序实际上不是一个的原位的算法？解决方案 是快速排序实际上并不是一个原地算法？标准的实施是不可以的原位的。这是...

快速排序通常被描述为一个的原位的（就地）算法，尽管它需要O（log n）的堆栈空间的事实。所以做的原位的意思是要求少于O（n）的额外空间，还是栈空间一般不会算作空间复杂度（但为什么会是这样的话？），或者是快速排序实际上不是一个的原位的算法？

解决方案   

是快速排序实际上并不是一个原地算法？

标准的实施是不可以的原位的。这是一个可怕的普遍的误解，但你作为正确注意到，由于堆栈空间消耗，这观念是错误的。

我说的是标准的实施，因为人们已经修改了算法，使其成为 O（1） -space算法。这里有一个例子：Quicksort没有堆。

当然，与经典的时空权衡一致，快速排序等版本比标准实现高性能的少。

Quicksort is often described as an in situ (in-place) algorithm, despite the fact that it requires O(log n) stack space. So does in situ mean "requires less than O(n) additional space", or does stack space generally not count as space complexity (but why would that be the case?), or is Quicksort actually not an in situ algorithm?

解决方案

is Quicksort actually not an in situ algorithm?

The standard implementation of it is not in situ. It's a horribly common misconception, but you as correctly note due to stack space consumption, that conception is wrong.

I say "standard implementation" of it because people have modified the algorithm to make it an O(1)-space algorithm. Here is one example: Quicksort without a stack.

Of course, consistent with the classic space-time tradeoff, such versions of quicksort are less performant than the standard implementation.