调整数组顺序使奇数位于偶数前面

方式一

类似于冒泡排序法

public class Solution {
  public void reOrderArray(int[] array) {

    if (array == null || array.length < 2) {
      return;
    }

    // 交换标记
    boolean flag = false;
    int lastPos = 0;

    // end 是有序区指示
    for (int end = array.length; end >= 0; end--) {
      for (int i = 0; i < end - 1; i++) {
        if ( (!isOddNumber(array[i])) && isOddNumber(array[i + 1])) {
          swap(i, i + 1, array);
          flag = true;
          // 记录最后的有序区边界
          lastPos = i + 1;
        }
      }
      if (!flag) {
        break;
      }
      flag = false;
      // end-- 会将 end 减少一个
      end = lastPos + 1;
    }
  }

  public static void swap(int indexA, int indexB, int[] arr) {
    arr[indexA] = arr[indexA] ^ arr[indexB];
    arr[indexB] = arr[indexA] ^ arr[indexB];
    arr[indexA] = arr[indexA] ^ arr[indexB];
    return;
  }

  public static boolean isOddNumber(int val) {
    if (val % 2 == 1) {
      return true;
    }
    return false;
  }
}

方法二

类似归并排序，采用递归，待大佬优化

public class Solution {
  public void reOrderArray(int[] array) {

    if (array == null || array.length < 2) {
      return;
    }

    mergeOrder(array, 0, array.length - 1);
  }

  public static void mergeOrder(int[] arr, int L, int R) {
    if (L == R) {
      return;
    }
    int mid = L + ((R - L) >> 1);
    mergeOrder(arr, L, mid);
    mergeOrder(arr, mid + 1, R);
    mergePartitionArr(arr, L, mid, R);
  }

  public static void mergePartitionArr(int[] arr, int L, int mid, int R) {
    int[] helpArr = new int[R - L + 1];
    int pHelpArr = 0;
    int pLeftArr = L;
    int pRightArr = mid + 1;
    // 左边的奇数先放
    while (pLeftArr <= mid && isOddNumber(arr[pLeftArr])) {
      helpArr[pHelpArr++] = arr[pLeftArr++];
    }
    while (pRightArr <= R && isOddNumber(arr[pRightArr])) {
      helpArr[pHelpArr++] = arr[pRightArr++];
    }
    // 左边的偶数先放
    while (pLeftArr <= mid) {
      helpArr[pHelpArr++] = arr[pLeftArr++];
    }
    while (pRightArr <= R) {
      helpArr[pHelpArr++] = arr[pRightArr++];
    }
    for (int i = 0; i < helpArr.length; i++) {
      arr[L + i]  = helpArr[i];
    }
    return;
  }

  public static boolean isOddNumber(int val) {
    if (val % 2 == 1) {
      return true;
    }
    return false;
  }
}