面试题14：调整数组顺序使奇数位于偶数前面

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

分析

最简单的办法就是开辟和原数组同样大小的空间，顺次扫描原数组 2 次，第一次将所有奇数放进新数组中，第二次将偶数放入就可以。这种方法的时间复杂度为 O(n)，空间复杂度为 O(n)。

代码如下：

void ReorderOddEven(vector<int>& arr)
{
    vector<int> newarr;
    int i;
    for(i=0;i<arr.size();++i)
    {
        if(arr[i]&0x1)
        {
            newarr.push_back(arr[i]);
        }
    }
    for(i=0;i<arr.size();++i)
    {
        if(!(arr[i]&0x1))
        {
            newarr.push_back(arr[i]);
        }
    }
    arr.clear();
    arr=newarr;
}

以上算法的优点是不会改变原数据的相对顺序。我们也可以只扫描原数组一次，若为奇数，则从新数组前面开始往后放；若为偶数，则从新数组后面开始往前放。这种方法缺点是会使偶数的相对顺序翻转。代码从略。

一种更好的思路是，受快速排序算法的启发，我们模仿快速排序的 partition 函数，从原数组的两端向中间扫描，前、后指针分别遇到偶数和奇数就停下来，然后交换他们即可。

代码如下：

void ReorderOddEven(vector<int>& arr)
{
    int i=0,j=arr.size()-1;
    while(i<j)
    {
        while(i<j && (arr[i] & 0x1))
            i++;
        while(i<j && !(arr[j] & 0x1))
            j--;
        swap(arr[i],arr[j]);
    }
}

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往