緩存遺漏快速排序的方式是什麼？

Question

在Burst sort論文作者聲稱快速排序並不是非常緩存高效的排序算法。正如作者提到

然而，一些快速排序的缺點仍然present.Each字符被檢查多次，直到其處於等於 樞軸partition.Each串每次在字符重新訪問它檢查 ，並在第一次分區後，這些訪問是 有效的隨機。對於一大組字符串，高速緩存的速率可能很高。

我還發現ppt它說快速排序和歸併排序是緩存不經意算法，但維基百科和few paper聲稱，快速排序是非常高效的高速緩存。

我不能理解快速排序獲取緩存錯過除了強制錯過整數數據的情況。任何人都可以解釋快速排序緩存未命中詳細？

Answer 1

您引用的段落主要討論排序字符串時的問題。如果快排中的字符串數組作爲指針存儲爲數組（這基本上是唯一的簡單方法），那麼在第一次快排後，存儲在數組附近位置的指針可能會指向內存即使原始字符串數組分配在連續內存中，也是相距甚遠的位置。看起來似乎合理的是，排序字符串可以被視爲一個特殊的問題，專門的算法可能會更有效地緩存。

如果您正在對一個數組（例如整數）進行排序，那麼您實際上是在快速排序時比較和交換數組中的數據，因此當您訪問數組中的附近位置時，您將獲得緩存優勢。在這種情況下，我的理解與您在維基百科和其他地方找到的理解相同，即quicksort相當緩存高效。基本上這是因爲每次快速排序都以高度局部的方式處理陣列的一部分。