arrays - 先排列奇数，再排列偶数。奇偶顺序不应该改变

Question

下面是代码片段，用于在不改变原始数组中偶数/奇数顺序的情况下，对奇数和偶数重新排序。

输入 - {1, 4, 8, 3, 9, 12, 7} 输出 - {1, 3, 9, 7, 4, 8, 12}

我们能否在空间上从 O(n2) 改进它(不使用额外空间)？

public  static void reOrder(int[] arr) {
     int evenIndex  = arr.length;
     for(int i=0; i < arr.length;i++) {
            if(arr[i] % 2 == 0 && evenIndex == arr.length) //even index
                evenIndex = i;

            else if( arr[i] % 2 != 0 ) {
                if(i > evenIndex ) {
                    shift (arr, evenIndex , i);
                    evenIndex ++;
                }
            }
     }
}

static void shift(int[] arr, int evenIndex, int endIndex) {
    int temp = arr[endIndex];
    for(int i = endIndex; i > evenIndex ;i --) {
        arr[i] = arr[i-1];
    }
    arr[evenIndex] = temp;
}

Answer 1

稳定的分区就是你要找的

std::vector<int> l = {1, 4, 8, 3, 9, 12, 7};
std::stable_partition(l.begin(), l.end(),
                      [](int A) -> bool {
                          return (A & 1) == 1; // A is odd
                      });

Exactly N applications of the predicate and O(N) swaps if there is enough extra memory. O(N log N) swaps and O(N) applications of the predicate

Question on how stable partition works along with its complexity.

例如，稳定的快速排序将在底层使用稳定的分区。查看已接受的答案 here用于复杂递归的稳定分区算法的 O(n*log(n)) 实现。