数组元素分割，就是说把整个的数组分成两部分，前半部分具有哪些性质，后半部分具有哪些性质。

题目描述：

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

这里对数组的分块，很容易的就联想到了快速排序中对数组的划分，从开头找一个具有性质2的元素，从结尾找一个具有性质1的元素，然后交换他们。这样整个的进行下去，最后的结果就是前半部分元素都具有性质1，后半部分元素都具有性质2。

直接代码：

void Reorder(vector
     
       &data){	if(data.size() == 0)		return;	int first = 0;	int last = data.size() - 1;		while(first < last)	{		while(first < last && !isEven(data[first]))		{			first++;		}		while(first < last && isEven(data[last]))		{			last++;		}		if(first < last)		{			swap(data[first], data[last]);		}	}}bool isEven(int num){	return (num & 1) == 0;}
     

　　这里的判断奇数与偶数的方法用按位与更快。同时可以在Reorder中传入一个指针函数，用来表明分类的方法。

---

如果现在有另外的一种需求，就是要求分割的两部分的奇数与奇数之间，偶数与偶数之间的顺序保持不变。

这时可以单独的开辟一个额外的空间存储偶数，利用空间换时间。如果不想这样的话，也可以利用插入排序的方式完成这个算法，但是时间复杂度会是O(n²)。

void reOrderArray(vector
     
       &array) {   	int odd = 0;	int i = 0;	int num = array.size();	while(i < num)	{		if(array[i] % 2 != 0)		{			int val = array[i];			int k = 0;			for(k = i; k > odd; k--)			{				array[k] = array[k - 1];			}			array[k] = val;			odd++;		}		++i;	}//while}