c++ - qsort 是否使用堆内存？

Question

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

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

Answer 1

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

Answer 2

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

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

Answer 3

正如您在此处和此处看到的，它根本不会在堆上分配内存。