logo标签列表

stdlib的qsort函数是递归的吗？

csortinglibcqsort
11

我读过qsort是一种通用排序算法，没有任何关于实现的承诺。我不知道各个平台库之间的差异，但是假设Mac OS X和Linux的实现大致相似，qsort的实现是递归和/或需要大量堆栈吗？

我有一个大数组（成千上万个元素），我想在不使堆栈崩溃的情况下对其进行排序。或者，是否有类似的针对大数组的排序算法可以推荐？

9个回答
22
这里有两个版本的qsort.c，一个来自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倍的“小”是“合理的”。
1
+1 如果你真的查看了源代码。有趣的是，glibc 在 qsort() 中使用快速排序/插入排序混合算法。 - nos
1
@nos：如果我没记错的话，那就是Knuth告诉你要做的事情，所以很有趣，但希望不会让人感到惊讶;-) - Steve Jessop
12

你知道，递归部分的深度是logn。在64个递归级别（大约是64*4=256字节的堆栈总大小）中，您可以对大小约为2^64的数组排序，即您可以在64位CPU上寻址的最大数组大小147573952589676412928字节，您甚至无法将其全部存储在内存中！

我认为应该关注有意义的事情。

+1。可能会有更多的字节，取决于每个级别推入堆栈的量，但它仍然是一个很小的常数。 - ShreevatsaR
3
这是错误的。快速排序的最坏情况下空间复杂度是O(n)，而不是O(log n)。一个大数组确实有可能会造成栈溢出。 - Nordic Mainframe
6
@Luther：如果正确实现（递归时，先对较小的分区进行排序），堆栈使用量将呈对数增长。确切地说，Knuth 将其表示为 [lg(N+1)/(M+2)]（其中“[]”表示“底部取整”），其中 N=要排序的元素数量，M=停止递归的分区大小（假设使用“改进”的快速排序，当整个数组几乎有序时切换到插入排序）。 - Jerry Coffin
3
路德，qsort()并不是“快速排序”——实际上算法的具体实现是由编译器定义的。例如，Glibc中的qsort()会转换为插入排序以避免最坏情况下的空间复杂度问题。 - Gmaxwell
2
@0A0D：那个阿尔伯塔幻灯片不太有用。可能对于教学目的来说是一种很好的简化，但实际上没有人通过分配两个新数组，并将元素复制到它们中的方式来实现划分步骤。因此，该分析与任何由知道自己在做什么的人编写的快速排序实现都无关 - 快速排序的部分好处在于它是一种（几乎）原地算法。 - Steve Jessop
显示剩余6条评论
10

是的，它是递归的。不过，它可能不会使用大量的堆栈。为什么不试一下呢？递归并不是某种可怕的东西 - 它是许多问题的首选解决方案。

2
@Joe Depths 像什么？快速排序中的递归将堆栈帧（即局部变量和返回地址）推送到堆栈上，而不是被排序的内容的副本。这是非常少的数据。 - anon
4
如果qsort不能很好地处理大型数据集，它不会成为首选。没有问题，只是我发现这里很多人不愿意真正尝试一些东西有点让人不爽。 - anon
7
完全离题：教皇不是天主教徒，大多数熊也不是在森林里拉屎 - ShreevatsaR
3
快速排序的最坏空间复杂度为O(n)，这意味着对于一个大数组进行排序可能会导致栈溢出。如果栈空间不充足（如在线程或协程中），那么这是需要考虑的问题。 - Nordic Mainframe
1
叹息；这个俏皮话引起了相当多的“冒犯”，所以我把它编辑掉了。 - Marc Gravell
显示剩余10条评论
5
一个正确实现的qsort不需要超过log2(N)层递归（即栈深度），其中N是给定平台上最大数组大小。请注意，这个限制适用于无论分区好坏如何，即它是递归的最差情况深度。例如，在32位平台上，递归深度在最坏情况下永远不会超过32，假设qsort实现合理。
换句话说，如果你担心特定的堆栈使用情况，除非你处理某些奇怪的低质量实现，否则你没有什么可担心的。
2
我记得在这本书中读到过：C语言程序设计现代方法，其中提到ANSI C规范并没有定义如何实现qsort。
该书还写道，qsort实际上可以是另一种排序方法，比如归并排序、插入排序，甚至冒泡排序:P
因此，qsort的实现可能不是递归的。
2
好的标准并不描述如何实现任何东西 - 但对于像排序这样的事情，它们确实指定了最小复杂度保证，这可能会限制实现算法的选择。 - anon
2
@Neil：不管好的标准有什么作用，事实上C标准并没有规定qsort和bsearch的复杂性。幸运的是，这个问题特别涉及到两个具体的实现，所以标准基本上是无关紧要的。如果苹果在下一个版本中倒行逆施地将OS X切换到Bogosort，那么他们是否能够得逞并不取决于它是否违反了C标准... - Steve Jessop
1

