本质上是一个01排序问题，要求稳定

  1. 对稳定性有要求，所以不能用与快排、荷兰国旗类似的实现方法
  2. 考虑哪些排序算法是稳定的：冒泡、插入、归并；

  • 冒泡：偶数下沉，奇数上升；每次遍历时，如果奇数在偶数后面，就交换两个数。时间复杂度O(n^2)

  • 插入：遇到奇数判断左边有多少偶数，将所有偶数往后移动一位，将奇数插入前面多出的空位；或者遇到偶数判断右边有多少奇数，将所有奇数往前移动一位，将偶数插入后面多出的空位。

  • 归并：对于每个分组按照奇前偶后排列，每个分组用一个额外数组进行归并操作；用递归实现
    代码是冒泡思想实现的：

    public class Solution {
  public void reOrderArray(int [] array) {
      int len = array.length;
      int temp,i,j;
      for(i=0;i<len-1;i++){
          for(j=0;j<len-i-1;j++){
              if((array[j]&1)==0 && (array[j+1]&1)==1){
                  temp=array[j];
                  array[j]=array[j+1];
                  array[j+1]=temp;
              }

          }
      }
  }
}
​​

欢迎指正~