剑指offer - 调整数组顺序使奇数位于偶数前面

题目

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

分析

• 思路1

如果不考虑时间复杂度，则最简单的思路应该是从头扫描这个数组，每碰到一个偶数，拿出这个数，并把位于这个数字后面的所有数字往前挪动一位。挪动之后在数组的末尾有一个空位，这时把该偶数放入这个空位。由于每碰到一个偶数就需要移动O(n)个数字，因此总的时间复杂度是O(n²)

• 思路2

其实扫描这个数组的时候，如果发现有偶数出现在奇数的前面，则交换奇偶数的位置即可

因此，我们可以维护两个指针：

• 第一个指针初始化时指向数组的第一个数字，它只向后移动；
• 第二个指针初始化时指向数组的最后一个数字，它只向前移动。

在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数，并且第二个指针指向的数字是奇数，则交换两个数字

分析具体例子

如：输入数组{1，2，3，4，5}来分析这种思路

• 在初始化时，把第一个指针指向数组的第一个数字1，而把第二个指针指向最后一个数字5，如图（a）所示。

• 第一个指针指向的数字1是奇数，不需要处理，我们把第一个指针向后移动，直到碰到一个偶数2。此时第二个指针已经指向了奇数，因此不需要移动。此时两个指针指向的位置如图（b）所示。这时候我们发现偶数2位于奇数5的前面，符合交换条件，也是交换这两个指针指向的数字，如图（c）

• 接下来我们继续向后移动第一个指针，直到碰到下一个偶数4，并向前移动第二个指针，直到碰到第一个奇数3，如图（d）所示。

这时我们发现第二个指针已经在第一个指针的前面了，表示所有的奇数都已经在偶数的前面了。此时的数组是{1，5，3，4，2}，的确是奇数位于数字的前半部分而偶数位于数组的后半部分

download.png

算法实现

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》