905. Sort Array By Parity（easy）
题目理解：
一个数组中全是非负数，现在要我们把偶数放在前面，奇数放在偶数之后
首先想到的做法：声明一个新的vector，扫描A两遍，第一遍插入偶数，第二遍插入奇数，返回新的vector
可能优化方向：
- 扫描一遍
- 不分配新空间
于是想到了新的做法：用两个指针标记位置，两个指针分别从前往后和从后往前扫描
比较两个指针所指的数据有4种情况：
| 情况 | 对应操作 |
|---|---|
| 前奇后偶 | 交换位置，i向后移，j向前移 |
| 前偶后奇 | 不用交换，i往后移，j往前移 |
| 前后全是偶数 | 不用交换，i往后移 |
| 前后全是奇数 | 不用交换，j往前移 |
其实这种做法的本质就是利用两个指针在O(N)时间里达到了和之前扫描两次同样的效果，并且维护了原数组，就不用再分配新的空间了，这也是一种比较常用的做法。
在实际代码里我对i，j移动的时机做了一些改动，结果是一样的，但是看起来可能更简单，也可以分成四种情况逐一用if...else if来写。
accept代码
class Solution {public: vector<int> sortArrayByParity(vector<int>& A) { int i = 0, j = A.size() - 1; int n = A.size(); while (i < j) { if (A[i] % 2 != 0 && A[j] % 2 != 1) swap(A[i++], A[j--]); if (A[i] % 2 == 0) i++; if (A[j] % 2 == 1) j--; } return A; }};
重点：
- 两个指针