给出一个含有正整数和负整数的数组，重新排列成一个正负数交错的数组。

 注意事项

不需要保持正整数或者负整数原来的顺序。

样例

给出数组[-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