C语言实现数组元素循环右移

试设计一个算法，将数组 A n A_n An​中的元素全部循环向右移动k位，并要求只用一个元素大小的附加存储，元素移动或者交换次数为 O ( n ) O(n) O(n)。

将数组分为两部分，前n-k个元素和后k个元素，分别将这两部分反转，然后再将整个数组反转。这样可以实现循环右移的效果，而且不需要使用递归。

首先我们来看优化算法的实现过程： 首先对k进行取模，以处理k大于n的情况。 然后反转前n-k个元素，将前n-k个元素从[0, n-k-1]反转为[n-k-1, 0]，此时数组变为了[An-k, An-k+1, …, An-1, A0, A1, …, An-k-1]。 接着反转后k个元素，将后k个元素从[n-k, n-1]反转为[n-1, n-k]，此时数组变为了[An-k, An-k+1, …, An-1, An-k, An-k+1, …, An-1-k]。 最后反转整个数组，将整个数组从[0, n-1]反转为[n-1, 0]，此时数组变为了[An-k, An-k+1, …, An-1-k, A0, A1, …, An-k-1]，即将所有元素循环右移了k位。

接下来我们用数学方法来分析为什么这样可以。 设原数组为A，将A循环右移k位后得到的新数组为B。 根据循环右移的定义，可以将B表示为： B[i] = A[(i+k) mod n] (0 1, 2, 3, 4, 5}; MoveRight(a, 5, 3); for (int i = 0; i while (start k %= n; reverse(a, 0, n - k - 1); reverse(a, n - k, n - 1); reverse(a, 0, n - 1); }