package y2019.Algorithm.array;

/**

 * @ProjectName: cutter-point

 * @Package: y2019.Algorithm.array

 * @ClassName: SortArrayByParity

 * @Author: xiaof

 * @Description: 905. Sort Array By Parity

 * Given an array A of non-negative integers, return an array consisting of all the even elements of A,

 * followed by all the odd elements of A.

 * You may return any answer array that satisfies this condition.

 *

 * Input: [3,1,2,4]

 * Output: [2,4,3,1]

 * The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

 *

 * @Date: 2019/7/3 8:48

 * @Version: 1.0

 */

public class SortArrayByParity {

    public int[] solution(int[] A) {

        //先获取所有偶元素，然后获取所有奇元元素，还有一个方法就是交换前后位置

        //吧所有偶数放到前面，奇数放后面,类似快排

        int index1 = 0, index2 = A.length - 1;

        while(index1 < index2) {

            //遍历起始第一个不是偶数的位置

            while(index1 < A.length && (A[index1] & 1) == 0) {

                index1++;

            }

            //后面往前，找到第一个不是奇数

            while(index2 > 0 && (A[index2] & 1) == 1) {

                index2--;

            }

            //交换位置

            if(index1 < index2 && index1 < A.length && index2 > 0) {

                //交换位置

                int temp = A[index1];

                A[index1] = A[index2];

                A[index2] = temp;

            }

        }

        return A;

    }

    public static void main(String args[]) {

        int A[] = {3,1,2,4};

        SortArrayByParity fuc = new SortArrayByParity();

        System.out.println(fuc.solution(A));

    }

}