问答题
已知数组A[1..n]的元素类型为整型int，设计一个时间和空间上尽可能高效的算法，将其调整为左右两部分，左边所有元素为负整数，右边所有元素为正整数。不要求对这些元素排序。
问答题
给出算法的基本设计思想；
【正确答案】算法的基本设计思想如[解析]所述。
【答案解析】
问答题
根据设计思想，采用C或C++或Java语言表述算法，关键之处给出注释；
【正确答案】用C语言算法描述如下：
void Adjust(int A[]){
//调整数组A，使得A的左边为负整数，右边为正整数
void Adjust(int A[]){ //调整数组A，使得A的左边为负整数，右边为正整数
int i=1, j=n, temp;
while(i＜j){
while(A[i]＜0 && i＜j) i++; //A[i]为负整数时，i增1
while(A[j]＞0 && i＜j) j- -; //A[j]为正整数时，j减1
if(i＜j){
temp=A[i]; A[i]=A[j]; A[j]=temp; //A[i]为正整数、A[j]为负整数时，交换
i++;
j- -;
}
}
}
【答案解析】
问答题
说明你所设计算法的时间复杂度和空间复杂度。
【正确答案】算法的时间复杂度为O(n)；算法的空间复杂度为O(1)。
【答案解析】[解析] 本题主要考查线性表的顺序存储结构(这里为数组)的应用。算法的基本设计思想是先设置好上、下界和轴值，然后分别从数组前端查找正整数和从数组末端查找负整数，找到后进行交换，直到上、下界相遇。
具体做法是：设置两个指示器i和j，其中i=1，j=n；当A[i]为正整数，A[j]为负整数时，A[i]和A[j]交换；否则，A[i]为负整数时，则i++；A[j]为正整数时，则j-。这样，可使算法的时间复杂度为O(n)。