stdlib的qsort是递归的吗？

Question

我读过这qsort只是一种通用的类型,没有关于实现的承诺.我不知道库在不同平台之间的差异,但假设Mac OS X和Linux实现大致相似,那么qsort实现是递归的还是需要大量的堆栈？

我有一个大型数组(数十万个元素),我想要排序它而不会让我的堆栈被遗忘.或者,对于大型数组的等价物的任何建议？

Answer 1

Blindy解释说,虽然递归深度的上限很小,但它是调用递归的.

这是glibc的一个版本,可能在某些时候在Linux系统中使用:

这不是递归的呼叫.出于与调用递归限制相同的原因,它可以使用少量固定数量的堆栈来管理其循环递归.

我可以查看最新版本吗？不 ;-)

对于几十万个数组元素,即使是调用递归实现也不会调用超过20个级别.在一个不太深入的宏观方案中,除了非常有限的嵌入式设备之外,它们没有足够的内存让你有一个大的排序数组.当N在上面有界时,O(log N)显然是一个常数,但是它通常是一个可管理的常数.通常32或64倍"小"是"合理的".

Answer 2

你知道,递归部分是登录深度.在64级递归(大约64*4 =〜256字节的堆栈)中,你可以对一个大小为~2 ^ 64的数组进行排序,即在64位cpu上可以寻址的数组,即147573952589676412928 64位整数的字节数.你甚至不能把它放在记忆中!

担心重要的东西.

@Luther:正确实现时(在递归时,首先对较小的分区进行排序),堆栈使用量限制在近似对数增长.确切地说,Knuth将其表示为[lg(N + 1)/(M + 2)]("[]"表示"floor"),其中N =要排序的元素数量,M =您所在的分区大小停止递归(假设一个"改进的"Quicksort,当整个事物接近排序时切换到插入排序). (6认同)
-1:这是错误的.Quicksort具有最差的案例空间复杂度O(n),而不是O(log n).一个大数组*可以*吹掉堆栈. (3认同)
路德,qsort()不是"Quicksort" - 或者说实际算法是实现定义的.例如,Glibc的qsort()切换到插入排序,以避免最坏的情况下的空间复杂性问题. (3认同)
@ 0A0D:艾伯塔省的幻灯片放映没用.可能是用于教学目的的精细简化,但实际上没有人通过分配两个新阵列来实现分区步骤,一个用于枢轴的每一侧,并且将元素复制到它们中.因此,分析与任何知道他们正在做什么的人编写的Quicksort实现无关 - Quicksort的部分好处是它是一个(几乎)就地算法. (2认同)

Answer 3

是的,它是递归的.不,它可能不会使用大量的堆栈.为什么不试试呢？递归不是某种忌 - 它是许多问题的首选解决方案.

完全脱离主题:[既不是教皇天主教徒,也不是熊在树林里大肆撒谎](http://www.guardian.co.uk/theguardian/2005/feb/08/features11.g2) (7认同)
@Joe qsort如果不能很好地处理非常大的数据集,那将不会是那种选择.这个问题没有错,除了我确实发现这里的许多人不愿意尝试一些有点小便的事情. (4认同)
-1:Quicksort具有最差的案例空间复杂度O(n),这意味着对大型数组*进行排序可以*打击堆栈.如果堆栈空间不充足(如在线程或协程中),那么这是需要考虑的事情. (3认同)
@Joe Depths喜欢什么？快速排序中的递归将堆栈帧(即局部变量和返回地址)推送到堆栈,而不是正在排序的事物的副本.这是非常少的数据. (2认同)

Answer 4

正确实现qsort不需要超过 log2(N) 级的递归（即堆栈深度），其中 N 是给定平台上的最大数组大小。请注意，无论分区的好坏如何，此限制都适用，即它是递归的最坏情况深度。例如，在 32 位平台上，递归的深度在最坏的情况下永远不会超过 32，假设qsort.

换句话说，如果您特别关注堆栈使用情况，则无需担心，除非您正在处理一些奇怪的低质量实现。