总结【剑指Offer T21】调整数组顺序使奇数位于偶数前面

一、开辟新数组法

1.分析：用快慢指针遍历数组，慢指针指向最后一个已调整位置奇数，快指针向后遍历，开辟一个新数组保存遍历过程中的偶数，遇到奇数则将其移动到慢指针的下一个位置。
2.代码

void reOrderArray_1(vector<int> &array) {
    vector<int> temp_even;
    int slow,fast,size=array.size();

    for (slow=-1,fast=0; fast<size; ++fast){
        if (array[fast] & 0x1) //若fast指向奇数，将其移动到指定位置
            array[++slow] = array[fast];
        else 
            temp_even.push_back(array[fast]);
    }

    for (fast=0; fast<temp_even.size(); ++fast)
        array[++slow] = temp_even[fast];
}

3.复杂度
时间复杂度：O(n)
空间复杂度：O(n)

二、不开辟新数组：

1.分析：

1. 用两个下标i,j进行遍历;
2. 当i走到偶数时停下，并让j从i的后一个元素开始遍历；(若i走到队尾则循环结束)
3. 若j所指的是偶数则继续前进，j遇到奇数则停下(如果j都没遇到奇数则在队尾停下，结束。)。
4. 此时j所指的是奇数，i所指的是偶数(i到j-1都是偶数)。
5. 则可以用临时变量temp保存j对应的值，然后从j-1开始到i，挨个后移一位。
6. 将temp保存的值插入到i的位置。
   优化：冒泡排序也可以保证相对位置不变，所以用冒泡排序写起来会更方便。

2.代码

    void reOrderArray_2(vector<int> &array) {
        int len = array.size();
        if(len <= 1){ // 数组空或长度为1
            return;
        }

        int i = 0;
        while(i < len){
            int j = i + 1;
            if(array[i]%2 == 0){ // a[i]为偶数，j前进，直到替换
                while(array[j]%2 == 0){ // j为偶数，前进
                    if(j==len-1)// i为偶数，j也为偶数，一直后移到了末尾，证明后面都是偶数
                         return;
                    j++;
                }
                // 此时j为奇数
                int count = j-i;
                int temp = array[i];
                array[i] = array[j];
                while(count>1){
                    array[i+count] = array[i+count-1];//数组后移
                    count--;
                }
                array[i+1] = temp;
            }
            i++;
        }
    }

3.复杂度
时间复杂度：O(n²)
空间复杂度：O(1)