输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

方法一：借助队列

/*
思路：创建两个队列，奇队列和偶队列。
扫描数组，若是奇数，则进入奇队列；若是偶数，则进入偶队列；
完成之后奇队列先出，偶队列后出
*/
void reOrderArray_1(vector<int>& array)
{
    if (array.size() == 0)
        return;
    queue<int> odd;
    queue<int> even;

    for (int i = 0; i < array.size(); i++)
    {
        if (array[i] % 2 != 0)
            odd.push(array[i]);
        else if (array[i] % 2 == 0)
            even.push(array[i]);
        else
            return;
    }

    int i = 0;
    while (!odd.empty())
    {
        int oddNumber = odd.front();
        odd.pop();
        array[i] = oddNumber;
        i++;
    }
    while (!even.empty())
    {
        int evenNumber = even.front();
        even.pop();
        array[i] = evenNumber;
        i++;
    }
}

方法2：类似于插入排序

/*
思路：类似于插入排序：
遍历数组，若遍历得到奇数，则判断之前是否为偶数，若是，插入排序到第一个偶数之前。
*/
bool isOdd(int n)
{
    if (n & 0x1) //位与运算判断是否为奇数，运算更快
        return true;
    else 
        return false;
}
void reOrderArray_2(vector<int>& array)
{
    if (array.empty())
        return;
    int length = array.size();

    int i = 0;
    while (i<length)
    {
        //若第i位为奇数，则往前遍历，有偶数则插入到第一个偶数之前
        if (isOdd(array[i]))
        {
            int j = i - 1,tmp=array[i];
            if (j >= 0)
            {
                while (!isOdd(array[j]) && j >= 0)
                {
                    array[j + 1] = array[j];
                    j--;
                }
                array[j + 1] = tmp;
            }

        }
        i++;
    }
}