Q

qsort使用堆內存嗎？

2013-07-23 110 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

相關問題