在Burst sort论文作者声称 Quicksort 不是缓存效率很高的排序算法。正如作者所说
However, some of the disadvantages of Quicksort are still present.Each character is inspected multiple times, until it is in an equal to pivot partition.Each string is re-accessed each time a character in it is inspected, and after the first partitioning these accesses are effectively random. For a large set of strings, the rate of cache misses is likely to be high.
我还找到了ppt其中说快速排序和归并排序是缓存 Oblivious 算法，但维基百科和 few paper声称快速排序的缓存效率很高。
除了整数数据的强制未命中之外，我无法理解快速排序导致缓存未命中的情况。谁能详细解释一下快速排序缓存未命中的情况？
最佳答案
你引用的这段话主要是讲字符串排序时的问题。如果在快速排序期间将字符串数组存储为数组作为指针(这基本上是唯一简单的方法)，那么在快速排序的第一遍之后，存储在数组附近位置的指针可能会指向内存相距很远的位置，即使原始字符串数组是在连续内存中分配的。似乎可以将排序字符串视为一个特殊问题，并且针对它的专门算法可以提高缓存效率。
如果相反，您正在对整数数组进行排序，那么您实际上是在快速排序期间比较和交换数组中的数据，因此当您访问数组中附近的位置时，您将获得缓存优势。在这种情况下，我的理解与您在维基百科和其他地方找到的相同，即快速排序相当缓存高效。基本上这是因为快速排序的每一遍都以高度本地化的方式处理它的数组部分。
关于algorithm - Quicksort 的缓存遗忘程度如何？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34659294/