题目

设计一个算法，将数组A[0, .... , n-1]中所有奇数移动到偶数之前，要求不另增存储空间，且时间复杂度为O(n)。

分析

设置两个指针i和j, i从数组的左边往右边遍历，j从数组的右边往左边遍历，当i指向偶数，j指向奇数的时候，将A[i]与A[j]交换；当i大于等于j的时候，算法结束。

代码（这份代码有错，留作警示）

核心代码（这份代码有错）：

/* 分离偶数与奇数，将奇数放到数组的前端，偶数放到后端 */
/* A[]指的是要分离的数组；n指的是数组元素的长度 */
void divide(int A[],int n) {
	int i=0;// i指向数组的第一个元素
	int j=n-1;// j指向数组最后一个元素
	int temp;// 作为临时存储变量
	while(i<j) { // 循环
		if(A[i]%2!=0&&i<j) { // 当是奇数并且i<j时，i指向数组的后一个元素，是偶数的时候停止
			i++;// 指向后一个元素
		}
		if(A[j]%2==0&&i<j) { // 当是偶数并且i<j时，j指向数组的前一个元素，是奇数的时候停止
			j--;// 指向前一个元素
		}
		if(i<j) { // 当i指向偶数，j指向奇数并且i<j时交换奇数与偶数
			temp=A[i];
			A[i]=A[j];
			A[j]=temp;
			i++;// 继续指向后一个元素直到所有的偶数与奇数交换完成
			j--;// 继续指向前一个元素
		}
	}
}

完整代码：

#include <stdio.h>
#include <stdlib.h>

/* 打印数组 */
/* a[]指的是要被打印的数组；length指的是数组中的元素个数 */
void printArray(int a[],int length) {
	printf("\n");
	for(int i=0; i<length; i++) {
		printf("%d\t",a[i]);
	}
	printf("\n");
}

/* 分离偶数与奇数，将奇数放到数组的前端，偶数放到后端 */
/* A[]指的是要分离的数组；n指的是数组元素的长度 */
void divide(int A[],int n) {
	int i=0;// i指向数组的第一个元素
	int j=n-1;// j指向数组最后一个元素
	int temp;// 作为临时存储变量
	while(i<j) { // 循环
		if(A[i]%2!=0&&i<j) { // 当是奇数并且i<j时，i指向数组的后一个元素，是偶数的时候停止
			i++;// 指向后一个元素
		}
		if(A[j]%2==0&&i<j) { // 当是偶数并且i<j时，j指向数组的前一个元素，是奇数的时候停止
			j--;// 指向前一个元素
		}
		if(i<j) { // 当i指向偶数，j指向奇数并且i<j时交换奇数与偶数
			temp=A[i];
			A[i]=A[j];
			A[j]=temp;
			i++;// 继续指向后一个元素直到所有的偶数与奇数交换完成
			j--;// 继续指向前一个元素
		}
	}
}

int main() {
	int a[]= {1,2,3,4,5};
	int length=5;

	printArray(a,length);// 打印操作前的数组元素

	divide(a,length);// 分离偶数与奇数

	printArray(a,length);// 打印操作后的数组元素【 

	return 0;
}

测试结果如下：

代码（纠错）

上面的代码，整体上没什么错，但在while循环中的两个if错误了。

把测试数据换成下面这个，再运行就会发现奇数没有移到偶数前

int a[]= {1,5,4,3,6,2,8};

解决就是将while循环中的两个if换成while，核心代码如下：

/* 分离偶数与奇数，将奇数放到数组的前端，偶数放到后端 */
/* A[]指的是要分离的数组；n指的是数组元素的长度 */
void divide(int A[],int n) {
	int i=0;// i指向数组的第一个元素
	int j=n-1;// j指向数组最后一个元素
	int temp;// 作为临时存储变量
	while(i<j) { // 循环
		while(A[i]%2!=0&&i<j) { // 当是奇数并且i<j时，i指向数组的后一个元素，是偶数的时候停止
			i++;// 指向后一个元素
		}
		while(A[j]%2==0&&i<j) { // 当是偶数并且i<j时，j指向数组的前一个元素，是奇数的时候停止
			j--;// 指向前一个元素
		}
		if(i<j) { // 当i指向偶数，j指向奇数并且i<j时交换奇数与偶数
			temp=A[i];
			A[i]=A[j];
			A[j]=temp;
			i++;// 继续指向后一个元素直到所有的偶数与奇数交换完成
			j--;// 继续指向前一个元素
		}
	}
}

在运行

解析下上面发生的情况：

还是使用上面的测试数据，不过在while(i<j)中打印每次比较的结果

• 使用while

使用while就是判断每个i元素是否是奇数，如果是奇数，就不交换，而是指向下一个元素。j也是这样。

• 使用if

使用if也是判断奇数偶数，指向下一个或上一个元素。

但上面的错误代码的示例恰巧是12345，如果遇到连续奇数或偶数就会产生问题，就会直接通过if(i<j)判断发生交换，如1543628。