爲什麼JDK的quicksort實現會導致堆棧溢出？

Question

我看到演示文稿中的其他日子，說話者曾使用過麥克羅伊的紙A Killer Adversary for Quicksort概述的技術來生成原始類型的輸入Arrays.sort會觸發爲O（n ）行爲。該順序導致數據透視選擇始終僅將數組大小減少一個常量，這導致Java Arrays.sort函數導致堆棧溢出。

根據the source files from the JDK，Arrays.sort1快速排序實現函數沒有防範來防止堆棧溢出。通過使排序例程不會觸發兩個遞歸調用，而是使用while循環爲當前較大的子數組重新使用當前堆棧幀並且僅遞歸一次（在較小的子數組上）時，始終可以使quicksort從不堆棧溢出。這會導致性能下降最小，並且不可能導致任何合理大小的輸入的堆棧溢出，因爲在大小爲n的輸入上堆棧深度絕不會超過O（log n）堆棧幀。作者還可以使用introsort算法，該算法修改快速排序以在快速排序遞歸深度超過某個限制時切換到最壞情況O（n log n）排序算法，以防止這種情況。

Arrays.sort的作者沒有任何理由不選擇這樣做？這看起來像是一個嚴重的問題，內置的排序算法會導致堆棧溢出，因爲它可以通過觸發重複的堆棧溢出來啓動針對此類系統的DoS攻擊。

Answer 1

爲什麼？因爲解決這個問題將會過度。

所使用的算法在所有情況下都是穩定的，但是在非常特殊的情況下，如果這些情況通常比較可能發生，那麼這種情況將受到外部防範。這就是爲什麼他們有API文檔來定義在幕後使用的算法。所以你可以抵禦它。

中斷提供的算法的特定順序的機率非常小。

我想如果你仔細觀察，會有數據集導致幾乎所有的標準JVM結構中斷。 防禦它們的成本是多少，並且是由於防禦措施而付出的努力的成本以及算法不可避免的退化。