关于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;
        }
    }
}