思路分析：
类似快速排序的处理。可以用两个指针分别指向数组的头和尾，头指针正向遍历数组，找到第一个偶数，尾指针逆向遍历数组，找到第一个奇数，使用引用参数传值交换两个指针指向的数字，然后两指针沿着相应的方向继续向前移动，重复上述步骤，直到头指针大于等于尾指针为止。
代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 |
#include "stdafx.h"#include <iostream>using
namespace std;void
Swap(int& a, int& b){ int
temp = a; a = b; b = temp;}void
ReverseArray(int
arr[], int
len){ if
(arr == NULL || len <= 0) printf("数组中无元素，变换毛线啊。"); else { int
begin = 0; int
end = len - 1; while
(begin < end) { while
(arr[begin] % 2 == 1 && end>begin) begin++; while
(arr[end] % 2 == 0 && end > begin) end--; Swap(arr[begin], arr[end]); } }}int
main(){ int
array[] = { 1, 23, 2, 34, 21, 45, 26, 22, 41, 66, 74, 91, 17, 64 }; int
len = sizeof(array) / sizeof(array[0]); int
i; printf("原数组为："); for
(i = 0; i < len; i++) printf("%d ", array[i]); printf("\n"); ReverseArray(array, len); printf("经过变换后的数组为："); for
(i = 0; i < len; i++) printf("%d ", array[i]); printf("\n"); getchar(); return
0;} |
效果如图：
如何重新排列数组使得数组左边为奇数，右边为偶数，并使得空间复杂度为O(1)，时间复杂度为O(n),布布扣,bubuko.com
如何重新排列数组使得数组左边为奇数，右边为偶数，并使得空间复杂度为O(1)，时间复杂度为O(n)
原文：http://www.cnblogs.com/cysolo/p/3593011.html