分区函数是否可以快速排序其参考位置？
Does partition function gives quick sort its locality of reference?
分区函数是否提供快速排序其引用位置？
如果有，怎么办？
我的意思是，与其他算法（例如归并排序或堆排序）相比，快速排序有什么特点可以提供参考位置？
我也看过
"The partitioning step in quicksort typically has excellent locality, since it accesses consecutive array elements near the front and the back".
我没听懂？
一般来说，如果代码进行的内存访问往往顺序地位于少量内存区域周围，则代码具有良好的引用局部性。例如，对数组的线性搜索具有很大的引用局部性，因为所有元素在内存中都是相邻的，但是对链表的线性搜索具有较差的局部性，因为链表单元格不一定在内存中连续出现。
让我们来看看快速排序。快速排序算法的 "meat" 是分区步骤，其中元素围绕一个枢轴重新排列。有几种实现分区算法的策略，其中大多数具有出色的局部性。一种常见的方法是从阵列的末端向内扫描到中心，只要元素相对不合适就交换它们。该算法将大部分数组访问限制在两个区域 - 数组的末端 - 并顺序访问元素，因此具有很大的局部性。
另一种分区策略的工作原理是从数组的左侧向右侧扫描，存储两个指针，这两个指针分隔包含较小值和较大值的区域。同样，数组访问都是顺序的，因此局部性非常好。
现在，将其与堆排序进行对比。在堆排序中，堆操作要求您反复比较一个位置的元素与索引是该元素索引两倍或一半的元素。这意味着数组访问是分散在整个数组而不是顺序的，所以整体局部性要差很多。
归因于合并步骤的工作方式，Mergesort 实际上具有相当不错的局部性。但是，因为它维护了一个和输入数组一样大的辅助缓冲区数组，它必须付出额外的内存成本，因此它的访问比快速排序的访问更分散。
'Locality of reference' 是指频繁访问的内存（时间 局部性）或连续的内存位置（空间 局部性），如数组。基本上，这意味着机器（更具体地说，缓存内存）发现访问这些内存位置更容易，因此更快。
考虑归并排序算法。
它首先（实际上）将数组分成两半，直到最小单元，即单个元素（split 函数）。然后它一次比较两个数组并以排序的方式合并它们（merge 函数）。考虑一个示例合并 b/w 两个长度为 n 的数组，比如 arr[0]...arr[n-1] 和 arr[n]...arr[ 2n-1]。处理器必须获取两个数组的第一个元素，即 arr[0] 和 arr[n]。由于它们不是本地化，因此效率会降低。
将此与 快速排序 算法进行比较。
partition 函数中的每个比较都在相邻的即 localized 内存位置之间进行，因此它将是缓存高效的。
希望对您有所帮助！
分区函数是否提供快速排序其引用位置？ 如果有，怎么办？
我的意思是，与其他算法（例如归并排序或堆排序）相比，快速排序有什么特点可以提供参考位置？
我也看过
"The partitioning step in quicksort typically has excellent locality, since it accesses consecutive array elements near the front and the back".
我没听懂？
一般来说，如果代码进行的内存访问往往顺序地位于少量内存区域周围，则代码具有良好的引用局部性。例如，对数组的线性搜索具有很大的引用局部性，因为所有元素在内存中都是相邻的，但是对链表的线性搜索具有较差的局部性，因为链表单元格不一定在内存中连续出现。
让我们来看看快速排序。快速排序算法的 "meat" 是分区步骤，其中元素围绕一个枢轴重新排列。有几种实现分区算法的策略，其中大多数具有出色的局部性。一种常见的方法是从阵列的末端向内扫描到中心，只要元素相对不合适就交换它们。该算法将大部分数组访问限制在两个区域 - 数组的末端 - 并顺序访问元素，因此具有很大的局部性。
另一种分区策略的工作原理是从数组的左侧向右侧扫描，存储两个指针，这两个指针分隔包含较小值和较大值的区域。同样，数组访问都是顺序的，因此局部性非常好。
现在，将其与堆排序进行对比。在堆排序中，堆操作要求您反复比较一个位置的元素与索引是该元素索引两倍或一半的元素。这意味着数组访问是分散在整个数组而不是顺序的，所以整体局部性要差很多。
归因于合并步骤的工作方式，Mergesort 实际上具有相当不错的局部性。但是，因为它维护了一个和输入数组一样大的辅助缓冲区数组，它必须付出额外的内存成本，因此它的访问比快速排序的访问更分散。
'Locality of reference' 是指频繁访问的内存（时间 局部性）或连续的内存位置（空间 局部性），如数组。基本上，这意味着机器（更具体地说，缓存内存）发现访问这些内存位置更容易，因此更快。
考虑归并排序算法。
它首先（实际上）将数组分成两半，直到最小单元，即单个元素（split 函数）。然后它一次比较两个数组并以排序的方式合并它们（merge 函数）。考虑一个示例合并 b/w 两个长度为 n 的数组，比如 arr[0]...arr[n-1] 和 arr[n]...arr[ 2n-1]。处理器必须获取两个数组的第一个元素，即 arr[0] 和 arr[n]。由于它们不是本地化，因此效率会降低。
将此与 快速排序 算法进行比较。
partition 函数中的每个比较都在相邻的即 localized 内存位置之间进行，因此它将是缓存高效的。
希望对您有所帮助！