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

题目描述

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

原地进行

采用类似插入排序的思想, k记录前面全是奇数的最后位置

1. 搜寻到奇数
2. 依次两两交换该奇数和前面的其他数 (这样的交换不会改变次序)

   //空间O(1) 时间O(nlogn)?
   public class Solution {
    public void reOrderArray(int [] array) {
        int k = 0;
        int len = array.length;
        for(int i = 0; i < len; i++){
            if(array[i] % 2 == 1){
                int j = i;
                while(j > k){
                    int tmp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = tmp;
                    j--;
                }
                k++;
            }
        }
    }
   }
   

非原地进行

1. 将奇数和偶数分别记录进一个新的数组
2. 将这两个奇偶数组依次再填入旧数组(这里可以使用System.arraycopy())

   public class Solution {
    public void reOrderArray(int [] array) {
        int[] a = new int[array.length];
        int[] b = new int[array.length];
        int j = 0;
        int k = 0;
        for(int num : array){
            if(num % 2 == 0){
                b[k++] = num;
            }else {
                a[j++] = num;
            }
        }
        for(int i = 0; i < j; i++){
            array[i] = a[i];
        }
        for(int i = 0; i < k; i++){
            array[i + j] = b[i];
        }
    }
   }