一、概念

归并排序(Merge Sort)是建设在归并操作上的一种无效,稳固的排序算法,该算法是采纳分治法的一个十分典型的利用。

将已有序的子序列合并,失去齐全有序的序列;即先使每个子序列有序,再使子序列段间有序。

二、排序过程

1、归并操作,指的是将两个程序序列合并成一个程序序列的办法。

如:数组 {6,202,100,301,38,8,1}

初始状态:6,202,100,301,38,8,1

第一次归并后:{6,202},{100,301},{8,38},{1};

第二次归并后:{6,100,202,301},{1,8,38};

第三次归并后:{1,6,8,38,100,202,301};

2、归并操作步骤如下

(1)申请空间,大小为两个曾经排好序的序列之和,该空间用来做辅助数组

(2)设定两个指针,最后地位别离为两个曾经排序序列的起始地位

(3)比拟两个指针所指向的元素,抉择绝对小的元素放入到合并空间(相等抉择左组),并挪动指针到下一地位。

反复步骤3直到某一指针越界。将另一序列剩下的所有元素间接复制到合并序列(辅助数组)尾,将辅助数组数据拷贝回原数组。

三、Master公式预计工夫复杂度

Master公式:剖析递归函数的工夫复杂度,要求子问题规模统一

形如:
T(N) = a * T(N/b) + O(N^d)(其中a、b、d都是常数)的递归函数,能够间接通过Master公式来确定工夫复杂度
1)如果log(b,a) < d,工夫复杂度为O(N^d)
2)如果log(b,a) > d,工夫复杂度为O(N^log(b,a))
3)如果log(b,a) == d,工夫复杂度为O(N^d * logN)

依据Master公式可得 T(N) =2 * T(N/2) + O(N)

因为每次都是拆分为两个子问题,每个子问题占总规模的一半,且合并过程的工夫复杂度是O(N)

可得归并排序的工夫复杂度是O(N*logN)

四、代码实现

1、递归办法实现

    /**     * 1.递归办法实现     */    public static void mergeSort1(int[] arr) {        if (arr == null || arr.length < 2) {            return;        }        process(arr, 0, arr.length - 1);    }    private static void process(int[] arr, int l, int r) {        if (l == r) {            return;        }        int mid = l + ((r - l) >> 1);        // 左组递归        process(arr, l, mid);        // 右组递归        process(arr, mid + 1, r);        // 合并        merge(arr, l, mid, r);    }    private static void merge(int[] arr, int l, int m, int r) {        // 辅助数组        int[] help = new int[r - l + 1];        int i = 0;        // 左组地位        int pL = l;        // 右组地位        int pR = m + 1;        while (pL <= m && pR <= r) {            // 谁小拷贝谁,相等的拷贝左组            help[i++] = arr[pL] <= arr[pR] ? arr[pL++] : arr[pR++];        }        // pL和pR有且只有一个会越界,也就是上面两个while只有一个会执行        while (pL <= m) {            help[i++] = arr[pL++];        }        while (pR <= r) {            help[i++] = arr[pR++];        }        // 拷贝回原数组        for (int j = 0; j < help.length; j++) {            arr[l + j] = help[j];        }    }

2、迭代形式实现

定义一个步长,初始值为1。从0地位的数开始,每两个步长的数merge完后拷贝回原数组,步长*2;再从0地位的数开始,每两个步长的数merge完后拷贝回原数组,步长*2……直到(步长 > 数组长度 / 2)
    /**     * 2.迭代形式实现归并排序     * <p>     * 步长调整次数 复杂度是logN,每次调整步长都会遍历一遍整个数组 复杂度是N,整个的工夫复杂度是O(N*logN)     */    public static void mergeSort2(int[] arr) {        if (arr == null || arr.length < 2) {            return;        }        int N = arr.length;        // 步长初始值        int mergeSize = 1;        // 步长不能超过数组长度        while (mergeSize < N) {            // 以后左组的第一个地位            int L = 0;            // 左组也不能超过数组长度            while (L < N) {                // 左组最初一个地位                int M = L + mergeSize - 1;                // 如果左组最初一个地位越界,表明左组都不够则不须要merge                if (M >= N) {                    break;                }                // 右组的最初一个地位                // 右组第一个地位是 M + 1,满足个数要求则右组大小是mergeSize,所以最初一个地位是 (M + 1) + mergeSize - 1                // 不满足则是数组的最大地位 N - 1                int R = Math.min(M + mergeSize, N - 1);                // 目前 左组:L......M,右组:M+1......R                merge(arr, L, M, R);                // 下一次左组的地位(所以才须要判断L < N)                L = R + 1;            }            // 避免溢出            // 当步长很凑近N的最大值时,乘以2扩充步长后,步长就溢出了            // 不能取 >=,假如最大值是9,mergeSize = 4时就不会扩充步长了,然而mergeSize = 8时还有一次merge,所以不能取 =            if (mergeSize > N / 2) {                break;            }            // 步长每次扩充2倍            mergeSize <<= 1;        }    }