qsort是否使用堆内存？

Question

在VS2008中使用qsort()的stdlib实现。

qsort()的这个实现是否使用堆上的内存？或者只使用基于堆栈的内存？

Answer 1

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

Answer 2

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

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

Answer 3

如您所见，here和here根本不在堆上分配内存。