分析：如果不考慮時間復雜度，最簡單的思路應該是從頭掃描這個數組，每碰到一個偶數時，拿出這個數字，並把位於這個數字後面的所有數字往前挪動一位。挪完之後在數組的末尾有一個空位，這時把該偶數放入這個空位。由於碰到一個偶數，需要移動O(n)個數字，因此總的時間復雜度是O(n２)。
要求的是把奇數放在數組的前半部分，偶數放在數組的後半部分，因此所有的奇數應該位於偶數的前面。也就是說我們在掃描這個數組的時候，如果發現有偶數出現在奇數的前面，我們可以交換他們的順序，交換之後就符合要求了。
因此我們可以維護兩個指針，第一個指針初始化為數組的第一個數字，它只向後移動；第二個指針初始化為數組的最後一個數字，它只向前移動。在兩個指針相遇之前，第一個指針總是位於第二個指針的前面。如果第一個指針指向的數字是偶數而第二個指針指向的數字是奇數，我們就交換這兩個數字。
1 #include<stdio.h>
2 #include<tchar.h>
3
4 void Reorder(int *pData, unsigned int length, bool (*func)(int));
5 bool isEven(int n);
6
7 /*思路:使用兩個指針，一個指向數組的一個數字，只向後移動，
8 一個指向數組的最後一個數字， 只向前移動，再兩個指針相遇前，
9 如果第一個指針指向的是偶數，第二個指向的是奇數，就交換這兩個數字
10 */
11 void ReorderOddEven_1(int *pData, unsigned int length)
12 {
13 if(pData == NULL || length == 0)
14 return;
15
16 int *pBegin = pData;
17 int *pEnd = pData + length - 1;
18
19 while(pBegin < pEnd)
20 {
21 while(pBegin < pEnd && (*pBegin & 0x1) != 0)
22 pBegin ++;
23 while(pBegin < pEnd && (*pEnd & 0x1) == 0)
24 pEnd --;
25
26 if(pBegin < pEnd)
27 {
28 int temp = *pBegin;
29 *pBegin = *pEnd;
30 *pEnd = temp;
31 }
32 }
33 }
34
35 //方法2和方法1思路是一樣的，只是將方法1的函數給解耦成兩部分，提高了代碼的復用性。
36 void ReorderOddEven_2(int *pData, unsigned int length)
37 {
38 Reorder(pData, length, isEven);
39 }
40
41 void Reorder(int *pData, unsigned int length, bool (*func)(int))
42 {
43 if(pData == NULL || length == 0)
44 return;
45
46 int *pBegin = pData;
47 int *pEnd = pData + length - 1;
48
49 while(pBegin < pEnd)
50 {
51 while(pBegin < pEnd && !func(*pBegin))
52 pBegin ++;
53
54 while(pBegin < pEnd && func(*pEnd))
55 pEnd --;
56
57 if(pBegin < pEnd)
58 {
59 int temp = *pBegin;
60 *pBegin = *pEnd;
61 *pEnd = temp;
62 }
63 }
64 }
65
66 bool isEven(int n)
67 {
68 return (n & 1) == 0;
69 }
70
71 void PrintArray(int numbers[], int length)
72 {
73 if(length < 0)
74 return;
75 for(int i = 0 ; i < length ; ++i)
76 printf("%d\t", numbers[i]);
77
78 printf("\n");
79 }
80
81 int main()
82 {
83 //使用方法1測試
84 int numbersOne[] = {1, 2, 3, 4, 5, 6, 7};
85 int lengthOne = sizeof(numbersOne) / sizeof(int);
86 printf("Test for solution 1:\n");
87 PrintArray(numbersOne, lengthOne);
88 ReorderOddEven_1(numbersOne,lengthOne);
89 PrintArray(numbersOne, lengthOne);
90 printf("\n");
91
92 //使用方法2測試
93 int numbersTwo[] = {2, 4, 6, 1, 3, 5, 7};
94 int lengthTwo = sizeof(numbersTwo) / sizeof(int);
95 printf("Test for solution 2:\n");
96 PrintArray(numbersTwo,lengthTwo);
97 ReorderOddEven_2(numbersTwo,lengthTwo);
98 PrintArray(numbersTwo, lengthTwo);
99
100 return 0 ;
101 }
還有一種思路，使用兩個指針，一個在前一個在後，當在前的遇到奇數時，就和在後的數進行交換。有一個細節是，若數組一開始就是奇數，則在前的和在和的指向的是同一個數，交換後數組不變，直到遇到第一個偶數時，在前的指針超過在後的指針。
1 #include<iostream>
2 //#include<algorithm> 可省略swap
3 using namespace std;
4
5 void swap(int* num1, int* num2)
6 {
7 int temp = *num1;
8 *num1 = *num2;
9 *num2 = temp;
10 }
11 bool isEven(int n)
12 {
13 return (n & 1)==0;
14 }
15
16 void Reorder(int *pData, unsigned int length, bool (*func)(int))
17 {
18 if(length < 0 || pData == NULL)
19 return;
20 else{
21 int i = -1;
22 for(int j =0 ; j < length; j++)
23 {
24 /*當數組中的數字為奇數時，交換i,j指向的兩個數字
25 當起始數字為奇數時，此時交換的數字是相同的，
26 當中間有偶數時，條件語句不滿足，跳過，此時j繼續增加，i不變，
27 然後遇到奇數時，j指向奇數,滿足條件，i指向前一個奇數，i++後，
28 此時i指向此奇數後面的偶數,交換兩數。
29 */
30 if(!func(*(pData+j)))
31 {
32 i++;
33 swap(*(pData+i), *(pData+j));
34 }
35 }
36 }
37 }
38
39 void PrintArray(int numbers[], int length)
40 {
41 if(length < 0)
42 return;
43 for(int i = 0 ; i < length ; ++i)
44 printf("%d\t", numbers[i]);
45
46 printf("\n");
47 }
48
49 int main()
50 {
51 int numbers[] = {3,4,5,6,7,8,9,10,1,2};
52 int length = sizeof(numbers) / sizeof(int);
53
54 PrintArray(numbers, length) ;
55
56 Reorder(numbers, length, isEven);
57
58 PrintArray(numbers, length);
59
60 return 0;
61 }
