LeetCode/solutions/905. Sort Array By Parity.md

# [905. Sort Array By Parity](https://leetcode.com/problems/sort-array-by-parity/)

# 思路

题目要求将一个数组中的偶数放在奇数前面。很简单用两个指针i和j就可以了，分别表示`a[0, 1, ..., i-1]`全部为偶数而`a[j+1, j+2, ..., n-1]`全部为奇数，所以i和j初始分别为0和n-1。然后就是循环，每个循环内部：
* 1. 如果`A[i]`为奇数那么交换`A[i]`和`A[j]`然后将`j--`，否则`i++`；
* 2. 如果`A[j]`为偶数那么交换`A[i]`和`A[j]`然后将`i++`，否则`j--`；

上面的1和2单独使用也是可以的。

另外STL中`partition`所干的就是此题要求的事，它会使所有使给定比较函数返回 true 的元素放在返回false的前面，所以我们只需要自定义比较函数就可以了。

# C++
``` C++
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        int i = 0, j = A.size() - 1;
        
        // 如果问题条件变一下, 例如将能被3整除的放在不能整除的前面, 我们只需要改这一行代码
        # define CONDITION(i) (A[i] & 1)
        
        while(i < j){
            if(i < j && CONDITION(i)) swap(A[i], A[j--]);
            else i++;
            
            if (i < j && !CONDITION(j)) swap(A[i++], A[j]);
            else j--;
        }
        return A;
    }
};
```
## 直接使用STL中的partition
``` C++
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        partition(A.begin(), A.end(), [](int a) { return !(a & 1);});
        return A;
    }
};
```