stdlib的qsort是递归的吗?

以下是BSD的一个版本,版权归苹果所有,大概是在某个时候在OS X中使用的:

http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c

它被称为递归,尽管递归深度的上限很小,正如Blindy所解释的。

http://www.umcs.maine.edu/~chaw/200801/capstone/n/qsort.c

它是 不

能麻烦我查一下最新版本吗?没有;-)

对于几十万个数组元素,即使调用递归实现也不会调用超过20层的深度。在这个宏大的计划中,除了在非常有限的嵌入式设备上,没有足够的内存让你有一个那么大的数组来排序。当N在上面有界时,O(logn)显然是a 常数 但更重要的是,它通常是一个可控的常数。通常32或64倍的“小”是“合理的”。

你知道,递归部分是logn deep。在64级递归(即~64*4=~256字节的堆栈总数)中,可以对大小为~2^64的数组进行排序,即在64位cpu上可以寻址的大小的数组,64位整数的大小为147573952589676412928字节。你连记忆都记不住了!

担心一些重要的事情。

是的,它是递归的。不,它可能不会使用大量堆栈。为什么不试试呢?递归并不是什么谬论,它是很多问题的首选解决方案。

适当实施的 qsort 不需要超过log2(N)级的递归(即堆栈深度),其中N是给定平台上的最大数组大小。请注意,此限制适用 分区的好坏,即 递归深度。例如,在32位平台上,给定一个合理的 快速排序 .

换句话说,如果您特别关心堆栈的使用,那么就不必担心,除非您正在处理一些奇怪的低质量实现。

我记得在这本书里读到: C Programming: A Modern Approach ansic规范没有定义如何实现qsort。

qsort 实际上可能是另一种排序,合并排序,插入排序,为什么不是冒泡排序呢

快速排序

使用快速排序,堆栈将按对数增长。你需要 很多 元素来炸毁你的堆栈。

我猜 qsort 实际使用Introsort算法。合理编写的快速排序无论如何也不会破坏堆栈(它会首先对较小的分区进行排序,这将堆栈深度限制为对数增长)。

)复杂性),它将切换到一个Heapsort,该Heapsort保证O(N log ₂ N) 复杂性 也限制了堆栈的使用。因此,即使它使用的快速排序是草率编写的,切换到Heapsort也会限制堆栈的使用。

A qsort 在大型阵列上可能失败的实现是非常失败的。如果你真的担心我会使用RTFS,但我怀疑任何半体面的实现要么使用就地排序算法,要么使用 malloc

简单快速排序实现(这仍然是qsort的一个流行选项)最坏的空间复杂度是O(N)。 该实现被修改为先对较小的arary进行排序 使用尾部递归优化或显式堆栈和迭代 然后

对于大多数开发人员来说,这永远不会是一个问题(他们已经对libc进行了供应商测试,libc的空间复杂度为O(logn)),但我认为不时关注潜在的库问题是一个好主意。

http://sources.redhat.com/ml/libc-alpha/2000-03/msg00139.html