java-调整数组顺序使奇数位于偶数前面

题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

解题思路
方法一：利用两个list存放奇数和偶数，之后将结果复制到原数组
方法二：遍历原数组，偶数不管，遇到奇数之后前插。记录当前奇数的最右下标

java代码

import java.util.*;
public class Solution {
    public void reOrderArray(int [] array) {//8ms 9560KB
        int i=0;//记录奇数的位置
        for(int j=0;j<array.length;j++){
            if(array[j]%2!=0){//偶数不管，遇见奇数直接前插
                int tmp=array[j];
                for(int k=j-1;k>=i;k--){//（涉及到之前的元素右移）
                    array[k+1]=array[k];
                }
                array[i++]=tmp;
            }
        }
    }
    public void reOrderArray1(int [] array) {//11ms 9632KB 
        //利用辅助数组
        ArrayList<Integer> list1=new ArrayList<>();
        ArrayList<Integer> list2=new ArrayList<>();
        for(int num:array){
            if(num%2==0){
                list2.add(num);
            }
            else{
                list1.add(num);
            }
        }
        for(int i=0;i<list1.size();i++){
            array[i]=list1.get(i);
        }
        for(int i=0;i<list2.size();i++){
            array[i+list1.size()]=list2.get(i);
        }
    }
}