劍指offer(07)-調整數組順序使奇數位于偶數前面【轉】

來源：http://www.acmerblog.com/offer-6-2429/

題目來自劍指offer系列 九度 1516

<dl></dl>

<dt>題目描述：</dt>

<dd>輸入一個整數數組，實作一個函數來調整該數組中數字的順序，使得所有的奇數位于數組的前半部分，所有的偶數位于位于數組的後半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變。</dd>

<dt>輸入：</dt>

<dd>每個輸入檔案包含一組測試案例。</dd>

對于每個測試案例，第一行輸入一個n，代表該數組中數字的個數。

接下來的一行輸入n個整數。代表數組中的n個數。

<dt>輸出：</dt>

<dd>對應每個測試案例，</dd>

輸入一行n個數字，代表調整後的數組。注意，數字和數字之間用一個空格隔開，最後一個數字後面沒有空格。

<dt>樣例輸入：</dt>

<dd></dd>

<dt>樣例輸出：</dt>

但是如果要保持相對位置的話，目前還沒有想到優美的算法。這裡的代碼完全是為了AC而寫的。可以無視

============================================================================================================================================

下面是不考慮處理後數字順序的那個文章的資料：http://www.acmerblog.com/interview-9-2427/

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

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

要求的是把奇數放在數組的前半部分，偶數放在數組的後半部分，是以所有的奇數應該位于偶數的前面。也就是說我們在掃描這個數組的時候，如果發現有偶數出現在奇數的前面，我們可以交換他們的順序，交換之後就符合要求了。

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

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

讨論：

上面的代碼有三點值得提出來和大家讨論：

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

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

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

轉自：http://zhedahht.blog.163.com/