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

输入描述:

给定无序数组。长度不超过1000000。

输出描述:

所有偶数位于数组的前半部分，所有奇数位于数组的后半部分。如果有多个答案可以输出任意一个正确答案。

备注:

请自觉使用O(n)的算法。