我读过qsort只是一种通用排序，不承诺实施。我不知道库在不同平台上有何不同，但假设 Mac OS X 和 Linux 实现大致相似，are the 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
It's not调用递归。出于完全相同的原因，调用递归的限制很小，它可以使用少量固定数量的堆栈来管理其循环递归。
我可以费心查找最新版本吗？没有 ;-）
对于几十万个数组元素，即使调用递归实现也不会调用超过 20 层深度。从宏伟的计划来看，这并不深入，除了非常有限的嵌入式设备，这些设备没有足够的内存让您首先拥有这么大的数组进行排序。当 N 有界以上时，O(log N) 显然是constant，但更重要的是，它通常是一个相当易于管理的常数。通常32或64倍“小”就是“合理”。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
