关于java:字节算法题正负数相互间隔

一道字节算法题

• 链接：算法连贯
• 起源：牛客网
• 把数组元素依照正负序重排列
• 给定一个数组，数组它依照上面的规定重排列后的数组： 1. 数组中的正负数互相距离 2. 符号雷同的数字绝对程序不变 3. 如果某种符号的数字多余，放到数组最初
• 例如：-1,3,2,4,5,-6,7,-9
• 重排列后：3,-1,2,-6,4,-9,5,7
• 空间复杂度要求O(1)

解决思路：
既然要求空间复杂度为为O(1)级别那只能用双指针进行排序了。
咱们遍历数组，交替的地寻找下一个负数/正数,记该数地位为j,将它插入到数组的以后地位i，并把数组[i~j]的元素往后移即可。

public void sortPosAndNeg(int[] array){
    //正负数索引地位
    int pos = 0, neg = 0;
    //用flag来标记以后要插入的是负数还是正数
    boolean flag = true;
    for (int i = 0; i < array.length; i++) {
        if (flag){
            //从数组以后地位开始查找下一个负数
            pos = i;
            while (pos < array.length && array[pos] < 0){
                pos++;
            }
            //找不到下一个负数，阐明排序完了
            if (pos >= array.length) break;
            //后移，先取出要插入的数 
            int res = array[pos];
            for (int j = pos; j > i; j--) {
                array[j] = array[j-1];
            }
            array[i] = res;
            flag = false;
        }else {
            neg = i;
            while (neg < array.length && array[neg] > 0){
                neg++;
            }
            if (neg >= array.length) break;
            //后移
            int res = array[neg];
            for (int j = neg; j > i; j--) {
                array[j] = array[j-1];
            }
            array[i] = res;
            flag = true;
        }
    }
}