思路：

1. 开辟新数组保存法：创建两个数组，一个用来存奇数，一个用来存偶数，最后合并。

2. 不开辟新数组：

   • 1.用两个下标i,j进行遍历;
   • 2.当i走到偶数时停下，并让j从i的后一个元素开始遍历；(若i走到队尾则循环结束)
   • 3.若j所指的是偶数则继续前进，j遇到奇数则停下(如果j都没遇到奇数则在队尾停下，结束。)。
   • 4.此时j所指的是奇数，i所指的是偶数(i到j-1都是偶数)。
   • 5.则可以用临时变量temp保存j对应的值，然后从j-1开始到i，挨个后移一位。
   • 6.将temp保存的值插入到i的位置。

3. 优化：冒泡排序也可以保证相对位置不变，所以用冒泡排序写起来会更方便。

   答案：

4. 不开辟新数组：

   public class Solution {
     public void reOrderArray(int[] array) {
         int len = array.length;
         if (len <= 1) {
             return;
         }
         int i = 0;
         while (i < len) {
             //如果i所指的元素是奇数，则继续前进
             if (array[i] % 2 == 1) {
                 i++;
             } else {
                 //当i遇到偶数停下时，j从i的后一位开始走
                 int j = i + 1;
                 //当j所指的元素也是偶数时，则j向后移动
                 while (array[j] % 2 == 0) {
                     //当j移到队尾，则说明i到队尾全是偶数，已满足题目的奇偶分离要求
                     if (j == len - 1) {
                         return;
                     }
                     j++;
                 }
                 //此时j为奇数，i为偶数，用temp保存array[j]的值
                 int temp = array[j];
                 //把i到j-1的元素往后移一位
                 while (j > i) {
                     array[j] = array[j - 1];
                     j--;
                 }
                 //把保存在temp中的原第j个元素的值赋给i，此时i就变成奇数了，并进入下个循环
                 array[i] = temp;
             }
   
         }
     }
   }