使用快速排序，堆栈将以对数方式增长。您需要非常多的元素才能使堆栈溢出。

1
@msw：既然你坚持要苛求细节，那么你忘记定义N为数组的大小了。就我而言，当谈论算法时，“对数增长”一词通常被理解为O(lg(n))。 - Daniel Egeberg
1

我猜现代大多数实现的qsort实际上使用了Introsort算法。一个合理编写的快速排序不会导致栈溢出（它会先对较小的分区进行排序，从而将栈深度限制在对数增长范围内）。

然而，Introsort更进一步——为了限制最坏情况下的复杂度，如果它发现快速排序效果不好（递归太多，可能导致O(N2)的复杂度），它会切换到堆排序，保证O(N log2 N)的复杂度，并且也限制了栈的使用。因此，即使它所使用的快速排序写得不够好，切换到堆排序仍然会限制栈的使用。

0
一个在大数组上可能失败的qsort实现是极其糟糕的。如果你真的很担心，我建议你去看看源代码，但我怀疑任何半靠谱的实现都会使用原地排序算法或者使用malloc来分配临时空间，并在malloc失败时退回到原地排序算法。
0

一个朴素的快速排序实现（仍然是qsort的流行选项）的最坏空间复杂度为O(N)。 如果修改实现以首先对较小的数组进行排序并且使用尾递归优化或显式堆栈和迭代，那么最坏情况下的空间可以降至O(log N)，（大多数答案已经写了）。因此，如果快速排序的实现没有问题，并且库没有被不当的编译器标志破坏，则不会使堆栈溢出。但是，例如，大多数支持尾递归消除的编译器不会在未优化的调试构建中执行此优化。使用错误标志构建的库（例如，在嵌入式领域中，有时需要构建自己的调试libc）可能会导致堆栈崩溃。

对于大多数开发人员来说，这永远不会成为问题（他们拥有供应商测试过的具有O(log N)空间复杂度的libc），但我认为定期关注潜在的库问题是个好主意。

更新：这里是我的一个例子：2000年libc中的一个错误，其中qsort将开始扰乱虚拟内存，因为qsort实现会在内部切换到mergesort，因为它认为有足够的内存来容纳临时数组。

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

2
问询者询问特定系统，其实现具有合理的质量。"naive quicksort implementation is still a popular option" 这句话是错误的。它不受关注的是编写C库的人群，这也是问题所关心的。 - Steve Jessop
1
问询者询问了关于“Linux”的问题。由于它是一个内核，Linux没有实现qsort。qsort是C运行时库的一个函数，有几个选项（glibc、uclibc、newlib、dietlibc等），还有他们放入Android中的东西。另外，请查看我的更新。 - Nordic Mainframe
我觉得一个假设的糟糕实现的qsort并不重要。glibc的qsort实现相当不错，我认为OS X的也是如此。糟糕的qsort实现是一个bug，需要修复。 - user25148
1
@Lars：我只是举了一个例子，展示了glibc的qsort 曾经以你认为虚构的方式实现，这给某些人带来了实际的麻烦。当然，它已经被修正了。 - Nordic Mainframe
+1 这是一个很好的回答。实际上，它与 AndreyT 的观点相似，只不过 Luther 没有超过 30K 的声望值。 - user195488
显示剩余5条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接