使數組中的奇數位于偶數之前
從數組兩端遍歷，檢測當前元素的奇偶性，條件允許時交換，直到兩個索引交叉。
http://www.shnenglu.com/jake1036/archive/2011/05/20/146798.html
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 using namespace std;
5
6 struct node
7 {
8 int m_;
9 public:
10 node(int i = 0) : m_(i) {};
11 int m() const
12 {
13 return m_;
14 }
15 };
16
17 bool operator < (const node& lhs, const node& rhs)
18 {
19 if (lhs.m() % 2 == 1 && rhs.m() % 2 == 0)
20 {
21 return true;
22 }
23 else if (lhs.m() % 2 == 0 && rhs.m() % 2 == 1)
24 {
25 return false;
26 }
27 else
28 {
29 return lhs.m() < rhs.m();
30 }
31 }
32
33 bool operator == (const node& lhs, const node& rhs)
34 {
35 return lhs.m() == rhs.m();
36 }
37
38 bool operator > (const node& lhs, const node& rhs)
39 {
40 return !(lhs < rhs || lhs == rhs);
41 }
42
43 void foo(int a[], int n)
44 {
45 int left = 0, right = n - 1;
46 while (left < right)
47 {
48 while (left < right && (a[left] & 0x01) == 1)
49 {
50 ++left;
51 }
52 while (right > left && (a[right] & 0x01) == 0)
53 {
54 --right;
55 }
56 if (left < right)
57 {
58 a[left] ^= a[right];
59 a[right] ^= a[left];
60 a[left] ^= a[right];
61 }
62 }
63 }
64
65 int main()
66 {
67 int a[] = {2, 4, 6, 8, 10, 1, 3, 5, 7, 9};
68 vector<node> test;
69 for (int i = 0; i != sizeof (a) / sizeof (*a); ++i)
70 {
71 test.push_back(node(a[i]));
72 }
73 foo(a, sizeof (a) / sizeof (*a));
74 for (int i = 0; i != sizeof (a) / sizeof (*a); ++i)
75 {
76 cout << a[i] << ' ';
77 }
78 cout << endl;
79
80 sort(test.begin(), test.end());
81 for (vector<node>::size_type i = 0; i != test.size(); ++i)
82 {
83 cout << test[i].m() << ' ';
84 }
85 cout << endl;
86
87 sort(test.begin(), test.end(), greater<node>());
88 for (vector<node>::size_type i = 0; i != test.size(); ++i)
89 {
90 cout << test[i].m() << ' ';
91 }
92 cout << endl;
93 }
posted on 2011-07-23 20:20
unixfy 閱讀(226)
評論(0) 編輯 收藏 引用