调整数组顺序使奇数位于偶数前面

题目

输入一个整数数组，实现一个函数来解决该数组中数字的位置，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

思路

第一个指针pHead 初始化为数组的第一个元素，第二个指针pTail 初始化为数组的最后一个元素。根据题目要求:所有奇数位于数组的前半部分，偶数位于数组的后半部分；我们只需：

1. 使指针pHead 向后遍历，直到指向的整数为偶数；
2. 使指针pTail 向前遍历，直到指向的整数为奇数；
3. 交换指针pHead 和指针pTail 所指向的元素。
4. 在 pHead 和 pTail 相遇之前，pHead继续向后遍历，pTail继续向前遍历。

引入函数

试考虑把题目改成如下情形：

1. 把数组中的数按照大小分为两部分，所有负数都在非负数的前面，该怎么做？
2. 把数组中的数分成两部分，能被 3 整除的数都在不能被 3 整除的数的前面。该怎么办？

实际上，上面两个问题是我们在开端那个题目的变形，只需改变 while 循环里的条件即可。因此我们可以把这个条件的逻辑框架抽象出来，而把判断的标准变成一个函数指针，也就是用一个单独的函数来判断数字是不是符合条件。因此上面的条件可以变成一个函数来解决：

bool Solution::check(vector<int>::iterator it)
{
    return *it&0x1==1?true:false;//检查是不是奇数,是奇数返回true，偶数返回false 
}

完整代码：

class Solution
{
    public:
        void reorder(vector<int> &v);
        bool check(vector<int>::iterator it);
};
void Solution::reorder(vector<int> &v)
{
    if(v.empty())
        return;
    vector<int>::iterator it1=v.begin();
    vector<int>::iterator it2=--v.end();//end指向最后一个元素的末尾 
    while(it1<it2)
    {
        while(it1<it2&&check(it1))
            ++it1;
        while(it1<it2&&!check(it2))
            --it2;
        if(it1<it2)
            swap(*it1,*it2);
    }
}
bool Solution::check(vector<int>::iterator it)
{
    return *it&0x1==1?true:false;//检查是不是奇数,是奇数返回true，偶数返回false 
}

 不改变元素相对顺序

class Solution {
public:
    void reOrderArray(vector<int> &arr) {
        if(arr.empty())
            return ;
        
        int len=0;
        for(int i=0;i<arr.size();++i)
        {
            if(check(arr[i]))
            {
                int j=i-1;
                int tmp=arr[i];
                for(;j>=len;--j)
                    arr[j+1]=arr[j];
                arr[j+1]=tmp;
                ++len;
            }
        }
    }
private:
    bool check(int val)
    {
        return val&0x01==1?true:false;
    }
};