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

输入：
每个输入文件包含一组测试案例。
对于每个测试案例，第一行输入一个n，代表该数组中数字的个数。
接下来的一行输入n个整数。代表数组中的n个数。

输出：
对应每个测试案例，
输入一行n个数字，代表调整后的数组。注意，数字和数字之间用一个空格隔开，最后一个数字后面没有空格。

样例输入：
5
1 2 3 4 5
样例输出：
1 3 5 2 4


第一种解法：遍历。两重for循环。判断奇数偶数，然后交换位置。
第二种解法：使用两个指针分别指向首尾地址，然后从前向后找偶数，从后向前找奇数，交换位置（可以看做时快排）。符合书上要求，不符合这题（按原有顺序排列）。
如样例：按照书上思路求出的是 1 5 3 4 2；
书上：
/* ***********************************************
Author        :bo-jwolf
Created Time  :2015年02月11日 星期三 19:14:45
File Name     :1516.cpp
************************************************ */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

const int MAX = 1000005;
int num[ MAX ], number[ MAX ];

int n;

void Reorder( int *pData, int length, bool (*func)(int) ){
	if( pData == NULL ?? length <= 0 )
		return;
	int *pBegin = pData + 1;
	int *pEnd = pBegin + length;
	int i = 1, j = length;
	while( pBegin <= pData + length  && i <= j &&func( *pBegin ) ){
		number[ i++ ] = *pBegin;
		cout << *pBegin << endl;
		pBegin++;
	}
	while( pEnd >= pData + 1 && j > i && !func( *pEnd ) ){
		number[ j-- ] = *pEnd;
		pEnd--;
	}
}

bool isEven( int n ){
//	return (n & 1) == 0;
	return (n & 1 ) == 0;
}

void ReorderOddEven( int *pData, unsigned int length ){
	Reorder( pData, length, isEven );
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while( scanf( "%d", &n ) != EOF ){
		memset( num, 0, sizeof( num ) );
		for( int i = 1; i <= n; ++i ){
			scanf( "%d", &num[ i ] );
		}
		ReorderOddEven( num, n );
		for( int i = 1; i < n; ++i ){
			printf( "%d ", number[ i ] );
		}
		printf( "%d\n", number[ n ] );
	}
    return 0;
}

简化：

#include <vector>
#include <cstdio>
#include <iostream>
using namespace std;

int main() {
    //freopen("1516.input", "r", stdin);
    int n;
    vector<int> v;
    while (scanf("%d", &n) != EOF) {
        v.resize(n);
        for (int i = 0; i < n; ++i) {
            scanf("%d", &v[i]);
        }
        int s = 0, e = n - 1, t;
        while (s < e) {
            while ((v[s] & 1) && s < e) ++s;
            while (!(v[e] & 1) && s < e) --e;
            t = v[s];
            v[s] = v[e];
            v[e] = t;
        }
        for (int i = 0; i < n; ++i) {
            (i == n - 1) ? printf("%d\n", v[i]) : printf("%d ", v[i]);
        }
    }
    return 0;
}

第三种解法：遍历一次，找到奇数则保留，找到偶数就插入到所以奇数长后面。有两种写法，（方案A）一种是可以使用临时数组，（方案B）一种则只能使用原有空间；

第一种写法（方案A）:100ms

/* ***********************************************
Author        :bo-jwolf
Created Time  :2015年02月11日 星期三 20:24:56
File Name     :1516a.cpp
************************************************ */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

const int MAX = 100005;
int num[ MAX ], number[ MAX ];

bool isOdd( int n ){
	return ( n & 1 ) == 1;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
	int n; 
	while( scanf( "%d", &n ) != EOF ){

		memset( number, 0, sizeof( number ) );
		for( int i = 1; i <= n; ++i )
			scanf( "%d", &num[ i ] );

		int k1 = 1, k2 = n;
		for( int i = 1; i <= n; ++i ){
			if( isOdd(num[ i ] ) )
				number[ k1++ ] = num[ i ];
		}
		for( int i = n; i >= 1; --i ){
			if( !isOdd( num[ i ] ) )
				number[ k2-- ] = num[ i ];
		}
		for( int i = 1; i < n; ++i ){
			printf( "%d ", number[ i ] );
		}
		printf( "%d\n", number[ n ] );
    }
	return 0;
}

第二种写法（方案B):70ms

/* ***********************************************
Author        :bo-jwolf
Created Time  :2015年02月11日 星期三 20:24:56
File Name     :1516a.cpp
************************************************ */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

bool isOdd( int n ){
	return ( n & 1 ) == 1;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
	int n, temp;
    vector<int> V;
	queue< int > Q;   
	while( scanf( "%d", &n ) != EOF ){
		V.resize( n+1 );
		V.clear();
		for( int i = 1; i <= n; ++i ){
			scanf( "%d", &V[ i ] );
		}

		int t = 0;
		for( int i = 1; i <= n; ++i ){
			if( isOdd(V[ i ] ) )
				V[ i - t ] = V[ i ];
			else{
				t++;
				Q.push( V[ i ] );
			}
		}
		for( int i = n - t+1; i <= n; ++i ){
			V[ i ] = Q.front();
			Q.pop();
		}
		for( int i = 1; i < n; ++ i ){
			printf( "%d ", V[ i ] );
		}
		if( n )
		printf( "%d\n",V[ n ] );
	}
	return 0;
}