给定一个数组，数组全都是正整数，写一个函数，使得这个数组的所有奇数排列到偶数的前面，且奇数之间的相对位置不变，偶数之间的相对位置也不变

需要O(N)空间的方法不再赘述

• 思路1
  冒泡，冒泡，冒泡 冒泡的思想是i和i+1的元素进行比较,O(N2)

  public void reOrder(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if ((nums[j] % 2 == 0) && (nums[j + 1] % 2 == 1)) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }

• 思路2
  类似快排的方法，但是完全用快排，数字之间的相对位置会发生改变，所以要进行一些改动
  参考链接

public void reOrder2(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return;
        }
        int i = 0;
        while (i < n) {
            int j = i + 1;
            if (nums[i] % 2 == 0) {
                while (nums[j] % 2 == 0) {
                    if (j == n - 1) {
                        return;
                    }
                    j++;
                }

                //此时j为奇数
                int cnt = j - i;
                int tmp = nums[i];
                nums[i] = nums[j];
                while (cnt > 1) {
                    nums[i + cnt] = nums[i + cnt - 1];//数组后移
                    cnt--;
                }
                nums[i + 1] = tmp;
            }
            i++;
        }
    }

思路2的别的写法，原理类似（自己写出来的）

public void reOrderArray(int[] nums) {
        int start = -1;
        int i = 0;
        for (i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 1) {
                continue;
            }

            if (start < 0) {
                start = i;
                break;
            }
        }
        while (i < nums.length) {
            while ((i < nums.length) && (nums[i] % 2 == 0)) {
                i++;
            }

            if (i >= nums.length) {
                continue;
            }

            for (int j = i; j > start; j--) {
                swap(nums, j, j - 1);
            }
            start++;
        }
    }

例子：

image.png