调整数组顺序使奇数位于偶数前面[算法]

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

分析：如果不考虑时间复杂度，最简单的思路应该是从头扫描这个数组，每碰到一个偶数时，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，这时把该偶数放入这个空位。由于碰到一个偶数，需要移动O(n)个数字，因此总的时间复杂度是O(n^２)。

要求的是把奇数放在数组的前半部分，偶数放在数组的后半部分，因此所有的奇数应该位于偶数的前面。也就是说我们在扫描这个数组的时候，如果发现有偶数出现在奇数的前面，我们可以交换他们的顺序，交换之后就符合要求了。

因此我们可以维护两个指针，第一个指针初始化为数组的第一个数字，它只向后移动；第二个指针初始化为数组的最后一个数字，它只向前移动。在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，我们就交换这两个数字。

基于这个思路，我们可以写出如下的代码：

 

void Reorder(int *pData, unsigned int length, bool (*func)(int));
bool isEven(int n);

/////////////////////////////////////////////////////////////////////////
// Devide an array of integers into two parts, odd in the first part,
// and even in the second part
// Input: pData  - an array of integers
//        length - the length of array
/////////////////////////////////////////////////////////////////////////
void ReorderOddEven(int *pData, unsigned int length)
{
      if(pData == NULL || length == 0)
            return;

      Reorder(pData, length, isEven);
}

/////////////////////////////////////////////////////////////////////////
// Devide an array of integers into two parts, the intergers which 
// satisfy func in the first part, otherwise in the second part
// Input: pData  - an array of integers
//        length - the length of array
//        func   - a function
/////////////////////////////////////////////////////////////////////////
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;
      }
}

/////////////////////////////////////////////////////////////////////////
// Determine whether an integer is even or not
// Input: an integer
// otherwise return false
/////////////////////////////////////////////////////////////////////////
bool isEven(int n)
{
      return (n & 1) == 0;
}

 转自：www.acmerblog.com