交错正负数
给出一个含有正整数和负整数的数组，重新排列成一个正负数交错的数组。
注意事项
不需要保持正整数或者负整数原来的顺序。
样例
给出数组[-1, -2, -3, 4, 5, 6]，重新排序之后，变成[-1, 5, -2, 4, -3, 6]或者其他任何满足要求的答案
挑战
原地完成，没有额外的空间
解题
1.快速排序
2.定义新数组，交叉选取正负数放到新数组
class Solution {
/**
* @param A: An integer array.
* @return: void
*/
public void rerange(int[] A) {
// write your code here
if(A == null ||A.length == 0)
return;
int low = 0;
int high = A.length - 1;
while(low < high){
// 负数放前
if( low < high && A[low] <0 )
low+=1;
// 正数放后
if( low < high && A[high] >0 )
high-=1;
if(low < high){
int tmp = A[low];
A[low] = A[high];
A[high] = tmp;
}
}
int flag = 0;
if(A.length -low > low)// 正数大于负数
flag =1;
int m = 0,n = low;
int[] B = new int[A.length];
for(int i = 0;i < B.length;i++){
if( flag==0){
if(i%2==0)
B[i]= A[m++];
else
B[i]= A[n++];
}else{
if(i%2==0)
B[i]= A[n++];
else
B[i]= A[m++];
}
}
for(int i =0;i<A.length;i++)
A[i] = B[i];
}
}