04归并排序及其常见面试题

public class MergeSort {

    public static void main(String[] args) {
        for (int i = 0; i < 5000; i++) {
            int[] arr = ArrayTools.generateRandomArray2(12, 15, true);
            mergeSort(arr);
            ArrayTools.printArr(arr);
            boolean isAsc = ArrayTools.isAsc(arr);
            if (!isAsc){
                System.out.println("出错了");
                break;
            }
        }

        System.out.println("AC");

    }

    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }


    /**
     * 归并排序
     * 递归版本
     *
     * @param arr
     * @param l
     * @param r
     */
    public static void process(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = l + ((r - l) >> 2);
        process(arr, l, mid);
        process(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    public static void merge(int[] arr, int l, int mid, int r) {

        //合并的逻辑：谁小拷贝谁，指针向后移动
        int[] help = new int[r - l + 1];
        //专门给help数字用的
        int i = 0;
        //一个左指针一个右指针
        int p1 = l;
        int p2 = mid + 1;
        //谁小拷贝谁
        while (p1 <= mid && p2 <= r) {
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        //下面两个肯定只有一个满足,因为经过上面的处理要么p1越界，要么p2越界
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        //再把help数组刷回去
        for (int j = 0; j < help.length; j++) {
            arr[l + j] = help[j];
        }
    }

}

public class MergeSort1 {

    //SUMMARY（总结）: 非递归的归并排序
    /**
     * k -> 1,2,4,8,16...
     *
     *
     */
    /**
     * @param arr
     */
    public static void mergeSort2(int arr[]) {

        if (arr == null || arr.length < 2) {
            return;
        }
        int len = arr.length;
        int mergeSize = 1;
        //mergeSize乘2直到到达len的规模
        while (mergeSize < len) {
            //LOOK ME（注意点）:怎么拆分呢？
            int l, mid, r;
            l = 0;

            while (l < len) {
                //LOOK ME（注意点）:计算中点
                //mid是基于mergeSize算的
                mid = l + mergeSize - 1;
                //r是基于mid算的
                //LOOK ME（注意点）:这个很重要，当mergeSize变得大了，r就会越界，这边取一个最小就搞定了这个问题
                r = Math.min(len - 1, mid + mergeSize);
                merge(arr, l, mid, r);
                //合并完后，l要换到r的右边

                //LOOK ME（注意点）:这一组换完了那就换下一组，一组是两个mergeSize
                l = r + 1;
            }
            //LOOK ME（注意点）:为了防止溢出
            if (mergeSize / 2 > len) {
                break;
            }
            //LOOK ME（注意点）:每次乘2，位运算就是快，快就完了
            mergeSize <<= 1;
        }

    }

    public static void merge(int arr[], int l, int mid, int r) {

        //先搞出来一个辅助数组，长度是左右索引差值加一
        int help[] = new int[r - l + 1];
        int i = 0;

        //左组的第一个索引
        int p1 = l;

        //右组的第一个索引
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= r) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }

        //谁剩下了就拷贝谁
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }

        //再把help刷回去
        for (int j = 0; j < help.length; j++) {
            arr[l + j] = help[j];
        }
    }

    public static void main(String[] args) {

        for (int i = 0; i < 5000; i++) {
            int arr[] = ArrayTools.generateRandomArray2(12, 14, true);
            mergeSort2(arr);
            ArrayTools.printArr(arr);
            ArrayTools.validArrAsc(arr);
        }
        ArrayTools.AC();
    }
}