給定一個(gè)存放整數(shù)的數(shù)組，重新排列數(shù)組使得數(shù)組左邊為奇數(shù)，右邊為偶數(shù)。
要求：空間復(fù)雜度O(1)，時(shí)間復(fù)雜度為O（n）。
1 bool func(int n)
2 {
3 return (n&1)==0; // n%2 is more expensive
4 }
5
6 void group_oddeven(std::vector<int>& a, bool (*func)(int))
7 {
8 int i = 0, j = a.size()-1;
9 int buf = 0;
10 while (i < j) {
11 if (!func(a[i])) // odd, move forward
12 { i++; continue; }
13 if (func(a[j])) // even, move backward
14 { j--; continue; }
15
16 std::swap(a[i++], a[j--]);
17 }
18 }
19