本文共 1763 字，大约阅读时间需要 5 分钟。

地址：http://ac.jobdu.com/problem.php?pid=1516

题目1516：调整数组顺序使奇数位于偶数前面

题目描述：

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

输入：

每个输入文件包含一组测试案例。

对于每个测试案例，第一行输入一个n，代表该数组中数字的个数。

接下来的一行输入n个整数。代表数组中的n个数。

输出：

对应每个测试案例，

输入一行n个数字，代表调整后的数组。注意，数字和数字之间用一个空格隔开，最后一个数字后面没有空格。

样例输入：

51 2 3 4 5

样例输出：

1 3 5 2 4

1、每读取一个数字就判断该数字是否为奇数

2、若为奇数，直接输出

3、若为偶数，存储到临时数组中

4、遍历所有输入后打印临时数组中的偶数

#include 
   
    int buf[100000];int main(){    int n;    scanf("%d", &n);    int k = 0;    bool first = true;    for(int i = 0; i < n; i ++){        int t;        scanf("%d", &t);        if(t & 0x1 != 0){            if(first) {                printf("%d", t);                first = false;            }            else                printf(" %d", t);        }        else {            buf[k ++] = t;        }    }    for(int j = 0; j < k; j ++)        printf(" %d", buf[j]);    printf("\n");    return 0;}/**************************************************************    Problem: 1516    Language: C++    Result: Accepted    Time:70 ms    Memory:1412 kb****************************************************************/
   

当输入数组过大时会超时。

方法：

1、以当前位置开始，从左至右找到第一个偶数（p1指向它）

2、以当前位置开始，从左至右找到第一个奇数（p2指向它），将该数暂存到临时变量里

3、将大于等于p1，小于p2之间的数向后移动，将临时变量里的数存到p1的位置

注：最后一个测试用例数量级在100000.用以下方法会超时

int main(){	int n;	scanf("%d", &n);	for(int i = 0; i < n; i ++)		scanf("%d", &buf[i]);	int p1 = 0;	int p2 = 0;	while(p2 < n && p1 < n){		while(buf[p1] % 2 != 0)			p1 ++;		p2 = p1 + 1;		while(buf[p2] % 2 == 0 && p2 < n)			p2 ++;		if(p2 >= n)			break;		int tmp = buf[p2];		for(int i = p2 - 1; i >= p1; i -- )			buf[i + 1] = buf[i];		buf[p1] = tmp; 	}	for(int i = 0; i < n; i ++){		if(i == 0)			printf("%d", buf[i]);		else			printf(" %d", buf[i]);	}	printf("\n");	return 0;}

转载地址：http://wesob.baihongyu.com/