思路1：根据双指针对撞指针的思路，定义一个左指针从数组前端开始遍历，定义一个右指针从后端开始遍历，这时候有四种情况

1. 左奇右偶：这种情况需要将其位置交换，将偶数提前，奇数后移
2. 左奇右奇：这种情况需要右指针遍历下一个
3. 左偶右偶：这种情况需要左指针遍历下一个
4. 左偶右奇：这种情况需要左指针和右指针分别遍历下一下

当左指针遇到右指针时排序完成

class Solution {public int[] sortArrayByParity(int[] nums) {int left = 0;int right = nums.length - 1;while(left < right){if(nums[left] % 2 == 0 && nums[right] % 2 == 0){left++;}else if(nums[left] % 2 == 0 && nums[right] % 2 == 1){left++;right--;}else if(nums[left] % 2 == 1 && nums[right] % 2 == 1){right--;}else{int temp = nums[left];nums[left] = nums[right];nums[right] = temp;}}return nums;}
}

思路二：优化解法，定义一个指针（下标）从头开始遍历，定义一个指针（下标）指向数组最后一个数，当左指针遇见奇数则将其与右指针指向的数做交换，右指针自减，左指针不变，这样右指针右边的数一定是奇数；继续判断左指针指向的数是否为奇数，若为奇数，则与右指针指向的数做交换，右指针再次自减，有点类似于滑动窗口，右指针右边的数全为奇数；若左指针为偶数，则左指针自加，右指针不变

当左指针与右指针相撞时，遍历结束

举例

        1 4 7 3 2 9 5  8 红色加粗数字即现在左指针所指的数字，黑色加粗数字即为右指针指向的数字，左指针现在指向的数为奇数，交换左右指针的数字，并右指针自减，左指针不变

        8 4 7 3 2 9 5 1  左指针所指为偶数，左指针自加，右指针不变

        8 4 7 3 2 9 5 1  

        8 4 7 3 2 9 5 1

        8 4 5 3 2 9 7 1

        8 4 9 3 2 5 7 1

        8 4 2 3 9 5 7 1

        8 4 2 3 9 5 7 1 当这时左指针和右指针相撞，遍历结束，排序也结束

Java实现：

class Solution {public int[] sortArrayByParity(int[] nums) {int tempEnd = nums.length - 1;for(int i = 0;i < tempEnd;i++){if(nums[i] % 2 == 1){int temp = nums[i];nums[i--] = nums[tempEnd];nums[tempEnd--] = temp;}}return nums;}
}