《剑指offer》第二十一题：调整数组顺序使奇数位于偶数前面（附牛客网代码）

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

#include <cstdio>

void Reorder(int* pData, unsigned int length, bool (*func)(int));
bool isEven(int n);

// ====================方法一====================
void ReorderOddEven_1(int* pData, unsigned int length)
{
    //鲁棒性检测
    if (pData == nullptr || length == 0)
        return;

    //主要思路：指针1寻找前半部分的偶数,指针2寻找后半部分的奇数,然后交换
    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;
        }
    }
}

// ====================方法二====================
void ReorderOddEven_2(int* pData, unsigned int length)
{
    Reorder(pData, length, isEven);
}

void Reorder(int* pData, unsigned int length, bool (*func)(int)) //函数地址
{
    if (pData == nullptr || length == 0)
        return;

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

    if (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 & 0x1) == 0;
}

// ====================测试代码====================
void PrintArray(int numbers[], int length)
{
    if (length < 0)
        return;

    for (int i = 0; i < length; ++i)
        printf("%d	", numbers[i]);

    printf("
");
}

void Test(const char* testName, int numbers[], int length)
{
    if (testName != nullptr)
        printf("%s begins:
", testName);

    int* copy = new int[length];
    for (int i = 0; i < length; ++i)
    {
        copy[i] = numbers[i];
    }

    printf("Test for solution 1:
");
    PrintArray(numbers, length);
    ReorderOddEven_1(numbers, length);
    PrintArray(numbers, length);

    printf("Test for solution 2:
");
    PrintArray(copy, length);
    ReorderOddEven_2(copy, length);
    PrintArray(copy, length);

    delete[] copy;
}

void Test1()
{
    int numbers[] = { 1, 2, 3, 4, 5, 6, 7 };
    Test("Test1", numbers, sizeof(numbers) / sizeof(int));
}

void Test2()
{
    int numbers[] = { 2, 4, 6, 1, 3, 5, 7 };
    Test("Test2", numbers, sizeof(numbers) / sizeof(int));
}

void Test3()
{
    int numbers[] = { 1, 3, 5, 7, 2, 4, 6 };
    Test("Test3", numbers, sizeof(numbers) / sizeof(int));
}

void Test4()
{
    int numbers[] = { 1 };
    Test("Test4", numbers, sizeof(numbers) / sizeof(int));
}

void Test5()
{
    int numbers[] = { 2 };
    Test("Test5", numbers, sizeof(numbers) / sizeof(int));
}

void Test6()
{
    Test("Test6", nullptr, 0);
}

int main(int argc, char* argv[])
{
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();

    return 0;
}

分析：两个指针进行操作，将函数模块化，传入函数地址。

---

牛客网要求数组中奇数和奇数，偶数和偶数之间的相对位置不变，因此原方法不可以用。

方法1：采用了冒泡排序的思想，更改if判断条件实现算法。时间复杂度O(nlogn)，空间复杂度O(1)。

方法2：还可以用空间换时间，使用时间复杂度为O(2n)，空间复杂度为O(n)的算法。

1.遍历容器保存并擦除array.erase(even)所有偶数到新容器；

2.将新容器的值压入原容器；

3.删除了新创建的容器，但是为什么内存占用并没有减少。

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        
        int length = (int)array.size();
        if (length <= 0)
            return;
        
        //冒泡排序思路,时间复杂度O(nlogn)
        //邓公，数据结构(C++语言版) Page5
        bool isSorted = false; //排序完成标志
        while (!isSorted) //借助标志位isSorted，可以提前退出
        {
            isSorted = true; //假设排序完成
            for (int i = 1; i < length; ++i) //从左到右检查
            {
                //当array[i]为奇数且array[i-1]为偶数时交换
                if ((array[i-1] & 0x1) == 0 && (array[i] & 0x1) == 1)
                {
                    int temp = array[i - 1];
                    array[i - 1] = array[i];
                    array[i] = temp;
                    isSorted = false; //整体排序不能保证，清除标志位
                }
            }
            --length; //末位元素已经就位，缩短排序序列长度
        }
    }
};

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        //牛客网，高赞答案walter52
        vector<int> arrayEven; //存放偶数的容器
        vector<int>::iterator vBegin, vEnd;
        vBegin = array.begin();
        vEnd = array.end(); //因为容器中删除了数据，所以每次都要重新获取
        
        //搜寻偶数并保存，从原数组删除
        for (; vBegin != array.end();)
        {
            //如果是偶数
            if ((*vBegin & 0x01) == 0)
            {
                arrayEven.push_back(*vBegin); //压入新容器
                vBegin = array.erase(vBegin); //删除原数据
            }
            else 
                ++vBegin;
        }
        
        vBegin = arrayEven.begin();
        vEnd = arrayEven.end();
        //新容器数据压入到原容器末尾
        for (; vBegin != vEnd; vBegin++)
        {
            array.push_back(*vBegin);
        }
        arrayEven.clear(); //加不加这句话好像内存占用一样，难顶
    }
};