给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
你可以返回任何满足上述条件的数组作为答案。
示例：
输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
提示：
2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000
思路：
两个指针，分别指向奇数位和偶数位，已经符合条件的项的末尾地址
遍历数组：
假设遇到偶数位上的偶数，或奇数位上的奇数，则相应指针后移
假设遇到偶数位上的奇数，或奇数位上的偶数，则交换当前位和对应指针位置元素。再从当前位重新判断
可能遇到的细节问题：当指针后移的比遍历要快的时候，要注意跳过一些已经排好位置的项
性能分析：
时间复杂度O(n)，空间复杂度O(1)
具体代码：
class Solution {
public void swap(int[] A, int a, int b){
//交换用函数
int t = A[a];
A[a] = A[b];
A[b] = t;
return;
}
public int[] sortArrayByParityII(int[] A) {
int sing = 1;
int doub = 0;
for(int i = 0; i < A.length; i++){
if(A[i] % 2 == 1){ //第i项为奇数
if(i % 2 == 1 && i >= sing){ // 索引也为奇数,且不是前序处理过
sing += 2;
continue;
}
else if(i % 2 == 0){ //索引为偶数
swap(A, sing, i);
sing += 2;
i--;
}
}
else{ //第i项为偶数
if(i % 2 == 1){ //索引为奇数
swap(A, doub, i);
doub += 2;
i--;
}
else if(i % 2 == 0 && i >= doub){ //索引为偶数,且不是前序处理过
doub += 2;
continue;
}
}
}
return A;
}
}
