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

方法一:借助队列

/*
思路:创建两个队列,奇队列和偶队列。
扫描数组,若是奇数,则进入奇队列;若是偶数,则进入偶队列;
完成之后奇队列先出,偶队列后出
*/
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++;
    }
}