算法-调整数组顺组使奇数位于偶数前面

题目： 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，偶数位于数组的后半部分。

解题思路： 比如我们有一个这样的数组：

这里写图片描述

数组的长度为10，最后能够实现前面4个数字是奇数，后面6个数字是偶数就好了，前面奇数的排序后后面偶数的排序没有要求，比如：

这里写图片描述

为啥数组里面有两个2呢？这是为了后面介绍是更方便的说明指针如何移动。

为了实现这个任务，一个最简单、粗暴、直接的方法就是从头遍历数组，如果发现是偶数，就拿出这个数并把该数字后面的元素全部向前移动一位，把这个数放到数组的最后一位。

这里写图片描述

由于我们并不知道数组中有几个奇数，有几个偶数，所以我们不得不遍历整个数组，所以这个算法的时间复杂度为O（n^2）

好在我们有更好的方式解决这个问题，管理两个指针p1和p2，p1初始位置指向数组中第一个数，p2初始位置指向数组中最后一个数，如果恰好p1指向地址内的是偶数，p2指向的地址内是奇数，那么就交换数值，移动指针，做下一次判断。举个例子：

这里写图片描述

p1指向0，p2指向9，两个数值交换，并且p1向后走1，p2向前走1；此时p1指向2，p2指向8，8就是偶数不需要交换，所以p1不动（等待p2指向奇数和它交换），p2向前走一步；此时p2指向7，两个数值交换并且p1向后走1，p2向前走1，重复上面的步骤：

这里写图片描述

此时p1指向3，p2指向4，不需要交换并且p1向后走1，p2向前走1：

这里写图片描述

p1跑到p2的后面了，表明所有的奇数都在偶数的前面了。

我们从上面的例子可以总结出指针移动的一些规律： p1只向后走，p2只向前走，其p1在p2后面时结束； 每次数值交换后p1，p2各走一步； p1指向偶数时如果p2满足条件则交换，不满足则保持不动，p2同理。 根据上面的分析，我们就可以写代码了。

代码实现

void ReorderOddEven(int *pData, unsigned int length)
{
    if(pData == NULL || length == 0)
        return;

    int *pBegin = pData;
    int *pEnd = pData + length - 1;

    while(pBegin < pEnd)
    {
        while(pBegin < pEnd && (*pBegin & 0x1) != 0)
            pBegin ++;

        while(pBegin < pEnd && (*pEnd & 0x1) == 0)
            pEnd --;

        if(pBegin < pEnd)
        {
            int temp = *pBegin;
            *pBegin = *pEnd;
            *pEnd = temp;
        }
    }
}

1.显然所有的操作都应该有一个大前提，p1（pBegin）在p2（pEnd）的前面：while(pBegin < pEnd)，由于数组是连续存储，后面的地址一定比前面的大，代码就是在利用这个特点控制何时终止。 2.代码判断奇偶数：0x1—00000001，按位与操作。 3.循环内if判断的作用：显然两个指针从while退出之后，pBegin指向奇数，pEnd指向偶数，但是到了最后一步，就不能再交换了。

这里写图片描述