(序列重排)全局数组变量 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) { int i, j, b[SIZE]; for (i = 1; i <= p; i++) b[ (1) ] = 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 >= (2) ; j--) // ( 2 分 ) a[j] = a[j - 1]; _____(3) = 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 ( (4) ) { // ( 3 分 ) start1 = (5) ; // ( 3 分 ) end1 = (6) ; // ( 3 分 ) start2 = j; } else break; } }