stdlib 的 qsort 是递归的吗？
我读到 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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
这是来自 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倍“小”就是“合理”。
Here's a version from BSD, copyright Apple, presumably used in OS X at some time or another:
http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c
It is call-recursive, although the upper bound on the depth of recursion is small, as Blindy explains.
Here's a version from glibc, presumably used in Linux systems at some time or another:
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 ;-)
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".
你知道，递归部分是很深的。在 64 级递归中（约 64*4=约 256 字节的堆栈总数），您可以对大小为约 2^64 的数组进行排序，即在 64 位 cpu 上可以寻址的数组，即 147573952589676412928 64 位整数的字节数。你甚至无法将它保留在记忆中！
在我看来，担心重要的事情。
You know, the recursive part is logn deep. In 64 levels of recursion (which is ~64*4=~256 bytes of stack total) you can sort an array of size ~2^64, ie an array as large as you can address on a 64 bit cpu, which is 147573952589676412928 bytes for 64 bit integers. You can't even hold it in memory!
Worry about stuff that matters imo.
是的，它是递归的。不，它可能不会使用大量的堆栈。为什么不简单地尝试一下呢？递归并不是某种禁忌——它是许多问题的首选解决方案。
Yes it's recursive. No, it probably will not use large amounts of stack. Why not simply try it? Recursion is not some kind of bogey - it's the solution of choice for very many problems.
正确实现的 qsort 不需要超过 log2(N) 级递归（即堆栈深度），其中 N 是给定平台上的最大数组大小。请注意，无论分区的好坏如何，此限制都适用，即它是最坏情况的递归深度。例如，在 32 位平台上，只要
qsort实现合理，在最坏的情况下，递归深度永远不会超过 32。换句话说，如果您特别关心堆栈的使用情况，则无需担心，除非您正在处理一些奇怪的低质量实现。
A properly implemented
qsortdoes not require more than log2(N) levels of recursion (i.e. depth of stack), where N is the largest array size on the given platform. Note that this limit applies regardless of how good or bad the partitioning happens to be, i.e. it is the worst case depth of recursion. For example, on a 32-bit platform, the depth of recursion will never exceed 32 in the worst possible case, given a sane implementation ofqsort.In other words, if you are concerned about the stack usage specifically, you have nothing to worry about, unless you are dealing with some strange low-quality implementation.
我记得读过这本书：C 编程：现代方法
ANSI C 规范没有定义如何实现 qsort。
书中写道，
qsort实际上可能是另一种排序、合并排序、插入排序，为什么不是冒泡排序：P因此，
qsort实现可能不是递归的。I remember reading in this book: C Programming: A Modern Approach
that the ANSI C specification doesn't define how to implement qsort.
And the book wrote that
qsortcould in reality be a another kind of sort, merge sort, insertion sort and why not bubble sort :PSo, the
qsortimplementation might not be recursive.使用快速排序，堆栈将以对数方式增长。您将需要大量元素来炸毁您的堆栈。
With quicksort, the stack will grow logarithmically. You will need a lot of elements to blow up your stack.
我猜想
qsort的大多数现代实现实际上都使用 Introsort 算法。合理编写的快速排序无论如何都不会破坏堆栈（它会首先对较小的分区进行排序，这将堆栈深度限制为对数增长）。不过，Introsort 更进一步——为了限制最坏情况的复杂性，如果它发现快速排序运行不佳（递归太多，因此可能具有 O(N2) 复杂性），它会将切换到堆排序，它保证 O(N log2 N) 复杂度并且也限制堆栈的使用。因此，即使它使用的Quicksort写得很马虎，切换到Heapsort无论如何也会限制堆栈的使用。
I'd guess that most modern implementations of
qsortactually use the Introsort algorithm. A reasonably written Quicksort won't blow the stack anyway (it'll sort the smaller partition first, which limits stack depth to logarithmic growth).Introsort goes a step further though -- to limit the worst case complexity, if it sees that Quicksort isn't working well (too much recursion, so it could have O(N2) complexity), it'll switch to a Heapsort which guarantees O(N log2 N) complexity and limits stack usage as well. Therefore, even if the Quicksort it uses is sloppily written, the switch to Heapsort will limit stack usage anyway.
在大型数组上可能失败的 qsort 实现是非常糟糕的。如果你真的担心我会选择 RTFS，但我怀疑任何半体面的实现要么使用就地排序算法，要么使用
malloc作为临时空间并回退到就地malloc失败时的算法。A
qsortimplementation which can fail on large arrays is extremely broken. If you're really worried I'd go RTFS, but I suspect any half-decent implementation will either use an in-place sorting algorithm or usemallocfor temporary space and fall back to an in-place algorithm ifmallocfails.朴素快速排序实现（仍然是 qsort 的流行选项）的最坏情况空间复杂度是 O(N)。 如果修改实现以首先对较小的数组进行排序和尾递归优化或使用显式堆栈和迭代则最坏情况空间可以降低到 O(log N)，（这里大多数答案已经写过）。因此，如果快速排序的实现没有被破坏并且库没有被不正确的编译器标志破坏，那么您就不会炸毁堆栈。但是，例如，大多数支持尾递归消除的编译器不会在未优化的调试版本中进行此优化。使用错误标志构建的库（即没有足够的优化，例如在嵌入式域中，您有时构建自己的调试 libc）可能会使堆栈崩溃。
对于大多数开发人员来说，这永远不会成为问题（他们有供应商测试过的 libc，其空间复杂度为 O(log N)），但我想说，时不时地关注潜在的库问题是个好主意。
更新：这是我的意思的一个例子：libc 中的一个错误（从 2000 年开始），其中 qsort 会开始破坏虚拟内存，因为 qsort 实现会在内部切换到合并排序，因为它虽然有足够的内存来保存临时数组。
http://sources.redhat.com/ml/libc-阿尔法/2000-03/msg00139.html
The worst-case space-complexity of a naive quicksort implementation (which is still a popular option for qsort) is O(N). If the implementation is modified to sort the smaller arary first and tail-recursion optimisation or an explicit stack and iteration is used then the worst case space can be brought down to O(log N), (what most answers here wrote already). So, you will not blow up your stack if the implementation of quick-sort is not broken and the library was not broken by improper compiler flags. But, for example, most compiler which support tail recursion elimination won't do this optimization it in unoptimized debug builds. A library built with the wrong flags (i.e. not enough optimization, for example in the embedded domain where you sometimes build your own debug libc) might crash the stack then.
For most developers, this will never be an issue (they have vendor tested libc's which have O(log N) space complexity), but I'd say it is a good idea to have an eye on potential library issues from time to time.
UPDATE: Here's an example for what I mean: A bug in libc (from 2000) where qsort would start thrashing virtual memory because the qsort implementation would switch internally to mergesort because it though there is enough memory to hold a temporary array.
http://sources.redhat.com/ml/libc-alpha/2000-03/msg00139.html