力扣对应题目链接：LCR 139. 训练计划 I - 力扣（LeetCode）
牛客对应题目链接：调整数组顺序使奇数位于偶数前面(二)_牛客题霸_牛客网 (nowcoder.com)
核心考点：数组操作，排序思想的扩展使用。
一、《剑指Offer》对应内容
二、分析题目
按照题目意思，其实跟快排的思路一致，我们只需要定义双指针 left 和 right 分别指向数组的第一个元素和最后一个元素，接着让 left 往后遍历，直到找到前半部分的第一个偶数，让 right 向前遍历，直到找到后半部分的第一个奇数，然后交换 left 和 right 所在位置的数即可，遍历后的数组就是我们要的答案。
扩展：假设现在新增需求，需要保证奇数和奇数，偶数和偶数之间的相对位置不变。
解决这个问题的方法也比较多，这里我们采用较优方式解决一下，借鉴插入排序的思想。做法：从左向右遍历，每次遇到的都是最前面的奇数，将该奇数之前的内容（偶数序列）整体后移一个位置，腾出位置后，将奇数保存在它将来该在的位置，因为我们是从左往右放的，没有跨越奇数，所以一定是相对位置不变的。
三、代码（C++）
1、方法一（头尾双指针法）
//写法一 class Solution { public: vector<int> trainingPlan(vector<int>& actions) { int n=actions.size(); int left=0, right=n-1; while(left<right) { while(left<right && actions[left]%2==1) left++; while(left<right && actions[right]%2==0) right--; if(left<right) swap(actions[left], actions[right]); } return actions; } }; //写法二 class Solution { public: vector<int> trainingPlan(vector<int>& actions) { int n=actions.size(); int left=0, right=n-1; while(left<right) { while(left<right && (actions[left]&1)) left++; while(left<right && !(actions[right]&1)) right--; if(left<right) swap(actions[left], actions[right]); } return actions; } };
//牛客网 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型vector * @return int整型vector */ vector<int> reOrderArrayTwo(vector<int>& array) { int n=array.size(); int left=0, right=n-1; while(left<right) { while(left<right && array[left]%2==1) left++; while(left<right && array[right]%2==0) right--; if(left<right) swap(array[left], array[right]); } return array; } };
2、方法二（插入法-保证相对顺序不变）
class Solution { public: vector<int> trainingPlan(vector<int>& actions) { int n=actions.size(); int k=0; //记录已排好序的奇数个数 for(int i=0; i<n; i++) { if(actions[i]%2==1) { int tmp=actions[i]; //先将当前奇数保存起来 int j=i; while(j>k) { actions[j]=actions[j-1]; j--; } actions[k++]=tmp; //将奇数保存在它将来该在的位置 } } return actions; } };
