/*

     * 新开数组：空间换时间

     * 1.遍历数组，若为奇数则从头部放入到原数组中，并记录索引

     * 2.若为偶数则放入到新数组中，记录索引

     * 3.将两数组合并，从最后一个奇数后插入偶数

     */

    public static void reOrderArray(int[] array) {

        if (array == null || array.length == 0)

            return;

        int indexOdd = 0, indexEven = 0;

        int[] even = new int[array.length];//存放偶数数组

        for (int num : array) {

            if ((num & 1) == 1) {//为奇数时

                array[indexOdd++] = num;

            } else {//为偶数时

                even[indexEven++] = num;

            }

        }

        //合并数组

        for (int i = 0; i < indexEven; i++) {

            array[indexOdd + i] = even[i];

        }

    }

    /*

     *  插入排序思想

     */

    public static void reOrderArray_2(int[] array){

        if (array == null || array.length == 0)

            return;

        int i,j,tempNum;

        for(i =1;i<array.length;i++){

            if((array[i]&1)==1){//当为奇数时

                tempNum = array[i]; //存储被比较的数

                j =i-1;

                while(j>=0&&(array[j]&1)==0){//当前一个数为偶数时，将奇数往前挪

                    array[j+1] = array[j];

                    j--;

                }

                array[j+1]=tempNum;

            }

        }

    }