如何缓存忘记Quicksort？

在Burst排序论文中,作者声称Quicksort并不是非常高效的排序算法.正如作者所说

但是,Quicksort的一些缺点仍然存在.每个字符都被多次检查,直到它等于pivot分区.每次检查一个字符时,每次查找字符串,并在第一次分区后重新访问这些字符串.访问实际上是随机的.对于大量字符串,缓存未命中率可能很高.

我还发现ppt说快速排序和合并排序是缓存Oblivious算法,但维基百科和少数论文声称快速排序非常高效缓存.

我无法理解除了整数数据的强制错过之外快速排序缓存错过的情况.任何人都可以详细解释快速排序缓存未命中？

您引用的段落主要是在排序字符串时讨论问题.如果快速排序期间的字符串数组作为指针存储为数组(这基本上是唯一简单的方法),那么在快速排序的第一次传递之后,存储在数组中附近位置的指针可能指向内存相距很远的位置,即使原始的字符串数组是在连续的内存中分配的.似乎有理由认为排序字符串可以被视为一个特殊问题,并且专门的算法可以提高缓存效率.

相反,如果您正在排序一个数组,比如整数,那么您实际上是在快速排序期间比较和交换数组中的数据,因此当您访问数组中的附近位置时,您将获得缓存优势.在这种情况下,我的理解与你在维基百科和其他地方发现的相同,即quicksort相当缓存效率.基本上这是因为quicksort的每次传递都以高度本地的方式处理其部分数组.