2.6 奇偶排序
题目描述
输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
分析与解法
最容易想到的办法是从头扫描这个数组，每碰到一个偶数，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，然后把该偶数放入这个空位。由于每碰到一个偶数，需要移动O(n)个数字，所以这种方法总的时间复杂度是O(n^2)，不符合题目要求。
事实上，若把奇数看做是小的数，偶数看做是大的数，那么按照题目所要求的奇数放在前面偶数放在后面，就相当于小数放在前面大数放在后面，联想到快速排序中的partition过程，不就是通过一个主元把整个数组分成大小两个部分么，小于主元的小数放在前面，大于主元的大数放在后面。
而partition过程有以下两种实现：
- 一头一尾两个指针往中间扫描，如果头指针遇到的数比主元大且尾指针遇到的数比主元小，则交换头尾指针所分别指向的数字；
- 一前一后两个指针同时从左往右扫，如果前指针遇到的数比主元小，则后指针右移一位，然后交换各自所指向的数字。
类似这个partition过程，奇偶排序问题也可以分别借鉴partition的两种实现解决。
为何？比如partition的实现一中，如果最终是为了让整个序列元素从小到大排序，那么头指针理应指向的就是小数，而尾指针理应指向的就是大数，故当头指针指的是大数且尾指针指的是小数的时候就不正常，此时就当交换。
解法一
借鉴partition的实现一，我们可以考虑维护两个指针，一个指针指向数组的第一个数字，我们称之为头指针，向右移动；一个指针指向最后一个数字，称之为尾指针，向左移动。
这样，两个指针分别从数组的头部和尾部向数组的中间移动，如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，我们就交换这两个数字。
因为按照题目要求，最终是为了让奇数排在数组的前面，偶数排在数组的后面，所以头指针理应指向的就是奇数，尾指针理应指向的就是偶数，故当头指针指向的是偶数且尾指针指向的是奇数时，我们就当立即交换它们所指向的数字。
思路有了，接下来，写代码实现：
//判断是否为奇数
bool IsOddNumber(int data)
{
return data & 1 == 1;
}
//交换两个元素
void swap(int* x, int* y)
{
int temp = *x;
*x = *y;
*y = temp;
}
//奇偶互换
void OddEvenSort(int *pData, unsigned int length)
{
if (pData == NULL || length == 0)
return;
int *pBegin = pData;
int *pEnd = pData + length - 1;
while (pBegin < pEnd)
{
//如果pBegin指针指向的是奇数，正常，向右移
if (IsOddNumber(*pBegin))
{
pBegin++;
}
//如果pEnd指针指向的是偶数，正常，向左移
else if (!IsOddNumber(*pEnd))
{
pEnd--;
}
else
{
//否则都不正常，交换
swap(*pBegin, *pEnd);
}
}
}本方法通过头尾两个指针往中间扫描，一次遍历完成所有奇数偶数的重新排列，时间复杂度为O(n)。
解法二
我们先来看看快速排序partition过程的第二种实现是具体怎样的一个原理。
partition分治过程，每一趟排序的过程中，选取的主元都会把整个数组排列成一大一小的序列，继而递归排序完整个数组。如下伪代码所示：
PARTITION(A, p, r)
1 x ← A[r]
2 i ← p - 1
3 for j ← p to r - 1
4 do if A[j] ≤ x
5 then i ← i + 1
6 exchange A[i] A[j]
7 exchange A[i + 1] A[r]
8 return i + 1举个例子如下：现要对数组data = {2, 8,7, 1, 3, 5, 6, 4}进行快速排序，为了表述方便，令i指向数组头部前一个位置，j指向数组头部元素，j在前，i在后，双双从左向右移动。
① j 指向元素2时，i 也指向元素2，2与2互换不变
i p/j
2 8 7 1 3 5 6 4(主元)② 于是j 继续后移，直到指向了1，1