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

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

Const int 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)

{

\tint i, j, b[SIZE];

\tfor (i = 1; i <= p; i )

\t\tb[ ( 1) ] = a[i]; //（2 分）

\tfor (i = p 1; i <= n; i )

\t\tb[i - p] = a[i];

\tfor (i = 1; i <= n; i )

\t\ta[i] = b[i];

}

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

void swap2(int p)

{

\tint i, j, temp;

\tfor (i = p 1; i <= n; i ) {

\t\ttemp = a[i];

\tfor (j = i; j >= (2) ; j--) //（2 分）

\t\ta[j] = a[j - 1];

(3) = temp; //（2 分）

\t}

}

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

void swap3(int p)

{

\tint start1, end1, start2, end2, i, j, temp;

\tstart1 = 1;

\tend1 = p;

\tstart2 = p 1;

\tend2 = n;

\twhile (true) {

\t\ti = start1;

\t\tj = start2;

\twhile ((i <= end1) && (j <= end2)) {

\t\ttemp = a[i];

\t\ta[i] = a[j];

\t\ta[j] = temp;

\t\ti ;

\t\tj ;

\t}

\tif (i <= end1)

\t\tstart1 = i;

\telse if ( (4) ) { //（3 分）

\t\tstart1 = (5) //（3 分）

\t\tendl = (6) //（3 分）

\t\tstart2 = j;

\t}

\telse

\t\tbreak;

\t}

}