奇偶数排序

题目描述：给定一个整数数组，请调整数组的顺序，使得所有奇数位于数组前半部分，所有偶数位于数组后半部分，
要求时间复杂度为O(n).

分析与解法：
最容易想到的办法是从头到尾扫描这个数组，每遇到一个偶数，就把他单独取出来，然后把该偶数后面的所有数往前移动一位，最后把该偶数放入数组的最末尾。因为每遇到一个偶数，需要移动O(N)个数，所以时间复杂故为O(N*N)，不符合题目要求。

事实上，若把奇数看成是小数，偶数看成大数，那么按照题目要求的奇数放在偶数前面，就相当于小数放在大数的前面，有点像快排，就是通过一个主元把整个数组分成大小两个部分，小于主元的小数放在前面，大于主元的放在后面，划分过程有以下两种：

（1）一头一尾两个指针同时往中间扫，如果头指针遇到的数比主元大且尾指针遇到的数比主元小，交换头指针与尾指针
所指的数。

（2）一前一后两个指针同时从左往右扫，如果前指针遇到的数比主元小，则后指针右移一位，然后交换各自指向的数。与这个划分类似，奇偶排序也可以借鉴这两种方法。

解法一：一头一尾指针往中间扫
借鉴划分过程的第一种实现，可以考虑维护两个指针，一个指针指向数组的第一个数，称为头指针，向右移动，另一个指针指向最后一个数，称之为尾指针，向左移动。
这样，两个指针分别从数组的头部和尾部向数组的中间移动，如果第一个指针指向的数是偶数而第二个数指向的书是奇数，就交换这两个数字。因为按照题目要求，最终是为了让奇数排在偶数的前面，所以头指针指向的是奇数，尾指针指向的是偶数，所以当头指针指向的数是偶数且尾指针指向的是奇数时，交换他们指向的数。

#include<stdio.h>

using namespace std;

//判断是否是奇数
bool IsOddNumber(int data)
{
    return data%2 != 0;
}

//奇数和偶数交换
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);
    }
}

int main()
{
    int array[] = {2,1,3,8,7,6,5,4,0};
    int len = sizeof(array)/sizeof(array[0]);
    OddEvenSort(array, len);
    for(int i=0; i<len; ++i)
    {
        cout<<array[i];
    }
    cout<<endl;

    system("pause");
    return 0;
}

解法二：一前一后指针往后扫描法
每一趟排序过程中，选取的主元都会把整个数组排列成一大一小的序列，继而递归完成整个数组的排序。
举个例子如下：
现在对数组A = { 2, 8, 7, 1, 3, 5, 6, 4}进行快速排序，为了表述方便，令p和j指向数组的第一个元素，i指向数组第一个元素的前一个位置，r指向主元，j在前，i在后，双双从左向右移动。

（1）j指向元素2时，i++后也指向元素2，2与2互换不变；

（2）j继续后移，直到指向了元素1，1<=4，i++,i指向8，故j所指元素1与i所指元素8互换
（3）j继续后移，指到了元素3，3<=4, i++, i指向7，故j所指元素3与i所指元素7互换
（4）j一路后移，没有遇到比主元4小的元素；

（5）执行交换A[i+1]与A[r]，即8与4交换，所以最终数组变成下图所示形式。

至此，快排第一次完成，4把数组分成了两个部分，前半部分是2，1，3；后半部分是7，5，6，8；最终递归对上述两部分进行排序。

借鉴划分过程的第二种实现，可以考虑维护两个指针i,j，一个指针指向数组的第一个数的前一个位置，称为后指针i，向右移动，另一个指针指向第一个数，称之为前指针j，向右移动，且前指针先向右移动。前指针j和后指针i向右移动的过程中，如果前指针j指向的数是奇数，
则令后指针i向右移动一位，然后交换i，j两指针指向的元素。
按照题目的要求，是让奇数排在偶数的前面，所以后指针i指向的数是奇数，前指针j指向的数是偶数，当j指针指向奇数时，i++，然后交换i，j两指针指向的元素。

#include<stdio.h>

using namespace std;

//判断是否是奇数
bool IsOddNumber(int data)
{
    return data%2 != 0;
}

//奇数和偶数互换
void OddEvenSort(int data[], int lo, int hi)
//lo--起始位置；hi--字符串最后一个元素位置
{
    int i = lo-1;
    for(int j = 0; j<hi; j++)
    {
        //data[j]指向奇数，交换
        if(IsOddNumber(data[j]))
        {
            i = i+1;
            swap(data[i], data[j]);
        }
    }
    swap(data[i+1], data[hi]);
}
int main()
{
    int array[] = {2,1,3,8,7,6,5,4,0};
    int len = sizeof(array)/sizeof(array[0]);
    OddEvenSort(array, 0, len-1);
    for(int i=0; i<len; ++i)
    {
        cout<<array[i]<<" ";
    }
    cout<<endl;

    system("pause");
    return 0;
}