我读过这qsort只是一种通用的排序，没有关于实施的承诺。我不知道库如何因平台而异，但假设 Mac OS X 和 Linux 实现大致相似，那么这些qsort实现是递归的和/或需要大量堆栈吗？
我有一个大数组（数十万个元素），我想对它进行排序，而不会让我的堆栈被遗忘。或者，对于大型数组的等效项有什么建议吗？
问问题
7080 次
9 回答
22
这是来自 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 倍的“小”是“合理的”。
于 2010-07-31T21:05:22.230 回答
12
你知道，递归部分是logn deep。在 64 级递归中（总共 ~64*4=~256 字节的堆栈），您可以对大小为 ~2^64 的数组进行排序，即您可以在 64 位 cpu 上寻址的最大数组，即 147573952589676412928 64 位整数的字节。你甚至无法记住它！
担心 imo 重要的事情。
于 2010-07-31T20:50:37.100 回答
10
是的，它是递归的。不，它可能不会使用大量堆栈。为什么不简单地尝试一下？递归不是某种柏忌——它是许多问题的首选解决方案。
于 2010-07-31T20:46:42.503 回答
5
正确实现qsort不需要超过 log2(N) 级别的递归（即堆栈深度），其中 N 是给定平台上的最大数组大小。请注意，无论分区的好坏，这个限制都适用，即它是最坏情况下的递归深度。例如，在 32 位平台上，递归深度在最坏的可能情况下永远不会超过 32，只要qsort.
换句话说，如果您特别关心堆栈的使用，则无需担心，除非您正在处理一些奇怪的低质量实现。
于 2010-07-31T21:21:31.597 回答
2
我记得读过这本书：C Programming: A Modern Approach ANSI C 规范没有定义如何实现 qsort。
这本书写道，qsort实际上可能是另一种排序，合并排序，插入排序，为什么不是冒泡排序：P
因此，qsort实现可能不是递归的。
于 2010-07-31T21:19:43.917 回答
1
使用快速排序，堆栈将以对数方式增长。你需要很多元素来炸毁你的堆栈。
于 2010-07-31T20:51:48.880 回答
1
我猜想大多数现代实现qsort实际上都使用 Introsort 算法。一个合理编写的快速排序无论如何都不会破坏堆栈（它会首先对较小的分区进行排序，这将堆栈深度限制为对数增长）。
不过，Introsort 更进了一步——为了限制最坏情况的复杂性，如果它发现 Quicksort 运行不佳（递归过多，因此它可能具有 O(N 2 ) 复杂性），它将切换到 Heapsort 哪个保证 O(N log 2 N) 复杂度并限制堆栈使用。因此，即使它使用的 Quicksort 写得很草率，切换到 Heapsort 无论如何都会限制堆栈的使用。
于 2010-07-31T21:06:22.513 回答
0
可能在大型阵列上失败的qsort实现被严重破坏。如果你真的担心我会选择 RTFS，但我怀疑任何半体面的实现要么使用就地排序算法，要么malloc用于临时空间，如果失败则回退到就地算法malloc。
于 2010-07-31T20:53:08.357 回答
0
天真的快速排序实现（仍然是 qsort 的流行选项）的最坏情况空间复杂度是 O(N)。如果修改实现以首先对较小的数组进行排序并使用尾递归优化或显式堆栈和迭代，则最坏情况的空间可以降低到 O(log N)，（这里的大多数答案已经写过了）。因此，如果快速排序的实现没有被破坏并且库没有被不正确的编译器标志破坏，你就不会炸毁你的堆栈。但是，例如，大多数支持尾递归消除的编译器不会在未优化的调试版本中进行此优化。使用错误标志构建的库（即没有足够的优化，例如在您有时构建自己的调试 libc 的嵌入式域中）可能会导致堆栈崩溃。
对于大多数开发人员来说，这永远不会成为问题（他们有供应商测试了具有 O(log N) 空间复杂度的 libc），但我认为不时关注潜在的库问题是个好主意。
更新：这是我的意思的一个例子：libc 中的一个错误（从 2000 年开始），其中 qsort 将开始颠簸虚拟内存，因为 qsort 实现将在内部切换到 mergesort，因为它虽然有足够的内存来保存临时数组。
http://sources.redhat.com/ml/libc-alpha/2000-03/msg00139.html
于 2010-07-31T22:02:16.547 回答