思路
两次遍历,第一次把奇数加到list中,第二次把偶数加到list中,时间复杂度为O(n)。
利用类似于插入排序的方法,但时间复杂度为O(n^2)。
代码
import java.util.ArrayList;
import java.util.List;
public class Solution {
public void reOrderArray(int[] array) {
List l=new ArrayList();
for(int i=0;i<=array.length-1;i++){
if(array[i]%2!=0){
l.add(array[i]);
}
} for(int i=0;i<=array.length-1;i++){
if(array[i]%2==0){
l.add(array[i]); }
}
for(int i=0;i<=l.size()-1;i++){
array[i]=(int)l.get(i);
}
}
}
如果不能开僻额外的空间,可以尝试有类似于冒泡排序的方法,如果当前的值为偶数,后一个值为奇数,则两个数对换位置:
public class Solution {
public void reOrderArray(int [] array) {
for(int i=0; i < array.length; i++){
for(int j=0; j<array.length-1; j++){
if(array[j] % 2 == 0 && array[j+1] % 2 != 0){
int temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
}
}
}
}
}