块交换算法

在计算机算法中，块交换算法交换一个数组中的两个元素区域。交换一个数组中大小相等的两个不重叠的区域很简单。然而，要将一个数组中的两个不重叠的区域原地互换，而这两个区域彼此相邻，但大小不等（这种互换相当于阵列旋转），则不简单。目前已知有三种算法可以完成这个任务。Bentley’sJuggling（也被称为Dolphin算法），Gries-Mills和Reversal。这三种算法都是线性时间O(n)，（见时间复杂度）。

反转算法是最简单的解释，使用旋转。旋转是数组元素的就地反转。这种方法将数组中的两个元素从外面换到一个范围内。旋转对偶数或奇数的数组元素都有效。反转算法使用三个就地旋转来完成一个就地块的互换。

旋转区域ABGries-Mills和Reversal算法比Bentley的Juggling表现得更好，因为它们对缓存友好的内存访问模式行为。Reversal算法的并行性很好，因为旋转可以被分割成子区域，这些子区域可以独立于其他区域进行旋转。