归并排序

思想

归并将两个或两个以上的有序表合并成一个新的有序表。

两路归并 (2-way merging)：
原始序列initList[]中两个有序表

1. initList[1] … initList[m]
2. initList[m+1] … initList[n]
3. 它们可归并成一个有序表, 存于另一对象序列mergedList的 l … n 中。

演示

代码

    /**
     * 合并子数组中已排序的两部分
     *
     * @param a        可以比较的数组
     * @param tmpArray 放置合并结果的数组
     * @param leftPos  最左边index
     * @param rightPos 第二个数组开始的index
     * @param rightEnd 最右边的index
     */
    private static <AnyType extends Comparable<? super AnyType>>
    void merge(AnyType[] a, AnyType[] tmpArray,
               int leftPos, int rightPos, int rightEnd) {
        //1.初始化位置指针，元素个数
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;

        //2.左右比较，合并，直到一边用完
        while (leftPos <= leftEnd && rightPos <= rightEnd) {
            if (a[leftPos].compareTo(a[rightPos]) < 0) {
                tmpArray[tmpPos++] = a[leftPos++];
            } else {
                tmpArray[tmpPos++] = a[rightPos++];
            }
        }

        //3.如果左边没用完，复制到tmpArray后面
        while (leftPos <= leftEnd) {
            tmpArray[tmpPos++] = a[leftPos++];
        }
        //4.如果右边没用完，复制到tmpArray后面
        while (rightPos <= rightEnd) {
            tmpArray[tmpPos++] = a[rightPos++];
        }

        //5.复制排好序的tmpArray到a里面去
        for (int i = 0; i < numElements; i++, rightEnd--) {
            a[rightEnd] = tmpArray[rightEnd];
        }

    }


    /**
     * 归并递归调用
     *
     * @param a         可以比较的数组
     * @param tmpArrays 放置合并结果的数组
     * @param left      最左边index
     * @param right     最右边index
     */
    private static <AnyType extends Comparable<? super AnyType>>
    void mergeSort(AnyType[] a, AnyType[] tmpArrays, int left, int right) {
        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(a, tmpArrays, left, center);
            mergeSort(a, tmpArrays, center + 1, right);
            merge(a, tmpArrays, left, center + 1, right);
        }
    }

    /**
     * 归并排序
     *
     * @param a 一组可以比较的数据
     */
    public static <AnyType extends Comparable<? super AnyType>>
    void mergeSort(AnyType[] a) {
        AnyType[] tmpArrays = (AnyType[]) new Comparable[a.length];
        mergeSort(a, tmpArrays, 0, a.length - 1);
    }

分析

时间复杂度最坏情况O(NlogN)