27．（完善程序）

（序列重排）全局数组变量 $a$ 定义如下：

#define SIZE 100 
int a[SIZE],n; 

它记录着一个长度为 $n$ 的序列 $a[1],a[2],...,a[n]$。

现在需要一个函数，以整数 $p（1≤p≤n）$ 为参数，实现如下功能：将序列 $a$ 的前 $p$ 个数与后 $n–p$ 个数对调，且不改变这 $p$ 个数（或 $n–p$ 个数）之间的相对位置。

例如，长度为 $5$ 的序列 $1,2,3,4,5$，当 $p=2$ 时重排结果为 $3,4,5,1,2$。

有一种朴素的算法可以实现这一需求，其时间复杂度为 $O(n)$、空间复杂度为 $O(n)$：

void swap1(int p)
{
  int i,j,b[SIZE];
  for(i=1;i<=p;i++)
    b[____________________]=a[i]; //（2分）
  for(i=p+1;i<=n;i++)
    b[i-p]=a[i];
  for(i=1;i<=n;i++)
    a[i]=b[i];
}

我们也可以用时间换空间，使用时间复杂度为 $O(n^2)$、空间复杂度为 $O(1)$ 的算法：

void swap2(int p)
{
  int i,j,temp;
  for(i=p+1;i<=n;i++){
    temp=a[i];
    for(j=i;j>=____________________;j--) //（2分）
      a[j]=a[j-1];
    ____________________=temp; //（2分）
  }
}

事实上，还有一种更好的算法，时间复杂度为 $O(n)$、空间复杂度为 $O(1)$：

void swap3(int p)
{
  int start1,end1,start2,end2,i,j,temp;
  start1=1;
  end1=p;
  start2=p+1;
  end2=n;
  while(true){
    i=start1;
    j=start2;
    while((i<=end1)&&(j<=end2)){
      temp=a[i];
      a[i]=a[j];
      a[j]=temp;
      i++;
      j++;
    }
    if(i<=end1)
      start1=i;
    else if(____________________){ //（3分）
      start1=____________________//（3分）
      endl=____________________//（3分）
      start2=j;
    }
    else
      break;
  }
}

①：{{ input(1) }}

②：{{ input(2) }}

③：{{ input(3) }}

④：{{ input(4) }}

⑤：{{ input(5) }}

⑥：{{ input(6) }}