迭代（基于堆栈）快速排序比递归快吗？

Question

在很多地方，我都看到过使用堆栈实现快速排序比使用递归更快的说法。这是真的吗？我知道编译器通常擅长将递归转换为迭代，但页面上的评论称，递归太复杂，无法优化。

快速排序还有哪些其他优化？

以下是我提到的一些地方，即递归实现优于递归实现：http://www.geeksforgeeks.org/iterative-quick-sort/

尽管有上述优化，该函数仍然是递归的，并使用函数调用堆栈来存储l和h的中间值。函数调用堆栈将其他簿记信息与参数一起存储。此外，函数调用涉及开销，如存储调用函数的激活记录，然后恢复执行。

在辅助堆栈的帮助下，上述函数可以很容易地转换为迭代版本。

快速排序：迭代或递归

我了解到递归算法总是比迭代算法慢。
然而，答案指出这并不总是正确的，尽管我不明白为什么在系统堆栈上存储函数状态所涉及的开销会有争论。

使用显式堆栈和迭代代替递归实现的优势基本上有三个方面：

http://www.codeproject.com/Articles/23196/Iterative-Quick-Sort

Using an explicit stack allows the sort to avoid the temporary storage of unnecessary information.
Rather than placing two partitions on a stack in arbitrary order, as a typical recursive Quicksort would implicitly do, the sizes of the

首先检查分区，并堆叠指示两者中较大者的指针。较小分区的指针根本没有堆叠：我们能够做到这一点，因为我们可以保证较小分区始终等效于第二个递归调用，第二个递归调用位于函数的末尾。这带来了第三个优点：可以消除任何后端递归，并用简单循环替换。

评论代码评论

由于递归，它不会扩展：JVM没有尾部调用优化，它只会将方法调用堆栈增长到与要排序的数组成比例的大小，并且对于太大的数组也会失败。（即使对于确实有尾部调用优化的语言/平台，我认为他们也无法将其实际应用于此代码）

这里也有很多基于堆栈/迭代的快速排序实现，但我想程序员这样做只是为了好玩？

Answer 1

递归算法几乎总是基于堆栈：它们使用“调用堆栈”，只有在尾部递归的情况下，最后一个调用记录才会被覆盖。使用递归的一个潜在优化是，增加调用堆栈是单个CPU指令。因此，在硬件支持方面，递归算法有时会更快。

在大多数情况下，您可以优化堆栈（例如，因为某些参数（如要排序的数组）仍然相同，或者因为只有一个返回地址）。如果是这种情况，显式堆栈可以更快。

一些编译器将尝试优化递归算法本身。但就像在几乎所有的优化案例中一样：不确定哪种算法会更快。

Answer 2

你给我们的链接并没有说在Java中使用堆栈更快，它说JVM会对一个大的排序数组进行堆栈溢出。顺便说一句，大多数（全部？）递归是用堆栈实现的。

请提供正确的链接，指向解释堆栈为什么比递归快的参数。没有这一点，我们无法回答。