题目
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分
分析
- 思路1
如果不考虑时间复杂度，则最简单的思路应该是从头扫描这个数组，每碰到一个偶数，拿出这个数，并把位于这个数字后面的所有数字往前挪动一位。挪动之后在数组的末尾有一个空位，这时把该偶数放入这个空位。由于每碰到一个偶数就需要移动O(n)个数字，因此总的时间复杂度是O(n2)
- 思路2
其实扫描这个数组的时候，如果发现有偶数出现在奇数的前面，则交换奇偶数的位置即可
因此，我们可以维护两个指针：
- 第一个指针初始化时指向数组的第一个数字，它只向后移动；
- 第二个指针初始化时指向数组的最后一个数字，它只向前移动。
在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数，并且第二个指针指向的数字是奇数，则交换两个数字
分析具体例子
如：输入数组{1，2，3，4，5}来分析这种思路
在初始化时，把第一个指针指向数组的第一个数字1，而把第二个指针指向最后一个数字5，如图（a）所示。
第一个指针指向的数字1是奇数，不需要处理，我们把第一个指针向后移动，直到碰到一个偶数2。此时第二个指针已经指向了奇数，因此不需要移动。此时两个指针指向的位置如图（b）所示。这时候我们发现偶数2位于奇数5的前面，符合交换条件，也是交换这两个指针指向的数字，如图（c）
接下来我们继续向后移动第一个指针，直到碰到下一个偶数4，并向前移动第二个指针，直到碰到第一个奇数3，如图（d）所示。
这时我们发现第二个指针已经在第一个指针的前面了，表示所有的奇数都已经在偶数的前面了。此时的数组是{1，5，3，4，2}，的确是奇数位于数字的前半部分而偶数位于数组的后半部分
算法实现
void RecorderOddEven(int *pData, unsigned int length)
{
if (pData == nullptr || length == 0)
return;
int *pBegin = pData;
int *pEnd = pData + length - 1;
while (pBegin < pEnd) {
// 向后移动pBegin，直到塔指向偶数
while (pBegin < pEnd && (*pBegin & 0x1) != 0) {
pBegin++;
}
// 向前移动pEnd，直到它指向奇数
while (pBegin < pEnd && (*pEnd & 0x1) == 0) {
pEnd--;
}
if (pBegin < pEnd) {
int temp = *pBegin;
*pBegin = *pEnd;
*pEnd = temp;
}
}
}
可扩展的解法
Reorder函数把pData为数组分为两部分
void Reorder(int *pData, unsigned int length, bool(*func)(int))
{
if (pData == nullptr || length == 0)
return;
int *pBegin = pData;
int *pEnd = pData + length - 1;
while (pBegin < pEnd) {
while (pBegin < pEnd && !func(*pBegin)) {
pBegin++;
}
while (pBegin < pEnd && func(*pEnd)) {
pEnd--;
}
if (pBegin<pEnd)
{
int temp = *pBegin;
*pBegin = *pEnd;
*pEnd = temp;
}
}
}
// 判断是不是偶数
bool isEven(int n)
{
return (n & 1) == 0;
}
有了上面两个函数，我们可以很方便的把数组中的所有奇数移到偶数的前面
void RecoderOddEven(int *pData, unsigned int length)
{
Reorder(pData, length, isEven);
}
如果把问题改成将数组中的负数移到非负数的前面，或者把能被3整除的数移到不能被3整除的数的前面，都只需定义新的函数来确定分组的标准，而函数Reorder不需要进行任何改动。也就是说，解耦的好处就是提高了代码的重用性，为功能的扩展提供了便利
参考
《剑指offer》
