rac*_*uzu 7 sorting quicksort localityofreference
分区功能是否可以快速排序其参考位置？如果有,怎么样？
我的意思是,在快速排序中,与其他算法(如合并排序或堆排序)相比,它的位置是什么？
我也看了
"快速排序中的分区步骤通常具有出色的局部性,因为它可以访问前后靠近的连续数组元素".
我不明白 ？
tem*_*def 10
通常,代码具有良好的引用局部性,如果存储器访问它使得倾向于顺序地位于少量存储器区域周围.例如,对数组的线性搜索具有很大的引用局部性,因为所有元素在内存中看起来都相邻,但链接列表上的线性搜索具有较差的局部性,因为链表单元格不一定连续出现在内存中.
我们来看看quicksort.快速排序算法的"肉"是分区步骤,其中元素围绕枢轴重新排列.实现分区算法有几种策略,其中大多数都具有出色的局部性.一种常见的方法是通过从阵列的末端向中心向内扫描,每当它们相对不合适时交换元件.该算法将大多数数组访问限制在两个区域 - 数组的末端 - 并按顺序访问元素,因此它具有很好的局部性.
另一种分区策略通过从数组的左侧向右扫描来工作,存储两个指针,这些指针限定了包含较小值和较大值的区域.同样,数组访问都是顺序的,所以本地性非常好.
现在,与heapsort形成鲜明对比.在堆中,堆操作要求您重复比较一个位置的元素与索引是该元素索引的两倍或一半的元素.这意味着数组访问分散在整个数组中而不是顺序访问,因此整体局部性更差.
由于合并步骤的工作原理,Mergesort实际上有一些不错的位置.但是,因为它维护了一个与输入数组一样大的辅助缓冲区数组,所以它必须支付额外内存的成本,因此它的访问比quicksort的访问更加分散.