微软面试题解析：调整数组顺序使奇数位于偶数前面（数组）

微软面试题解析：调整数组顺序使奇数位于偶数前面（数组）2014-12-24题目：

输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O（n）。

分析：

只需要设置头尾两个指针遍历就可以了，前面遇到偶数记下来，后面遇到奇数记下来，交换，知道后面的指针小于前面的指针。

实现如下：

#include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<vector>using namespace std;void dodata（int* rd, const int num）{if（num <= 0） return;int ieven = num-1, iodd = 0;while（ieven > iodd）{if（rd[iodd] %2 == 1）{iodd ++;continue;} if（rd[ieven]%2 == 0）{ieven --;continue;}int t = rd[iodd];rd[iodd] = rd[ieven];rd[ieven] = t;iodd ++;ieven --;}}int main（）{int inter[10] = {1,2,3,4,5,6,7,8,9,10};dodata（inter, 10）;int i = 0;while（i < 10）{cout << inter[i++] << ",";}cout << endl;return 0;}

编译：

g++ test.cpp -o test

执行：

./test

运行结果为：（输入是：1,2,3,4,5,6,7,8,9,10）

1,9,3,7,5,6,4,8,2,10,

作者：csdn博客 hhh3h