題目：輸入一個整數(shù)數(shù)組，調(diào)整數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分，所有偶數(shù)位于數(shù)組的后半部分。要求時間復(fù)雜度為O(n)。

分析：如果不考慮時間復(fù)雜度，最簡單的思路應(yīng)該是從頭掃描這個數(shù)組，每碰到一個偶數(shù)時，拿出這個數(shù)字，并把位于這個數(shù)字后面的所有數(shù)字往前挪動一位。挪完之后在數(shù)組的末尾有一個空位，這時把該偶數(shù)放入這個空位。由于碰到一個偶數(shù)，需要移動O(n)個數(shù)字，因此總的時間復(fù)雜度是O(n^２)。

要求的是把奇數(shù)放在數(shù)組的前半部分，偶數(shù)放在數(shù)組的后半部分，因此所有的奇數(shù)應(yīng)該位于偶數(shù)的前面。也就是說我們在掃描這個數(shù)組的時候，如果發(fā)現(xiàn)有偶數(shù)出現(xiàn)在奇數(shù)的前面，我們可以交換他們的順序，交換之后就符合要求了。

因此我們可以維護(hù)兩個指針，第一個指針初始化為數(shù)組的第一個數(shù)字，它只向后移動；第二個指針初始化為數(shù)組的最后一個數(shù)字，它只向前移動。在兩個指針相遇之前，第一個指針總是位于第二個指針的前面。如果第一個指針指向的數(shù)字是偶數(shù)而第二個指針指向的數(shù)字是奇數(shù)，我們就交換這兩個數(shù)字。

基于這個思路，我們可以寫出如下的代碼：

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;
}

討論：

上面的代碼有三點(diǎn)值得提出來和大家討論：

１．函數(shù)isEven判斷一個數(shù)字是不是偶數(shù)并沒有用%運(yùn)算符而是用&。理由是通常情況下位運(yùn)算符比%要快一些；

２．這道題有很多變種。這里要求是把奇數(shù)放在偶數(shù)的前面，如果把要求改成：把負(fù)數(shù)放在非負(fù)數(shù)的前面等，思路都是都一樣的。

３．在函數(shù)Reorder中，用函數(shù)指針func指向的函數(shù)來判斷一個數(shù)字是不是符合給定的條件，而不是用在代碼直接判斷（hard code）。這樣的好處是把調(diào)整順序的算法和調(diào)整的標(biāo)準(zhǔn)分開了（即解耦，decouple）。當(dāng)調(diào)整的標(biāo)準(zhǔn)改變時，Reorder的代碼不需要修改，只需要提供一個新的確定調(diào)整標(biāo)準(zhǔn)的函數(shù)即可，提高了代碼的可維護(hù)性。例如要求把負(fù)數(shù)放在非負(fù)數(shù)的前面，我們不需要修改Reorder的代碼，只需添加一個函數(shù)來判斷整數(shù)是不是非負(fù)數(shù)。這樣的思路在很多庫中都有廣泛的應(yīng)用，比如在ＳＴＬ的很多算法函數(shù)中都有一個仿函數(shù)（functor）的參數(shù)（當(dāng)然仿函數(shù)不是函數(shù)指針，但其思想是一樣的）。如果在面試中能夠想到這一層，無疑能給面試官留下很好的印象。