算法1

(临时数组)

首先最容易想到的是申请一个同样大小的临时数组，把原数组的值放到临时数组中，奇数放前面，偶数从后面放。

Java 代码

class Solution {
    public int[] exchange(int[] nums) {
        if (nums == null || nums.length == 0) return nums;
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        int tmp[] = new int[n];
        for (int i = 0; i < n; ++i) {
            if ((nums[i] & 1) == 0) {
                // 偶数从后面放
                tmp[right--] = nums[i];
            }
            else {
                // 奇数从前面放
                tmp[left++] = nums[i];
            }
        } 
        return tmp;
    }
}

算法2

(双指针)

我们可以使用两个指针$left$和$right$。$left$从左边开始扫描，如果是奇数就往右走，如果是遇到偶数就停下来（此时$left$指向的是偶数），$right$从右边开始扫描，如果是偶数就往左走，如果是奇数就停下来（此时$right$指向的是奇数），交换$left$和$right$指向的值。继续循环，直到$left==right$为止。我们就以数组$[3, 2, 4, 9, 5, 8, 1]$为例来画图看一下：

Java 代码

class Solution {
    public int[] exchange(int[] nums) {
        if (nums == null || nums.length == 0) return nums;
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        while (left < right) {
            // 如果是奇数，就往后挪，直到遇到偶数为止
            while (left < right && (nums[left] & 1) == 1) left++;
            // 如果是偶数，就往前挪，直到遇到奇数为止
            while (left < right && (nums[right] & 1) == 0) right--;
            // 交换两个值
            if (left < right) {
                nums[left] ^= nums[right];
                nums[right] ^= nums[left];
                nums[left] ^= nums[right];
            }
        }
        return nums;
    }
}

算法3

(快慢指针)

第三种方式使用的是快慢指针，和上一种解决方式有一点区别，上一种是一前一后扫描。我们这里使用的是快慢指针都是从头开始扫描。我们使用两个指针，一个快指针$fast$，一个慢指针$slow$。慢指针$slow$存放下一个奇数应该存放的位置，快指针$fast$往前搜索奇数，搜索到之后然后就和$slow$指向的值交换，我们还以上面的数据为例画个图来分析下：

Java 代码

class Solution {
    public int[] exchange(int[] nums) {
        if (nums == null || nums.length == 0) return nums;
        int n = nums.length;
        int slow = 0, fast = 0;
        while (fast < n) {
            if ((nums[fast] & 1) == 1) {
                if (slow != fast) {
                    nums[slow] ^= nums[fast];
                    nums[fast] ^= nums[slow];
                    nums[slow] ^= nums[fast];
                }
                slow++;
            }
            fast++;
        }
        return nums;
    }
}