c - 通过队列实现快速排序？

Question

我可以使用队列实现快速排序吗？
我只找到这篇文章https://www.quora.com/Can-we-use-a-queue-in-quicksort-in-C .
这篇文章是否正确？
如果是，为什么教科书总是只实现堆栈快速排序或递归方法？
因为这个问题的资料很少，所以在这里问一下。

Answer 1

缓存性能差

有了栈，我们有足够的时间局部性，而有了队列，它就完全丢失了。我们基本上是尝试在队列方法中以广度优先搜索方式对数组进行排序。

编辑(来自 Will Ness 的回答):对于更大的数组 (>RAM)，队列方法甚至不起作用，因为它需要 O(n) 空间来对大小为 n 的数组进行排序.而基于堆栈的方法只需要 log n 空间。两者的所有理论时间复杂度都是一样的。