我已经看到很多地方都说quicksort很好，因为它适合与缓存相关的内容，例如Wiki中所述
此外，quicksort的顺序和本地化内存引用可与缓存配合使用
http://en.wikipedia.org/wiki/Quicksort
谁能给我一些有关此主张的见解？quicksort与缓存有何关系？通常，该语句中的缓存意味着什么？为什么快速排序更适合缓存？
谢谢
quicksort将数组更改为原位-在数组中进行处理（例如，与合并排序不同- 会为其创建另一个数组）。因此，它采用了引用局部性原则。
高速缓存受益于对内存中同一位置的多次访问，因为只有第一个访问实际上需要从内存中获取-其余的访问都是从高速缓存中获取的，这比对内存的访问要快得多。
例如，合并排序-需要更多的内存[RAM]访问-因为您创建的每个附件阵列-都在再次访问RAM。
树甚至更糟-因为树中的2个顺序访问不太可能彼此接近。[缓存填充在块中，因此对于顺序访问-块中只有第一个字节是“未命中”，其他字节是“命中”]。
