一、概述

    在上一篇中我们分析了几个时间复杂度为O(N^2)排序算法，今天我们将深入学习几个时间复杂度为O(NlogN)的排序，大家拴好安全带，博主直接弹射起步，开始本篇的内容。

二、分析

    1.剖析递归行为

    重点：剖析递归行为和递归行为时间复杂度估算

    场景：用递归方法找一个数组中的最大值，系统上到底是怎么做到的？

    递归行为时间复杂度估算常用公式：master公式的使用：T(N) = a*T(N/b) + O(N^d)，满足此公式的算法时间复杂度计算如下：

        (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)

    常规递归代码演示：

    /**
     * 递归获取数组arr上L到R中的最大值
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static int process(int[] arr,int L,int R){
        //始终保持 R >= L
        if(L>R){
            L = L ^ R;
            R = L ^ R;
            L = L ^ R;
        }
        if(L == R){
            return arr[L];
        }
//        int mid = L >> 1 + R >> 1; 这样写执行顺序等同于 mid = L >> (1 + R >> 1); 导致mid最终等于0
//        int mid = (L  + R) >> 1; 这样写会导致 L + R 的值可能超过int的最大值范围
        int mid = (L >> 1) + (R >> 1);
        int lMax = process(arr,L,mid);
//        int rMax = process(arr,mid,R); //左边递归已经到了mid，所以右边递归从mid+1开始，
        int rMax = process(arr,mid+1,R);
//        return lMax>rMax?lMax:rMax;
        return Math.max(lMax,rMax); //源码中 return (a >= b) ? a : b;等同于上面
    }

    执行结果：

    master公式分析：T(N) = a*T(N/b) + O(N^d)

        (1) T(N)标识母问题，也就是递归最初的问题；

        (2) a 标识子递归调用的次数；

        (3) T(N/b) 中的b表示每次子递归时，规模是等量的，都是1/b的规模；

        (4) O(N^d)表示除了子过程调用之外，剩下的过程时间复杂度是多少。

    由上面常规递归代码得出：a等于2，b等于2，c等于1，最终时间复杂度公式为 T(N) = 2*T(N/2) + O(1)，得出log(b,a) = 1，d=0，因为log(b,a) > d，则时间复杂度为O(N^log(b,a))，即O(N)。

    2.归并排序

    1）整体就是一个简单的递归，左边排好序、右边排好序、让整体有序

    2）让其整体有序的过程里用了排外序方法

    3）利用master公式来求解时间复杂度

    4）归并排序的实质

    复杂度：时间复杂度O(N*logN)，额外空间复杂度O(N)。

    代码如下：

    /**
     * 递归获取数组arr上L到R中的最大值
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static void margeSort(int[] arr,int L,int R){
        //始终保持 R >= L
        if(L>R){
            L = L ^ R;
            R = L ^ R;
            L = L ^ R;
        }
        if(L == R){
            return ;
        }
        int mid = (L >> 1) + (R >> 1);
        //左右分别递归
        margeSort(arr,L,mid);
        margeSort(arr,mid+1,R);
        //排序并合并
        marge(arr,L,mid,R);
    }

    public static void marge(int[] arr,int L,int mid,int R){
        //初始化一个临时数组
        int[] resArr = new int[R-L+1];
        //临时数组下标
        int i = 0;
        //左边数组的初始下标
        int p1 = L;
        //右边数组的初始下标
        int p2 = mid+1;
        //当左右数组都没越界的时候，进行比较
        while (p1 <= mid && p2 <= R){
            resArr[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        //当p2已经越界的时候，p1还有元素，就将p1所有的元素填充到临时数组(和下面的情况只会出现一种)
        while(p1 <= mid){
            resArr[i++] = arr[p1++];
        }
        //当p1已经越界的时候，p2还有元素，就将p2所有的元素填充到临时数组(和上面的情况只会出现一种)
        while(p2 <= R){
            resArr[i++] = arr[p2++];
        }
        //替换到数组arr中L到R的元素
        for (int j = 0; j < resArr.length; j++) {
            arr[L+j] = resArr[j];
        }
    }

    时间复杂度分析：满足T(N) = 2*T(N/2) + O(N)，得出log(b,a) = 1，d=1，因为log(b,a) = d，则时间复杂度为O(N^logN)。

    3.小和问题——归并排序拓展（逆序对问题）

    小和问题：在一个数组中，每个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。

    例子：数组[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。

    解法思路：采用递归的方式分为左右两个数组，则左边的数组产生的小和+右边的数组产生的小和+左右数组合并产生的小和就为最终的结果。

    代码如下：

    /**
     * 获取数组arr的小和
     * @param arr
     * @return
     */
    public static int smallSum(int[] arr){
        if(arr == null || arr.length < 2){
            return 0;
        }
        return process(arr,0,arr.length-1);
    }


    /**
     * 递归获取数组arr上L到R中的最大值
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static int process(int[] arr,int L,int R){
        //始终保持 R >= L
        if(L>R){
            L = L ^ R;
            R = L ^ R;
            L = L ^ R;
        }
        if(L == R){
            return 0;
        }
        int mid = (L >> 1) + (R >> 1);
        //左右分别递归
        return process(arr,L,mid) + process(arr,mid+1,R) + marge(arr,L,mid,R);
    }

    public static int marge(int[] arr,int L,int mid,int R){
        //初始化一个临时数组
        int[] resArr = new int[R-L+1];
        //临时数组下标
        int i = 0;
        //左边数组的初始下标
        int p1 = L;
        //右边数组的初始下标
        int p2 = mid+1;
        //初始化小和
        int res = 0;
        //当左右数组都没越界的时候，进行比较
        while (p1 <= mid && p2 <= R){
            //产生小和
            res += arr[p1] < arr[p2] ? ((R - p2 + 1) * arr[p1]) : 0;
            //元素拷贝
            resArr[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        //当p2已经越界的时候，p1还有元素，就将p1所有的元素填充到临时数组(和下面的情况只会出现一种)
        while(p1 <= mid){
            resArr[i++] = arr[p1++];
        }
        //当p1已经越界的时候，p2还有元素，就将p2所有的元素填充到临时数组(和上面的情况只会出现一种)
        while(p2 <= R){
            resArr[i++] = arr[p2++];
        }
        //替换到数组arr中L到R的元素
        for (int j = 0; j < resArr.length; j++) {
            arr[L+j] = resArr[j];
        }
        return res;
    }

    逆序对问题：在一个数组中，左边的数如果比右边的大，则这两个数构成一个逆序对，请打印所有逆序对。解法雷同小和问题。

    4.荷兰国旗问题——引出快速排序

    问题一：给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)。

    问题二(荷兰国旗问题)：给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)。

    5.快速排序的演变

    1）基本快速排序描述：

    （1）把数组范围中的最后一个数作为划分值，然后把数组通过荷兰国旗问题分成三部分：左侧<划分值、中间==划分值、右侧大于划分值；

    （2）对左侧范围和右侧范围，递归执行。

    分析：

    （1）划分值越靠近两侧，复杂度越高；划分值越靠近中间，复杂度越低；

    （2）可以轻易的举出最差的例子，所以不改进的快排时间复杂度为O(N^2)。

   2） 改进快速排序描述：

    （1）把数组范围中的随机一个数作为划分值，然后把数组通过荷兰国旗问题分成三部分：左侧<划分值、中间==划分值、右侧大于划分值；

    （2）对左侧范围和右侧范围，递归执行。

    分析：由于划分值改为随机获取，所以各种情况产生的概率相同，改进的快排时间复杂度为O(N*logN)。

    代码：

    /**
     * 快排
     * @param arr
     * @return
     */
    public static void quickSort(int[] arr){
        if(arr == null || arr.length < 2){
            return ;
        }
        quickSort(arr,0,arr.length-1);
    }

    /**
     * 数组arr上L到R排序
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static void quickSort(int[] arr,int L,int R){
        //始终保持 R >= L
        if(L>R){
            L = L ^ R;
            R = L ^ R;
            L = L ^ R;
        }
        if(L < R){
            swap(arr,L+(int)(Math.random()*(R-L+1)),R);
            //左右分别递归
            int[] p = partition(arr,L,R);
            partition(arr,L,p[0]-1); // 小于区域
            partition(arr,p[1]+1,R); // 大于区域
        }

    }

    public static int[] partition(int[] arr,int L,int R){
        //小于区域右边界
        int less = L - 1;
        //大于区域左边界
        int more = R;
        //L表示当前位置 arr[R]是划分值
        while(L < more){
            if(arr[L] < arr[R]){ //当前数 <划分值时
                swap(arr,++less,L++);
            }else if(arr[L] > arr[R]){ //当前数 >划分值时
                swap(arr,--more,L);
            }else {
                L++;
            }
        }
        swap(arr,more,R);
        return new int[] {less+1,more};
    }

三、总结

    本文剖析了归并排序和快速排序的演变和原理，深入了解排序过程中元素的变化。下一篇博主将介绍堆排序、桶排序等详解，并且将会对之前的排序内容作出总结，敬请期待《算法从入门到精通（三）：详解桶排序以及排序内容大总结》。

    更多精彩内容，敬请扫描下方二维码，关注我的微信公众号【Java觉浅】，获取第一时间更新哦！