一、使用辅助数组

使用两个辅助数组，一个用来存偶数，一个用来存奇数，时间复杂度O(n)，代码如下：

            if (array==null||array.length==0)
                return;
            //解法1：排序+额外空间
            LinkedList<Integer> oddList=new LinkedList<>();
            LinkedList<Integer> evenList=new LinkedList<>();
            for (int item:array){
                if ((item&1)==0)
                    evenList.add(item);
                else
                    oddList.add(item);
            }
            int p=0;
            for (int i:oddList)
                array[p++]=i;
            for (int i:evenList)
                array[p++]=i;

二、双指针

利用双指针，p1遇到偶数先停下来，p2向后移动，直到遇到奇数，将奇数换到前面，然后将p1和p2之间的数字整体后移。代码如下：

            if (array==null||array.length==0)
                return;
            int p1=0,p2=0;
            while (true){
                //找到第一个偶数，停下来
                for (;p1<array.length;++p1){
                    if ((array[p1]&1)==0)
                        break;
                }
                //找到第一个奇数，停下来
                for (p2=p1+1;p2<array.length;++p2){
                    if ((array[p2]&1)==1)
                        break;
                }
                if (p1==array.length||p2==array.length)
                    break;
                //将p1-p2之间的数据整体往后移
                int tmp=array[p2];
                for (int i=p2;i>p1;--i){
                    array[i]=array[i-1];
                }
                array[p1]=tmp;
            }