06.07.md

##奇偶调序

题目描述

输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

分析与解法

解法一

最容易想到的办法是从头扫描这个数组，每碰到一个偶数时，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，这时把该偶数放入这个空位。由于碰到一个偶数，需要移动O(n)个数字，只是这种方法总的时间复杂度是O(n^2)，不符合要求。

解法二

再细想下，我们发觉可以考虑维护两个指针，一个指针指向数组的第一个数字，向后移动；一个个指针指向最后一个数字，向前移动。如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，我们就交换这两个数字。

思路有了，接下来，写代码实现：

//思路，很简答，俩指针，一首一尾  
//如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，  
//我们就交换这两个数字  
  
// 2 1 3 4 6 5 7   
// 7 1 3 4 6 5 2  
// 7 1 3 5 6 4 2  
  
//如果限制空间复杂度为O（1），时间为O（N），且奇偶数之间相对顺序不变，就相当于正负数间顺序调整的那道题了。  
  
//copyright@2010 zhedahht
void Reorder(int *pData, unsigned int length, bool (*func)(int));
bool isEven(int n);
void ReorderOddEven(int *pData, unsigned int length)
{
    if (pData == NULL || length == 0)
        return;

    Reorder(pData, length, isEven);
}
void Reorder(int *pData, unsigned int length, bool (*func)(int))
{
    if (pData == NULL || length == 0)
        return;
    int *pBegin = pData;
    int *pEnd = pData + length - 1;
    while (pBegin < pEnd)
    {
        // if *pBegin does not satisfy func, move forward
        if (!func(*pBegin))  //如果是奇数, 则向后移一个位置
        {
            pBegin ++;
            continue;
        }

        // if *pEnd does not satisfy func, move backward
        if (func(*pEnd))     //如是是偶数, 则向前移一个位置
        {
            pEnd --;
            continue;
        }
        // if *pBegin satisfy func while *pEnd does not,
        // swap these integers
        int temp = *pBegin;
        *pBegin = *pEnd;
        *pEnd = temp;
    }
}
bool isEven(int n)
{
    return (n & 1) == 0;
}

类似问题

一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来的正负数之间相对顺序，比如： input: 1,7,-5,9,-12,15 ans: -5,-12,1,7,9,15 要求时间复杂度O(N),空间O(1)。

分析：如果本题没有这个要求“并且要求不改变原来的正负数之间相对顺序”，那么同奇偶数排序是一道题，但加上这个不能改变正负数之间的相对顺序后，便使得问题变得比较艰难了，若有兴趣，读者可以参考这篇论文《STABLE MINIMUM SPACE PARTITIONING IN LINEAR TIME》。