剑指offer编程题—调整数组顺序使奇数位于偶数前面

题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

注意：题目最后有个限定条件，保证奇数和奇数，偶数和偶数之间的相对位置不变。

题解如下：

#include<iostream>
#include<vector>
using namespace std;

void display(vector<int> array);

/*错解：
思路：维护两个指针
1. 第一个指针初始化时指向数组的第一个数字，它只向后移动；
2. 第二个指针初始化时指向数组的最后一个数字，它只向前移动。
在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数，并且第二个指针指向的数字是奇数，则交换两个数字
这种解法能满足数组中前半部分全部为奇数，后半部分全部为偶数，
但是不能满足原本的奇数和奇数、偶数和偶数的相对关系不变
举例：原数组22254
调整顺序后：52224，显然原数组中第一个2排到了原数组5的位置上了，
偶数的相对位置发生变化，不满足题目要求。
*/
class Solution1 {
public:
    void reOrderArray(vector<int> &array) {
        int tmp;
        int i=0;
        int j=array.size()-1;
        while(i<j){
            while(i<j && array[i]%2!=0){
                ++i;
            }
            tmp=array[i];
            while(i<j && array[j]%2==0){
                --j;
            }
            array[i]=array[j];
            array[j]=tmp;
            ++i;
            --j;
        }
    }
};

//正解
class Solution2 {
public:
    void reOrderArray(vector<int> &array) {
        vector<int> v;
        int i;
        for(i=0;i<array.size();++i){
            if(array[i]%2!=0){
                v.push_back(array[i]);
            }
        }
        for(i=0;i<array.size();++i){
            if(array[i]%2==0){
                v.push_back(array[i]);
            }
        }
        array=v;
    }
};

int main(int argc,char **argv)
{
    int a[5]={2,2,2,5,4};
    vector<int> v(a,a+5);
    display(v);
    class Solution1 sol1;
    sol1.reOrderArray(v);
    display(v);

    vector<int> v1(a,a+5);
    display(v1);
    class Solution2 sol2;
    sol2.reOrderArray(v1);
    display(v1);
    return 0;
}

void display(vector<int> array)
{
    int i;
    for(i=0;i<array.size();++i){
        printf("%d ",array[i]);
    }
    printf("\n");
}

运行结果如下图：