剑指0ffer-数组

public class Solution {
    public void reOrderArray(int [] array) {
       //在原数组上处理
        int j;//用于记录当前奇数的索引值
        int k = 0;//用于记录当前排头的奇数个数
        for (int i = 0; i < array.length; i++) {
            if(array[i] % 2 == 1){
                j = i;//说明定位到了奇数
                //再把奇数前面的所有偶数与当前奇数逆次交换，完成重排，但是需要注意的是
                //当前奇数与前面交换的次数由K决定，
                while(j > k){
                    int temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                    j--;
                }
                k++;
            }
        }
    }
}

这个是按照高赞写的，背了下来，啊哈哈，不过有一说一，这个是最坏的是O(n2)?最好的是o(n)，还是用最简单的空间换时间，
新建数组，就铁定是o(n)的复杂度。

        ArrayList<Integer> temp1 = new ArrayList<Integer>();
        ArrayList<Integer> temp2 = new ArrayList<Integer>();
        for (int i = 0; i < array.length; i++) {
            if(array[i] % 2== 0){
                temp1.add(array[i]);
            }else{
                temp2.add(array[i]);
            }
        }
        temp1.addAll(temp2);
        System.out.println(temp1);