是STDLIB的递归的qsort？ [英] Is stdlib's qsort recursive?

问题描述

我读过的qsort 只是一个普通的那种，不执行有关承诺。我不知道图书馆如何变化，从平台者平台，但假设Mac OS X和Linux实现大体相似，是的qsort 实现递归和/还是需要大量的叠

I've read that qsort is just a generic sort, with no promises about implementation. I don't know about how libraries vary from platform to plaform, but assuming the Mac OS X and Linux implementations are broadly similar, are the qsort implementations recursive and/or require a lot of stack?

我有一个大阵列（成千上万的元素），我想不吹我的筹码被遗忘对它进行排序。此外，一个相当于为大型阵列有什么建议？

I have a large array (hundreds of thousands of elements) and I want to sort it without blowing my stack to oblivion. Alternatively, any suggestions for an equivalent for large arrays?

推荐答案

下面是从BSD，版权苹果，$ P $版本在一段时间或其他在OS X中使用psumably：

Here's a version from BSD, copyright Apple, presumably used in OS X at some time or another:

<一个href=\"http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c\">http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c

这是调用递归，但递归的深度上限很小，因为Blindy解释说。

It is call-recursive, although the upper bound on the depth of recursion is small, as Blindy explains.

下面是glibc的版本，$ P $在一段时间或其他Linux系统psumably使用：

Here's a version from glibc, presumably used in Linux systems at some time or another:

<一个href=\"http://www.umcs.maine.edu/~chaw/200801/capstone/n/qsort.c\">http://www.umcs.maine.edu/~chaw/200801/capstone/n/qsort.c

这是的不的递归调用。为完全同样的原因，在呼叫递归极限小，它可以使用堆叠的小的固定量来管理其循环递归

It's not call recursive. For exactly the same reason that the limit on call-recursion is small, it can use a small fixed amount of stack to manage its loop-recursion.

我可以懒得去查找最新版本？没了; - ）

Can I be bothered to look up the latest versions? Nope ;-)

有关几十万数组元素，甚至呼叫递归实现不会打电话超过20级。在事物的宏伟计划是不深，除了在非常有限的嵌入式设备，这将没有足够的内存让你有一个数组，大到在第一时间进行排序。当n为上界，为O（log N）显然是一个的恒的，但比它通常相当恒定的管理更加。通常为32或64倍的小，是合理的。

For a few hundred thousand array elements, even the call-recursive implementation won't call more than 20 levels deep. In the grand scheme of things that is not deep, except on very limited embedded devices, which wouldn't have enough memory for you to have an array that big to sort in the first place. When N is bounded above, O(log N) obviously is a constant, but more than that it's normally quite a manageable constant. Usually 32 or 64 times "small" is "reasonable".

这篇关于是STDLIB的递归的qsort？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！