sorting - 分区函数是否可以快速排序其参考位置？

Question

分区函数是否可以快速排序其参考位置？如果有，怎么做？

我的意思是，与其他算法（如合并排序或堆排序）相比，快速排序中有什么可以提供参考的局部性？

我也读过

“快速排序中的分区步骤通常具有极好的局部性，因为它访问前后附近的连续数组元素”。

我不明白 ？

Answer 1

一般来说，如果代码访问的内存倾向于顺序位于少量内存区域周围，则代码具有良好的引用局部性。例如，对数组的线性搜索具有很大的引用局部性，因为所有元素在内存中都出现相邻，但对链表的线性搜索具有较差的局部性，因为链表单元不一定连续出现在内存中。

让我们看一下快速排序。快速排序算法的“关键”是分区步骤，其中元素围绕枢轴重新排列。分区算法的实现有多种策略，其中大部分具有极好的局部性。一种常见的方法是从数组的末端向中心扫描，每当元素相对不合适时交换元素。该算法将大部分数组访问限制在两个区域 - 数组的末端 - 并按顺序访问元素，因此它具有很好的局部性。

另一种分区策略的工作原理是从数组的左侧向右扫描，存储两个指针来分隔保存较小值和较大值的区域。同样，数组访问都是顺序的，所以局部性非常好。

现在，将其与堆排序进行对比。在堆排序中，堆操作要求您重复比较一个位置的元素与索引是该元素索引的两倍或一半的元素。这意味着数组访问分散在整个数组中，而不是顺序访问，因此整体局部性要差得多。

由于合并步骤的工作方式，Mergesort 实际上具有一些不错的局部性。然而，因为它维护一个与输入数组一样大的辅助缓冲区数组，它必须支付额外内存的成本，因此它的访问比快速排序的访问更加分散。

Answer 2

“参考位置”是指频繁访问的内存（时间位置）或连续的内存位置（空间位置），如数组。基本上，这意味着机器（更具体地说，缓存内存）发现访问这些内存位置更容易，因此也更快。

考虑归并排序算法。
它首先（实际上）将数组分成两半，直到最小单位，即奇异元素（拆分函数）。然后它一次比较两个数组并以排序方式合并它们（合并函数）。考虑一个样本合并 b/w 两个长度为n的数组，例如 arr[0]...arr[n-1] 和 arr[n]...arr[2n-1]。处理器必须获取两个数组的第一个元素，即 arr[0] 和 arr[n]。由于它们没有本地化，因此效率会降低。

将此与快速排序算法进行比较。分区
函数 中的每个比较都发生在相邻的即局部内存位置之间，因此它将是缓存有效的。

希望这可以帮助！