设将n(n>1) 个整数存放到一维数组 R 中。试设计一个在时间和空间两方面都尽可能高效的算法。将 R 中保存的序列循环左移p(0<p<N) 个位置，即将 R 中的数据由<x0,x1,⋯,xn−1>变换为<xp,xp+1,⋯,xn−1,x0,x1,⋯,xp−1>。要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 或 Java 语言描述，关键之处给出注释。

(3) 说明你所设计算法的时间复杂度和空间复杂度。

顺序表

[tag_link]

1）算法的基本设计思想可以将这个问题视为把数组ab转换成数组ba（a代表数组的前p个元素，b代表数组中余下的n−p个元素），先将a逆置得到a−1b, 再将b逆置得到a−1b−1，最后将整个a−1b−1逆置得到(a−1b−1)−1=ba。设 Reverse 函数执行将数组元素逆置的操作，对 abcdefgh 向左循环移动 3(p=3) 个位置的过程如下：Reverse(0,p-1) 得到 cbadefgh:Reverse(p,n-l) 得到 cbahgfed;Reverse(0,n-l) 得到 defghabc,注：Reverse 中，两个参数分别表示数组中待转换元素的始末位置。

2）使用 C 语言描述算法如下：

void reverse(int a[], int from, int to) {
  int i = from;
  int j = to;
  while (i < j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
    i++;
    j--;
  }
}

void loopMove(int a[], int n, int p) {
  if (p < 0) {
    return;
  }
  p = p % n;
  reverse(a, 0, p-1);
  reverse(a, p, n-1);
  reverse(a, 0, n-1);
}

3）上述算法中 3 个 Reverse 函数的时间复杂度分别为O(p/2)、O((n−p)/2)和O(n/2)，故所设计的算法的时间复杂度为O(n)，空间复杂度为O(1)。【另解】借助辅助数组来实现。算法思想：创建大小为p的辅助数组S，将R中前p个整数依次暂存在S中，同时将R中后p个整数左移，然后将S中暂存的p个数依次放回到R中的后续单元。时间复杂度为O(n), 空间复杂度为O(p)。