922. 按奇偶排序数组 II (opens new window)

1.原地交换

分析：按照奇数索引进行搜索，只要保证奇数索引下都是奇数，那么剩余另一半肯定是偶数。

维护一个一直向右走的偶数指针，只要当前奇数索引下出现偶数，那么把它与偶数指针下的奇数进行交换。空间O(1)，时间O(n)

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int zero=0;
        //只需要保证所有偶数索引都是偶数就可以了
        //换而言之，我们只需要搜索所有奇数位置，把其中的偶数丢到偶数指针即可
        for(int i=1;i<nums.length;i+=2){
            if(nums[i]%2==0){
                while(zero<nums.length&&nums[zero]%2==0)zero+=2;
                if(zero>=nums.length) return nums;
                int swap=nums[zero];
                nums[zero]=nums[i];
                nums[i]=swap;
             	zero+=2;
            }
        }
        return nums;
    }
}