输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

 

示例：

输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。  

---

一趟遍历划分

借用快速排序划分的思想，将数组分为两个部分

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        // index记录新奇数可以存放的第一个位置
        int index = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] & 1 == 1) {
                swap(nums[index++], nums[i]);
            }
        }
        return nums;
    }
};