#奇偶調序 ## 題目描述 輸入一個整數數組，調整數組中數字的順序，使得所有奇數位于數組的前半部分，所有偶數位于數組的后半部分。要求時間復雜度為O(n)。 ### 分析與解法 最容易想到的辦法是從頭掃描這個數組，每碰到一個偶數，拿出這個數字，并把位于這個數字后面的所有數字往前挪動一位。挪完之后在數組的末尾有一個空位，然后把該偶數放入這個空位。由于每碰到一個偶數，需要移動O(n)個數字，所以這種方法總的時間復雜度是O(n^2)，不符合題目要求。 事實上，若把奇數看做是小的數，偶數看做是大的數，那么按照題目所要求的奇數放在前面偶數放在后面，就相當于小數放在前面大數放在后面，聯想到快速排序中的partition過程，不就是通過一個主元把整個數組分成大小兩個部分么，小于主元的小數放在前面，大于主元的大數放在后面。 而partition過程有以下兩種實現： - 一頭一尾兩個指針往中間掃描，如果頭指針遇到的數比主元大且尾指針遇到的數比主元小，則交換頭尾指針所分別指向的數字； - 一前一后兩個指針同時從左往右掃，如果前指針遇到的數比主元小，則后指針右移一位，然后交換各自所指向的數字。 類似這個partition過程，奇偶排序問題也可以分別借鑒partition的兩種實現解決。 為何？比如partition的實現一中，如果最終是為了讓整個序列元素從小到大排序，那么頭指針理應指向的就是小數，而尾指針理應指向的就是大數，故當頭指針指的是大數且尾指針指的是小數的時候就不正常，此時就當交換。 #### 解法一 借鑒partition的實現一，我們可以考慮維護兩個指針，一個指針指向數組的第一個數字，我們稱之為頭指針，向右移動；一個指針指向最后一個數字，稱之為尾指針，向左移動。 這樣，兩個指針分別從數組的頭部和尾部向數組的中間移動，如果第一個指針指向的數字是偶數而第二個指針指向的數字是奇數，我們就交換這兩個數字。 因為按照題目要求，最終是為了讓奇數排在數組的前面，偶數排在數組的后面，所以頭指針理應指向的就是奇數，尾指針理應指向的就是偶數，故當頭指針指向的是偶數且尾指針指向的是奇數時，我們就當立即交換它們所指向的數字。 思路有了，接下來，寫代碼實現： ```cpp //判斷是否為奇數 bool IsOddNumber(int data) { return data & 1 == 1; } //奇偶互換 void OddEvenSort(int *pData, unsigned int length) { if (pData == NULL || length == 0) return; int *pBegin = pData; int *pEnd = pData + length - 1; while (pBegin < pEnd) { //如果pBegin指針指向的是奇數，正常，向右移 if (IsOddNumber(*pBegin)) { pBegin++; } //如果pEnd指針指向的是偶數，正常，向左移 else if (!IsOddNumber(*pEnd)) { pEnd--; } else { //否則都不正常，交換 //swap是STL庫函數，聲明為void swap(int& a, int& b); swap(*pBegin, *pEnd); } } } ``` 本方法通過頭尾兩個指針往中間掃描，一次遍歷完成所有奇數偶數的重新排列，時間復雜度為O(n)。 #### 解法二 我們先來看看快速排序partition過程的第二種實現是具體怎樣的一個原理。 partition分治過程，每一趟排序的過程中，選取的主元都會把整個數組排列成一大一小的序列，繼而遞歸排序完整個數組。如下偽代碼所示： PARTITION(A, p, r) 1 x ← A[r] 2 i ← p - 1 3 for j ← p to r - 1 4 do if A[j] ≤ x 5 then i ← i + 1 6 exchange A[i] <-> A[j] 7 exchange A[i + 1] <-> A[r] 8 return i + 1 舉個例子如下：現要對數組data = {2, 8,7, 1, 3, 5, 6, 4}進行快速排序，為了表述方便，令`i`指向數組頭部前一個位置，`j`指向數組頭部元素，`j`在前，`i`在后，雙雙從左向右移動。 ① j 指向元素2時，i 也指向元素2，2與2互換不變 i p/j 2 8 7 1 3 5 6 4(主元) ② 于是j 繼續后移，直到指向了1，1 <= 4，于是i++，i 指向8，故j 所指元素1 與 i 所指元素8 位置互換： i j 2 1 7 8 3 5 6 4 ③ j 繼續后移，指到了元素3,3 <= 4，于是同樣i++，i 指向7，故j 所指元素3 與 i 所指元素7 位置互換： i j 2 1 3 8 7 5 6 4 ④ j 一路后移，沒有再碰到比主元4小的元素： i j 2 1 3 8 7 5 6 4 ⑤ 最后，A[i + 1] <-> A[r]，即8與4交換，所以，數組最終變成了如下形式： 2 1 3 4 7 5 6 8 這樣，快速排序第一趟完成。就這樣，4把整個數組分成了倆部分，2 1 3,7 5 6 8，再遞歸對這兩部分分別進行排序。 借鑒partition的上述實現，我們也可以維護兩個指針i和j，一個指針指向數組的第一個數的前一個位置，我們稱之為后指針i，向右移動；一個指針指向數組第一個數，稱之為前指針j，也向右移動，且前指針j先向右移動。如果前指針j指向的數字是奇數，則令i指針向右移動一位，然后交換i和j指針所各自指向的數字。 因為按照題目要求，最終是為了讓奇數排在數組的前面，偶數排在數組的后面，所以i指針理應指向的就是奇數，j指針理應指向的就是偶數，所以，當j指針指向的是奇數時，不正常，我們就當讓i++，然后交換i和j指針所各自指向的數字。 參考代碼如下： ```c //奇偶互換 void OddEvenSort2(int data[], int lo, int hi) { int i = lo - 1; for (int j = lo; j < hi; j++) { //data[j]指向奇數，交換 if ( IsOddNumber(data[j]) ) { i = i + 1; swap(data[i], data[j]); } } swap(data[i + 1], data[hi]); } ``` 此解法一前一后兩個指針同時向右掃描的過程中，也是一次遍歷完成奇數偶數的重新排列，故時間復雜度也為O(n)。 ### 舉一反三 一個未排序整數數組，有正負數，重新排列使負數排在正數前面，并且要求不改變原來的正負數之間相對順序，比如： 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》。