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

在不同的地方我看到声称使用堆栈实现快速排序比使用递归更快。这是真的？我知道编译器通常擅长将迭代更改为迭代，但链接到声明的页面上的注释太复杂，无法优化。迭代（基于堆栈）快速排序比递归更快吗？

quicksort还有哪些其他优化？

这里有一些地方，我红认为itterative实现比递归的要好： http://www.geeksforgeeks.org/iterative-quick-sort/

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

上述功能可以很容易地转换为迭代版本，辅助堆栈的帮助。

Quicksort : Iterative or Recursive

我了解到，递归算法总是比他们的迭代对应慢。
但是答案指出这并非总是如此，虽然我不明白为什么会在系统堆栈中存储函数状态所涉及的开销的原因。

代替递归实现的使用显式堆叠和迭代的优点是基本上三倍：

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 
分区被检查第一和指示所述指针较大的这两个堆叠。由于我们可以保证较小的分区总是等于函数尾部的第二个递归调用，所以我们可以做到这一点。这导致第三个的优势：任何尾端递归都可以被消除并用一个简单的循环代替。

Comment on codereview

它不能扩展，由于递归：在JVM没有尾巴电话优化，它只会增加方法调用堆栈成正比阵列东西进行排序，并将失败太大的数组。（甚至对于语言/平台，确实有尾调用优化，我不认为他们会能够真正应用到这个代码）

也有基于相当多的堆栈/迭代实现快速排序here，但我想编码器只是为了好玩而这么做的？

来源

2014-07-15 Celeritas

你的基准测试告诉你什么？ –

比较苹果和橘子？你不是指迭代还是递归？ – leppie

@MarkRansom我的大脑告诉我，这是一种离开后者基准的情况，并在随机散列代码并将其关入基准测试程序之前给出一些理论思考。 – Celeritas

你给我们的链接并没有说在Java中使用堆栈更快，它表示JVM会堆栈溢出一个大的排序数组。顺便说一下，大多数（所有？）递归都是通过堆栈实现的。

请给出正确的链接指向参数，解释为什么堆栈比递归更快。没有这个我们不能回答。

来源

2014-07-15 08:46:46 fjardon

确定更新了链接。我听到的另一个说法是，堆栈可以比系统堆栈更快速地执行快速排序（可能是自定义裁剪的情况）。这对我来说没有意义，因为不是堆栈如此简单，对于一个实现比另一个实现更好，没有意义。 – Celeritas

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

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

一些编译器会尝试优化递归算法本身。但正如几乎所有的优化情况一样：不确定哪种算法会更快。

来源

2014-07-15 08:58:28

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

回答

相关问题