算法1
双指针扫描 $O(n)$
用两个指针l,r,一个从前往后指知道遇到第一个偶数,一个从后往前指直到遇到第一个奇数,两指针指向相同时退出循环
C++ 代码
class Solution {
public:
void reOrderArray(vector<int> &array) {
int n=array.size();
int l=0,r=n-1;
while(l<r)
{
while(l<r&&array[l]%2==1)l++;
while(l<r&&array[r]%2==0)r--;
if(l<r)swap(array[l],array[r]);
}
for(int i=0;i<n;i++)//保证奇数,偶数的大小顺序不变
{
if(array[i]>array[i+1]&&array[i]%2==1&&array[i+1]%2==1)
swap(array[i],array[i+1]);
if(array[i]>array[i+1]&&array[i]%2==0&&array[i+1]%2==0&&i+1<n)
swap(array[i],array[i+1]);
}
}
};