求一个算法设数组A[1..2n]中存放有n个负数和n个正数,且随机存放.现要求按负数正数相间存放.请写出实现此要求的算法.算法要求:不能使用额外的存储空间,但可使用少量工作单元,算法的时间

Question

求一个算法
设数组A[1..2n]中存放有n个负数和n 个正数,且随机存放.现要求按负数正数相间存放.请写出实现此要求的算法.算法要求:不能使用额外的存储空间,但可使用少量工作单元,算法的时间复杂度应为O(n).

Answer 1

相间存放,说明如果所有负数在奇数位置上,则所有正数在偶数位置上,反之亦然.假设把所有负数都放奇数位置上,所有正数都放偶数位置上,则A[0],A[2],...,A[2n-2]位置应该都存放负数,A[1],A[3],...,A[2n-1]位置上应该存放正数.可以设计两个索引forward和back,初始分别执行第一个位置和最后一个位置,forward每次都递增2,back每次都递减2,直到forward所指位置的元素为正数,back所指元素为负数,然后交换forward和back所指元素.一直到遍历完数组中的所有元素.
参考程序：
void arrange(int a[],int n)
{
int forwad,back;
forward = 0;
back = 2*n-1;
while(forward < 2*n - 1 && back > 0)
{
while(forward < 2*n - 1 && a[forward] < 0)
forward += 2;
while(back > 0 && a[back] > 0)
back -= 2;
if(back > 0)
{
int temp;
temp = a[forward];
a[forward] = a[back];
a[back] = temp;
}
}
}