问题：将一个长度为n的数组中的元素右移k个位置。例如当n=5, k=3时：[1, 2, 3, 4, 5] => [3, 4, 5, 1, 2]。

要求O(1)的空间复杂度。

最容易实现的方法，性能也比较稳定。设数组共有n个元素:

[a(0), a(1), ..., a(n-k), a(n-k+1), ..., a(n-1)]

先将整个数组反转:

[a(n-1), ..., a(n-k+1), a(n-k), ..., a(1), a(0)]

再将a[n-k, n-1]和a[0, n-k-1]分别反转(注意中间的分隔线):

[a(n-k, a(n-k+1), ..., a(n-1) | a(0), a(1), ..., a(n-k-1)]

这就得到了我们想要的结果。反转的过程，可以通过不断swap两端的两个元素来实现。

数据量大时，最快的方法，最能有效利用缓存。

原理如下，设a[0, n-k-1]为a，a[n-k, n-1]为b，原本的数组可以写成a b，可见我们只要想办法将a与b互换即可，最后结果应该是b a。假定b比a要长，将b分为b_l和b_r两段，令b_r与a的长度相同，原数组可写为a b_l b_r，最后结果应该是b_l b_r a。将a与b_r互换，得到b_r b_l a，可见a的位置已然正确，因此接下来我们只要想办法将b_r和b_l互换即可，问题成功转化为一个较小的问题。最后，当b_l与b_r长度相等时，可以直接互换，算法结束，我们得到了最终结果。

见编程珠玑第14页。由于不能很好地利用缓存，性能最差。