归并排序

前面几篇文章，我们对冒泡排序，插入排序，和选择排序进行了分析。但是他们的实际复杂度都是O(n平方)。这次我们来看看时间复杂度更小的归并排序。

思想

归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

1. 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
2. 解决（Conquer）：用合并排序法对两个子序列递归的排序。
3. 合并（Combine）：合并两个已排序的子序列已得到排序结果。

思想图解

具体的我们以一组无序数列｛14，12，15，13，11，16｝为例分解说明，如下图所示：

代码

递归实现

//递归实现归并排序
    public  static void mergeSort_recursion(int[] arr){
        if (arr == null || arr.length<2){
            return;
        }
        process(arr,0,arr.length-1);
    }

    //L ...R 位置上是有序的
    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); //数据合并
    }

    //其实合并的时候有点想 leetcode 中 合并两个有序数组的题目
    private static void merge(int[] arr, int L, int M, int R) {
        //声明一个临时数组
        int[] help =  new int[R-L+1];
        int i = 0;
        int p1 = L;
        int p2 = M+1;
        while (p1<=M && p2<=R){//防止数组越界
            //i++ 先赋值再++
            help[i++] = arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
        }
        //善后工作,要么p1越界了，要么p2越界了
        while (p1<=M){
            help[i++] =arr[p1++];
        }
        while (p2<=R){
            help[i++] =arr[p2++];
        }
        for (i=0;i<help.length;i++){
            arr[L+i] = help[i];
        }
    }


复制代码

非递归实现

// 非递归方法实现
    public static void mergeSort(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){
                if (mergeSize>=N-L){//防止越界
                    break;
                }
                int M = L+mergeSize-1;
                int R = M+Math.min(mergeSize,N-M-1);//确认右边界
                merge(arr,L,M,R);
            }
            //防止溢出
            if (mergeSize> N/2){
                break;
            }
            mergeSize<<=1;//步长调整为原来的2倍
        }
    }
复制代码

归并排序思想的变种题目

求最小和

在一个数组中，一个数左边比它小的数的总和，叫做小和，所有数的小和累加起来，叫做数组的小和。求数组的小和。例如[1, 3, 4, 2, 5]

• 1左边比1小的数：没有
• 3左边比3小的数：1
• 4左边比4小的数：1、3
• 2左边比2小的数为：1
• 5左边比5小的数为：1、3、4、2
• 所以该数组的小和为：1+1+3+1+1+3+4+2 = 16

代码及思路

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

    // arr[L..R]既要排好序，也要求小和返回
    // 所有merge时，产生的小和，累加
    // 左 排序   merge
    // 右 排序  merge
    // merge
    public static int process(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        // l < r
        int mid = l + ((r - l) >> 1);
        return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
    }

    //
    public static int merge(int[] arr, int L, int m, int r) {
        int[] help = new int[r - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = m + 1;
        int res = 0;
        while (p1 <= m && p2 <= r) {
            //不同点：当前的数是比右组小的，产生右组当前位置到右组右边界数量个小和，累加到res。否则res加0
            // why (r - p2 + 1) * arr[p1]? 因为 左右两边都是排好序的，当p2 位置的数比p1 位置的 数大时，
            // 那么就有 (r - p2 + 1) 个数比p1 位置的数大,因为 p1 会向右移动，所以只会比较一次
            // 1  2  3  4  |  0  3  6
            // p1             p2
            // p1                p2 ======>R-P2+1 个数 比 p1 位置的数大
            //    p1             p2 ======>R-P2+1 个数 比 p1 位置的数大
            res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
            // 不同点： 如果p1 位置的数 == p2 位置的数，先copy 右边的数
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
        return res;
    }

复制代码