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

题目描述

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

这个题目比较简单，首先会联想到使用空间换时间，达到O（N）的时间复杂度与O（N）的空间复杂度。

import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    public static void reOrderArray(int [] array) {
        Queue<Integer> odd = new LinkedList<Integer>();
        Queue<Integer> even = new LinkedList<Integer>();
        //判断，奇数放到奇数队列，偶数放到偶数队列
        for(int i = 0; i < array.length; i++) {
            if((array[i] & 1) == 1) odd.offer(array[i]);
            else even.offer(array[i]);
        }
        int i = 0;
        //对原数组进行覆盖
            while(odd.size() != 0){
                array[i] = odd.poll();
                i++;
            }
            while(even.size() != 0) {
                array[i] = even.poll();
                i++;
            }   
    }
}

上述代码拥有较理想的时间复杂度，但是可否降低如此大的空间开销呢，答案是肯定的，但是代价是牺牲较好的时间特性。

/* 
*  1.找到第一个偶数的位置
*  2.找到偶数后第一个奇数的位置
*  3.将偶数开始到奇数截止的数字均后移一位，该奇数插到原偶数位置
*  4.直到遍历完毕
*  5.时间复杂度为O（N2）
*/
public class Solution {
    public static void reOrderArray(int [] array) {
        int i = 0;
        while((i < array.length) && ((array[i] & 1) == 1)) i++;
        int j = i + 1;
        while(j < array.length) {
            while((j < array.length) && (array[j] & 1) == 0) j++;
            if(j < array.length) {
            int tmp = array[j];
            for(int m = j - 1; m >= i; m--) 
                array[m + 1] = array[m];
            array[i] = tmp;
            i++;
            }
            else break;
        }
    }
}

剑指 offer原书上的题目是没有要求奇数与奇数，偶数与偶数之间的相对位置不变的。这样的话只需要设置两个指针指向头部和尾部，头部先移动，遇到偶数停下，尾部再移动，遇到奇数停下，头尾指针指向的元素交换位置。循环迭代到头尾指针相遇即可。这样时间复杂度O（N），空间复杂度O（1）。
但是这道题目不能止步于此，还需注意可以通过函数解藕来增加程序的扩展性。

public class Solution {
    public static void reOrderArray(int [] array) {
        int i = 0;
        while((i < array.length) && (!isEven(array[i]))) i++;
        int j = i + 1;
        while(j < array.length) {
            while((j < array.length) && (isEven(array[j]))) j++;
            if(j < array.length) {
            int tmp = array[j];
            for(int m = j - 1; m >= i; m--) 
                array[m + 1] = array[m];
            array[i] = tmp;
            i++;
            }
            else break;
        }
    }
    public static boolean isEven(int m) {
        return (m & 1) == 0;
    }
}

这样通过函数接偶将程序分成两部分，一部分负责数据操作，一部分负责条件判断。这样当条件改变时，如“把数组中的数分为两部分，能被3整除的数放在前面，不能的放在后面”，则只需要更改条件判断函数即可。