Q

qsort使用堆内存吗？

2013-07-23 65 views 1 likes

1

在VS2008中使用stdlib实现qsort()。qsort使用堆内存吗？

qsort()的这个实现是否在堆上使用了内存？还是仅使用基于堆栈的内存？

2013-07-23 Nicholas

+2

'std :: sort（）'有什么问题？ – jxh

+0

也没关系。问题仍然存在。我不需要快速排序，只需要一个不使用堆内存的排序。 – Nicholas

+1

为防万一您不知道，VC++附带了运行时库的源代码（大部分浮点例程除外），但您可能需要在安装/重新安装过程中检查某些方框以获取它。如果你想知道实施的细节，你通常可以很容易地找到答案。 –

A

回答

6

快速排序是一种现场排序算法。除了递归调用的运行时栈上的空间外，它不使用任何内存。

2013-07-23 00:13:15 user515430

+0

请记住，'qsort（）'不需要使用Quicksort算法 - 尽管我认为大多数使用它的一些变体。（例如，glibc的文档提到：“此库中qsort的实现可能不是就地排序并可能因此使用额外的内存来存储阵列”） –

1

正如你所看到的here和here它根本没有在堆上分配内存。

2013-07-23 00:18:34

+2

链接到其他两个实现不会回答此问题关于VC++实现的问题.. – Blastfurnace

2

它使用什么，它没有使用的是实现细节。该语言的规范不提供任何回答这个问题。

但是可以说的是，有没有理由为合理的qsort实现使用动态内存。在qsort中正确实施的递归计划永远不会要求递归深度大于给定平台上最大数组大小的log2。这意味着，例如，在平面存储器平台上，递归深度不会超过平台的“位数”（例如，它在32位平台上不超过32位）。这又意味着qsort很容易允许完全基于堆栈的实现。

2013-07-23 01:27:40 AnT

相关问题