前言

归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为 O(NlogN)(大O符号)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

归并排序的图示:

算法讲解

归并排序算法是采用经典的分治策略,将问题divide成一些小问题,然后在conquer阶段将分的阶段得到的答案修补在一起,即为分而治之。


任何的递归都可以采用迭代来实现,递归行为实质上是压栈和出栈的过程。

算法实例

算法流程:

  • 对待排序数组array进行拆分,即分治思想中的分。
  • 将array分为两组之后进行排序,保证子序列有序。在保证子序列有序的过程中还会递归上一步骤,直到left==right的时候。
    /**
     * 传入参数合法性校验,然后调用归并排序的方法
     *
     * @param array 目标数组
     */
    public static void mergeSort(int array[]) {
        if (array == null || array.length < 2) {
            return;
        }
        sort(array, 0, array.length - 1);
    }

    /**
     * 归并排序的实现,这里用到的是分治的思想
     *
     * @param array
     * @param left
     * @param right
     */
    private static void sort(int[] array, int left, int right) {
        //递归终止条件
        if (left == right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        sort(array, left, mid);
        sort(array, mid + 1, right);
        //归并
        merge(array, left, right);
    }

    /**
     * 归并算法
     *
     * @param array
     * @param left
     * @param right
     */
    private static void merge(int[] array, int left, int right) {
        int mid = left + ((right - left) >> 1);//防止因为left和right太大导致的integer越界,相当于left+(right-left)/2
        int[] help = new int[right - left + 1];//建立辅助数组
        int i = 0;
        int p1 = left;//p1指向left的数组第一个
        int p2 = mid + 1;//p2指向right数组的第一个
        while (p1 <= mid && p2 <= right) {
            //比较,谁小填入辅助数组
            help[i++] = array[p1] < array[p2]   ? array[p1++] : array[p2++];
        }
        //上面的while循环结束,当且只当p1和p2有一个越界,下面的两个while是将剩下的数组数据填到辅助数组
        while (p1 <= mid) {
            help[i++] = array[p1++];
        }
        while (p2 <= right) {
            help[i++] = array[p2++];
        }
        //数据回填,将辅助数组的数据回填到原数组
        for (i = 0; i < help.length; i++) {
            array[left + i] = help[i];
        }
    }

总结

时间复杂度分析:

递归行为可以采用master公式:

T(N)=a*T(N/b)+O(N^d)

以上算法针对的是对于一个数据,可以分为b个部分进行处理。


1) log(b,a) > d -> 复杂度为O(N^log(b,a)) 2) log(b,a) = d -> 复杂度为O(N^d * logN) 3) log(b,a) < d -> 复杂度为O(N^d)

对于归并来说,可以看做是将一个数据分为两部分来进行处理。

这里的公式为:


```d=1,log(b,a)=1```,那么这个时间复杂度为

关于master公式:www.gocalf.com/blog/algorithm-complexity-and-mastertheorem.html