利用排序算法调整数组

这道题很明显是利用排序算法解决实际问题的题
由于要保证奇数和奇数，偶数和偶数之间的相对位置不变。
即排序算法要具有稳定性： 冒泡，插入，并归，计数，基数，桶
这里分别修改冒泡排序(20ms)，插入排序(25ms)，并归排序(14ms)来解决这个问题

1. 冒泡法 O(n^2) Java 20ms

这里考虑到提前完成的情况，所以判断内层是否发生交换，如果没有就直接跳出嵌套循环

/**
     * 冒泡
     * @param array
     */
    public static void reOrderArray1(int [] array) {
        boolean changed = true;
        for (int i=0;i<array.length && changed;i++){
            changed = false;
            for (int j=0;j<array.length-1-i;j++){
                // 左边是奇数右边是偶数的情况交换
                if ((array[j]&1)==0 && (array[j+1]&1)==1){ 
                    changed = true;
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }

    }

2. 插入法 O(N^2) Java 25ms

也是直接修改判断条件即可

/**
     * 插入
     * @param array
     */
    private static void reOrderArray2(int[] array) {
        int j,key;
        for (int i=1;i<array.length;i++){
            key = array[i];
            if ((key&1)==0) continue;// 如果是偶数的话跳过
            j = i-1;
            while (j>=0 && (array[j]&1)==0){ // 找到奇数位置
                array[j+1] = array[j];
                j--;
            }
            array[j+1] = key;
        }
    }

3. 并归法 O(nlogn) Java 14ms

也是直接修改判断条件即可

/**
     * 并归 14ms
     * @param array
     */
    private static void reOrderArray(int[] array) {
        mergeSort(array,0,array.length-1);
    }
    /**
     * 归并排序，合并排序
     * @param arr 要排序的数组
     * @param p 左边索引
     * @param r 右边索引
     */
    public static void mergeSort(int[] arr, int p, int r){
        // 递归实现合并排序
        if(p<r){
            int q = (p+r)/2;
            mergeSort(arr, p, q);
            mergeSort(arr, q+1, r);
            merge(arr, p, q, r); //上面的合并算法
        }
    }
    /**
     * 合并
     */
    public static void merge(int[] arr, int p, int q, int r){
        // arr是数组，p，q，r为下标。 p-q 和 q-r 为已经排好序的两个堆（不带哨兵）
        int n1 = q-p+1; // [p-q]左边元素的个数,q元素归左边
        int n2 = r-q; // (q-r]右边元素个数
        int[] L = new int[n1];
        int[] R = new int[n2];
        System.arraycopy(arr, p, L, 0, n1);
        System.arraycopy(arr,q+1,R,0,n2);
        for(int k=p,i=0,j=0; k<=r; k++){
            if(i==n1)
                arr[k] = R[j++]; // 左边已经到头了
            else if(j==n2)
                arr[k] = L[i++]; // 右边已经到头了
            else if((L[i]&1)==1 || ((L[i]&1)==0 && (R[j]&1)==0))
                arr[k] = L[i++]; // 左边是奇数(或者左右都是偶数时) 的话左边放入数组
            else
                arr[k] = R[j++]; // 否则右边放入
        }
    }