《剑指offer》 第21题 调整数组顺序使奇数位于偶数前

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

思路1：

创建一个辅助数组，原数组扫一轮，新数组装一轮。因此时间复杂度 O(n)，空间复杂度 O(n)，利用空间换时间。

public class Solution {
    public void reOrderArray(int [] array) {
        if(array.length==0||array.length==1)
            return;
        int oddCount=0;//记录奇数个数
        int oddBegin=0;
        int[] newArray = new int[array.length];
        for(int i=0;i<array.length;i++){
            if((array[i]&1)==1) 
                oddCount++;
        }
        for(int i=0;i<array.length;i++){
            if((array[i]&1)==1) 
                newArray[oddBegin++]=array[i];  //这是偶数的装填
            else newArray[oddCount++]=array[i]; //奇数从oddcount++开始装
        }
        for(int i=0;i<array.length;i++){
            array[i]=newArray[i];//数组复制过去
        }
    }
}

思路2：

冒泡排序的思想 时间复杂度是O(n^2) 每次都让一个偶数移动到最右侧

public class Solution {
    public void reOrderArray(int [] array) {
         for(int i=0;i<array.length-1;i++)
            for(int j=0;j<array.length-i-1;j++){//每次都找一个奇偶相邻的进行交换
                if(array[j]%2==0 && array[j+1]%2==1){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
    }
}

思路3：

插入排序的思想 时间复杂度是O(n^2) 因为需要保证偶数直接相对位置不变，所以是逐个进行交换，否则还有优化空间

public class Solution {
    public void reOrderArray(int [] array) {
        //相对位置不变，稳定性
        //插入排序的思想
        int m = array.length;
        int k = 0;//记录已经摆好位置的奇数的个数
        for (int i = 0; i < m; 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++;
            }
        }
    }
}

总结：

本题和offer书上不一致，书上没有要求稳定，因此采用了哨兵，而本题要求稳定，所以有些算法不能使用。（解法不止总结出来的3种）