当务之急是快速排序原位（就地）或不？ [英] Is imperative Quicksort in situ (in-place) or not?

问题描述

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

解决方案

  

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

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

我说的是标准的实施，因为人们已经修改了算法，使其成为 O（1） -space算法。这里有一个例子：<一href="http://books.google.com/books?id=oaVq6dbw37kC&pg=PA283&dq=Quicksort+in+constant+space&hl=en&sa=X&ei=VUMpT6zTJ8mEtgeB6ej9BA&ved=0CDcQ6AEwAQ#v=onepage&q=Quicksort%20in%20constant%20space&f=false">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.

这篇关于当务之急是快速排序原位（就地）或不？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！