题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序。

使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

样例

输入：[1,2,3,4,5]

输出: [1,3,5,2,4]

算法1

分析：

按照y总的归并排序写的，就是这个偶数的排列顺序不一样，但是可以AC，y总可以加强一下数据

C++ 代码

class Solution {
public:
    void merge(vector<int> &nums, int l, int r)
    {
        if(l >= r) return ;
        int mid = l + r >> 1;
        merge(nums, l, mid), merge(nums, mid + 1, r);
        vector<int> tmp;
        int i = l, j = mid + 1;
        while(i <= mid && j <= r)
        {
            if(nums[i] % 2 != 0) tmp.push_back(nums[i++]);
            else tmp.push_back(nums[j++]);
        }
        while(i <= mid) tmp.push_back(nums[i++]);
        while(j <= r) tmp.push_back(nums[j++]);
        for(int i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];
    }
    void reOrderArray(vector<int> &nums) {
        if(nums.empty()) return;
        int n = nums.size();
        merge(nums, 0, n - 1);
    }
};