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

思路：参考快速排序

• i++往前走碰到偶数停下来，j = i+1
• 若 a[j]为偶数，j++前进，直到碰到奇数
  • a[j]对应的奇数插到a[i]位置，j经过的j-i个偶数依次后移
• 如果j==len-1时还没碰到奇数，证明i和j之间都为偶数了，完成整个移动

class Solution {
public:
    void reOrderArray(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++;
        }
    }
};