题目
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
分析
事实上，这个题比较简单，很多种方式都可以实现，但是其时间复杂度或空间复杂度不尽相同。
解法一
书中作者提到一种初始的做法是，从头扫描整个数组，如果遇到偶数，则拿出这个数，并且把整个数组的数据都向前挪动一位，再把拿出的数放到末尾。每碰到一个偶数就需要移动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语言代码实现如下：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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87//reorder.c
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++;
}
}
}
void printArray(int A[],int n)
{
if(n > 100)
{
printf("too much，will not print\n");
return;
}
int i = 0;
while(i < n)
{
printf("%d ",A[i]);
i++;
}
printf("\n");
}
int main(int argc,char *argv[])
{
if(argc < 2)
{
printf("usage:reorder num\n");
return -1;
}
int len = atoi(argv[1]);
printf("reorder for %d numbers\n",len);
/*随机产生输入数量的数据*/
int *A = malloc(sizeof(int)*len);
int i = 0;
srand(time(NULL));
while(i < len)
{
A[i] = rand()%100;
i++;
}
printf("before reorder:");
printArray(A,len);
/*对数据进行排序*/
reorder(A,len);
printf("after reorder:");
printArray(A,len);
free(A);
return 0;
}
解法二
很多人其实最先想到的解法可能是，创建一个新的数组，从头扫描，遇到偶数放后边，遇到奇数放前边。扫描结束后，再将数组内容拷贝到原数组，这样整个时间复杂度为(n）,而空间复杂度也为O(n)，这样的方法实现简单，也不容易出错。C语言代码实现如下（省略了main函数以及printArr函数）：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//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语言代码实现如下（省略了main函数以及printArr函数）：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//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;
}
}
}
运行效率比较
编译后，对一百万数据进行操作，运行时间结果如下。
解法一：1
$ time ./reorder 1000000
并没有耐心等到结果出来。
解法二：1
2
3
4
5
6
7
8$ 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亿数据进行操作，耗时很短，只是内存占用较多。
解法三：1
2
3
4
5
6
7
8$ 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
耗时很短，内存占用少。
扩展
在本题中，只是对整数是奇还是偶进行分开，那么如果是别的条件呢？例如是否为素数，是否为正数等等。我们可以让调用者传入一个条件函数，让它决定到底是放在后半部分，还是前半部分。这是不是很向库函数qsort需要传入一个比较函数的做法？这部分内容可以参考《函数指针》，根据这个思路，我们修改解法三的代码：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//reorder3.c
/*定义函数指针类型*/
typedef int (*CheckFun)(int);
int isMatch(int num)
{
if(0 == (num & 1))
return 1;
else
return 0;
}
void reorder(int arr[],int len,CheckFun isMatch)
{
if(NULL == arr || 0 == len || NULL == isMatch)
return;
int i = 0;
int j = len - 1;
int temp;
for(;;)
{
/*i j分别向右和向左移动，i遇到偶数停止，j遇到奇数停止？*/
while(!(*isMatch)(arr[i]))
{
i++;
}
while((*isMatch)(arr[j]))
{
j--;
}
if(i < j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/*交错时停止*/
else
{
break;
}
}
}
这个时候通过传入函数指针，可以对任意条件进行处理了。
总结
我们发现，一些基本算法的思想，通常可以用到其他问题上，而不同的思路，带来的效率可能天差地别。
练习
尝试自己实现上面的算法。
