剑指Offer——面试题21：调整数组顺序使奇数位于偶数前面

题目描述

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

算法分析

题目比较简单，设置两个指针 p1 和 p2 分别指向数组的开始和结尾，p1向后遍历，p2向前遍历，如果发现 p1 指向偶数，p2 指向奇数（即偶数在奇数之前），则将两者交换，一直做下去，直到 p1 > p2

程序代码

class Solution {
public:
    void reOrderArray(vector<int> &array) 
    {
        //这个一定要加上
        if(array.empty())
            return;

        vector<int>::iterator p1 = array.begin();
        vector<int>::iterator p2 = array.end()-1;
        while(p1 < p2)
        {
            while((*p1&0x1) && p1<p2) p1++;//如果*p1是奇数
            while(!(*p2&0x1) && p1<p2) p2--;//如果*p2是偶数

            if(p1 < p2)
            {
                int temp;
                temp = *p2;
                *p2 = *p1;
                *p1 = temp;
                p1++;
                p2--;
            }
        }
    }
};

扩展部分

如果在题目要求的基础上，保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路

设置指针 p 指向数组首元素，change变量用于记录交换的次数。
从前向后遍历数组，如果发现 (p&0x1)==0 && ((p+1)&0x1)!=0，即偶数在奇数之前就交换，change加1，直到没有发生交换后跳出循环，程序结束。

程序代码

class Solution {
public:
    void reOrderArray(vector<int> &array) 
    {
        if(array.empty())
            return;

        vector<int>::iterator p; 
        int change = 1;

        while(change)
        {
            p = array.begin();
            change = 0;
            while(p != array.end())
            {
                if((*p&0x1)==0 && (*(p+1)&0x1)!=0)
                {
                    int temp;
                    temp = *(p+1);
                    *(p+1) = *p;
                    *p = temp;
                    change++;
                }
                p++;
            }
        }

    }
};