輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有奇數位於數組的前半部分，所有偶數位於數組的後半部分。 ...
題目
輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有奇數位於數組的前半部分，所有偶數位於數組的後半部分。
分析
事實上，這個題比較簡單，很多種方式都可以實現，但是其時間複雜度或空間複雜度不盡相同。
解法一
書中作者提到一種初始的做法是，從頭掃描整個數組，如果遇到偶數，則拿出這個數，並且把整個數組的數據都向前挪動一位，再把拿出的數放到末尾。每碰到一個偶數就需要移動O(N)次，這樣總的時間複雜度為O(n^2),空間複雜度為O(1)。
這種方式很簡單，如果已經很清楚是怎麼回事，可以跳過例子說明，繼續閱讀下一個解法。但是可以嘗試自己寫一下代碼，發現有些細節部分並不是那麼容易寫出來。
舉個例子，假設有數據1,2,3,4,5,6：
從左往右掃描，找到第一個偶數2，並臨時保存：
| 1 | 2 | 3 | 4 | 5 | 6 |
| ↑ | |||||
| 取出 |
將2後面的所有數往前移動一個位置，並將2放到最後一個位置：
| 1 | 3 | 4 | 5 | 6 | 2 |
| ↑ | 移動後 |
繼續掃描當前位置，發現3為奇數，繼續，發現4為偶數，將從3之後位置的數開始，到倒數第二個位置，所有數往前移動一個位置，並將4放到最後：
| 1 | 3 | 5 | 6 | 4 | 2 |
| ↑ | 移動後 |
繼續掃描當前位置數5，6，至此，偶數有2兩個，當前指向位置為,所在下標為4，總數 - 位置 <= 偶數 ,結束。
| 1 | 3 | 5 | 6 | 4 | 2 |
| ↑ |
根據該思路，C語言代碼實現如下：
//reorder.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
void reorder(int arr[],int len)
{
if(NULL == arr || 0 == len)
return;
/*統計偶數數量，減少移動次數*/
int evenNum = 0;
int loop = 0;
int temp;
int inLoop = 0;
while(loop < len)
{
/*如果是偶數，則需要開始移動*/
temp = arr[loop];
/*如果已經達到了*/
if(0 == (temp & 1) && (len - loop > evenNum))
{
/*從當前位置開始移動，直到遇到剩下的數量是偶數的個數*/
for(inLoop = loop + 1;inLoop < len - evenNum;inLoop++)
{
arr[inLoop-1] = arr[inLoop];
}
/*把空出來的位填充上*/
arr[len - evenNum - 1] = temp;
evenNum++;
/*交換後繼續*/
continue;
}
/*繼續迴圈下一個*/
else
{
loop++;
}
}
}
解法二
很多人其實最先想到的解法可能是，創建一個新的數組，從頭掃描，遇到偶數放後邊，遇到奇數放前邊。掃描結束後，再將數組內容拷貝到原數組，這樣整個時間複雜度為(n）,而空間複雜度也為O(n)，這樣的方法實現簡單，也不容易出錯。C語言代碼實現如下：
//reorder1.c
void reorder(int arr[],int len)
{
if(NULL == arr || 0 == len)
return;
/*記錄奇偶的數量*/
int oddNum = 0;
int evenNum = 0;
int loop = 0;
/*創建一個新的數組*/
int *temp = malloc(len * sizeof(int));
if(NULL == temp)
{
printf("malloc memory failed\n");
return;
}
/*拷貝數組，並遍歷*/
memcpy(temp,arr,sizeof(int)*len);
for(;loop < len;loop++)
{
/*偶數放到數組末尾*/
if(0 == (temp[loop] & 1))
{
arr[len-1-evenNum] = temp[loop];
evenNum++;
}
/*奇數放到數組末尾*/
else
{
arr[oddNum] = temp[loop];
oddNum++;
}
}
free(temp);
}
解法三
還記得我們之前介紹過的《快速排序優化詳解》嗎？快速排序中，有一個分區操作，是將整個數組大於等於基準的部分放右邊，而小於等於基準的部分放左邊，即根據基準，將數組一分為二。其實在這裡，同樣可以參考這個思路，只不過跟基準比大小，變成了判斷是奇還是偶。
這裡簡單描述一下該思路，更多細節可以參考《快速排序優化詳解》中如何將元素移動到基準兩側一節：
- 定義下標i和j，分別從開頭和結尾開始掃描
- 當i遇到偶數時，停止掃描
- 當j遇到奇數時，停止掃描
- 此時交換i和j位置的值
- 繼續前面的操作，直到i和j交錯或相等
舉個例子，假設有數據1,2,3,4,5,6,7,8：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ↑ | ↑ | ||||||
| i | j |
i和j繼續掃描，i遇到2停止，j遇到5停止，交換兩處的值：
| 1 | 7 | 3 | 4 | 5 | 6 | 2 | 8 |
| ↑ | ↑ | ||||||
| i | j |
i和j繼續掃描，i遇到4停止，j遇到5停止，交換兩處的值：
| 1 | 7 | 3 | 5 | 4 | 6 | 2 | 8 |
| ↑ | ↑ | ||||||
| i | j |
繼續掃描，此時，i和j交錯，掃描結束：
| 1 | 7 | 3 | 5 | 4 | 6 | 2 | 8 |
| ↑ | ↑ | ||||||
| j | i |
基於該思路的演算法時間複雜度為O(n)，空間複雜度為O(1)，C語言代碼實現如下：
//reorder2.c
void reorder(int arr[],int len)
{
if(NULL == arr || 0 == len)
return;
int i = 0;
int j = len - 1;
int temp;
for(;;)
{
/*i j分別向右和向左移動，i遇到偶數停止，j遇到奇數停止？*/
while(1 == (arr[i] & 1))
{
i++;
}
while(0 == (arr[j] & 1))
{
j--;
}
if(i < j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/*交錯時停止*/
else
{
break;
}
}
}
運行效率比較
編譯後，對一百萬數據進行操作，運行時間結果如下。
解法一：
$ time ./reorder 1000000
並沒有耐心等到結果出來。
解法二：
$ time ./reorder1 100000000
reorder for 100000000 numbers
before reorder:too much，will not print
after reorder:too much，will not print
real 0m2.425s
user 0m2.141s
sys 0m0.284s
對1億數據進行操作，耗時很短，只是記憶體占用較多。
解法三：
$ time ./reorder2 100000000
reorder for 100000000 numbers
before reorder:too much，will not print
after reorder:too much，will not print
real 0m2.146s
user 0m2.018s
sys 0m0.128s
耗時很短，記憶體占用少。
微信公眾號【編程珠璣】：專註但不限於分享電腦編程基礎，Linux，C語言，C++，演算法，資料庫等編程相關[原創]技術文章，號內包含大量經典電子書和視頻學習資源。歡迎一起交流學習，一起修煉電腦“內功”，知其然，更知其所以然。
擴展
在本題中，只是對整數是奇還是偶進行分開，那麼如果是別的條件呢？例如是否為素數，是否為正數等等。我們可以讓調用者傳入一個條件函數，讓它決定到底是放在後半部分，還是前半部分。這是不是很向庫函數qsort需要傳入一個比較函數的做法？這部分內容可以參考《函數指針》，根據這個思路，我們修改解法三的代碼：
略
這個時候通過傳入函數指針，可以對任意條件進行處理了。
總結
我們發現，一些基本演算法的思想，通常可以用到其他問題上，而不同的思路，帶來的效率可能天差地別。
練習
嘗試自己實現上面的演算法。如果需要保證奇數或偶數之間的相對位置不變，該如何修改？
備註
完整代碼以及模擬一億數據處理請訪問:劍指offer：調整數組順序使奇數位於偶數前面
微信公眾號【編程珠璣】：專註但不限於分享電腦編程基礎，Linux，C語言，C++，演算法，資料庫等編程相關[原創]技術文章，號內包含大量經典電子書和視頻學習資源。歡迎一起交流學習，一起修煉電腦“內功”，知其然，更知其所以然。
