stdlib的qsort是递归的吗？
我已经读过qsort只是一种通用的类型，没有关于实现的承诺。 我不知道库在不同平台之间的差异，但假设Mac OS X和Linux实现大致相似， 那么qsort实现是递归的还是需要大量的堆栈 ？
我有一个大型数组（数十万个元素），我想要排序它而不会让我的堆栈被遗忘。 或者，对于大型数组的等价物的任何建议？
这是来自BSD的版本，版权所有Apple，可能在某些时候在OS X中使用：
http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c
Blindy解释说，虽然递归深度的上限很小，但它是调用递归的。
这是glibc的一个版本，可能在某些时候在Linux系统中使用：
http://www.umcs.maine.edu/~chaw/200801/capstone/n/qsort.c
这不是递归的呼叫。 出于与调用递归限制相同的原因，它可以使用少量固定数量的堆栈来管理其循环递归。
我可以打扰查看最新版本吗？ 不 ;-）
对于几十万个数组元素，即使是调用递归实现也不会调用超过20个级别。 在不太深入的宏观方案中，除了非常有限的嵌入式设备之外，没有足够的内存让你有一个大的排序数组。 当N在上面有界时，O（log N）显然是一个常数 ，但是它通常是一个可管理的常数。 通常32或64倍“小”是“合理的”。
你知道，递归部分是登录深度。 在64级递归（大约64 * 4 =〜256字节的堆栈）中，您可以对大小为~2 ^ 64的数组进行排序，即在64位cpu上可以寻址的数组，即147573952589676412928 64位整数的字节数。 你甚至不能把它放在记忆中！
担心重要的东西。
是的，这是递归的。 不，它可能不会使用大量的堆栈。 为什么不试试呢？ 递归不是某种忌 – 它是许多问题的首选解决方案。
正确实现的qsort不需要超过log2（N）级别的递归（即堆栈深度），其中N是给定平台上的最大arrays大小。 请注意， 无论分区的好坏程度如何，此限制都适用，即最坏情况下的递归深度。 例如，在一个32位平台上，在最糟糕的情况下，递归深度永远不会超过32，给出一个合理的qsort实现。
换句话说，如果您特别关注堆栈使用情况，除非您正在处理一些奇怪的低质量实现，否则您无需担心。
我记得在本书中读到： C编程：现代方法 ，ANSI C规范没有定义如何实现qsort。
这本书写道， qsort实际上可以是另一种排序，合并排序，插入排序以及为什么不冒泡排序：P
因此， qsort实现可能不是递归的。
使用quicksort，堆栈将以对数方式增长。 你将需要很多元素来炸毁堆栈。
我猜大多数qsort现代实现实际上都使用了Introsort算法。 一个合理编写的Quicksort无论如何都不会打击堆栈（它会先对较小的分区进行排序，这会将堆栈深度限制为对数增长）。
Introsort更进了一步 – 为了限制最坏的情况复杂性，如果它看到Quicksort运行不正常（递归过多，因此可能有O（N 2 ）复杂度），它将切换到Heapsort，保证O（N log 2 N）复杂度并限制堆栈使用。 因此，即使它使用的Quicksort写得很潦草，切换到Heapsort也会限制堆栈的使用。
在大型arrays上失败的qsort实现非常破碎。 如果你真的担心我会去RTFS，但是我怀疑任何半好的实现都会使用就地排序算法或者使用malloc作为临时空间，如果malloc失败则回退到就地算法。
天真快速实施（对qsort来说仍然是一个流行的选项）的最坏情况空间复杂度是O（N）。 如果修改实现以首先对较小的arary进行排序并且使用尾递归优化或使用显式堆栈和迭代， 那么最坏情况空间可以降低到O（log N），（这里已经写出了大多数答案）。 因此，如果快速排序的实现没有被破坏并且库没有被不正确的编译器标志破坏，那么您将不会炸毁堆栈。 但是，例如，大多数支持尾递归消除的编译器都不会在未经优化的调试版本中对其进行优化。 使用错误标志构建的库（即，没有足够的优化，例如在您有时构建自己的调试libc的嵌入式域中）可能会使堆栈崩溃。
对于大多数开发人员来说，这永远不会成为一个问题（他们有供应商测试的libc具有O（log N）空间复杂度），但我认为不时关注潜在的库问题是个好主意。
更新：这是我的意思的一个例子：libc（来自2000）中的一个错误，其中qsort将开始颠倒虚拟内存，因为qsort实现将在内部切换到mergesort，因为它虽然有足够的内存来容纳临时数组。
http://sources.redhat.com/ml/libc-alpha/2000-03/msg00139.html