分治法与归并排序

分治法

许多有用的算法在结构上是递归的：为了解决一个给定的问题，算法一次或多次递归地调用其自身以解决紧密相关的若干子问题。这些算法使用的就是分治思想：

1.先将先原问题分解成若干子问题，这些子问题是原问题规模较小的实例
2.对这小较小问题进行求解，分解到最后小到不能最小时能够直接求解
3.将这些子问题的解进行合并和汇总后就得到了原问题的解

归并排序

归并算法就是这样一种使用了分治算法进行求解问题的算法，它的思想就是将一组需要排序的序列一分为二，左边右边都递归地调用归并排序排好序后进行合并。待排序的序列只有一个的时候可以直接排序，然后递归回升将这些小的有序序列给合并起来，从而整体排序成功。

合并这个过程就是，现在有两堆扑克牌面朝下，而且都是有序的，从大到小堆起来（最顶上的是最小的）。现在需要将这两堆给合并起来产生一堆有序的扑克牌，这就是归并排序中合并需要做的事情。做法是，左右都翻开最顶上一张牌，把较小的放到新的堆中。不断的比较最顶上的牌，直到将这两堆都放入到新堆中，此时排序就结束了，出现了一堆有序的扑克牌。

归并排序.gif

代码实现

/**
 * author waigo
 * create 2021-02-03 22:20
 */
public class MergeSort {
    /**
     *
     * @param A 待排序的数组
     * @param p 待排序区间开始下标
     * @param q 中间分界下标
     * @param r 待排序区间结束下标
     */
    public static void merge(int[] A, int p, int q, int r) {
        //创建新的两个数组，分别存有一半的数据
        int n1 = q - p + 1;//第一堆的个数
        int n2 = r - q;
        int[] L = new int[n1 + 1], R = new int[n2 + 1];
        for (int i = 0; i < n1; i++)
            L[i] = A[p + i];
        for (int i = 0; i < n2; i++)
            R[i] = A[q + i + 1];
        //放置哨兵牌，这个有大用，免去了后面复杂的判断下标是否溢出
        L[n1] = Integer.MAX_VALUE;
        R[n2] = Integer.MAX_VALUE;
        //总共需要循环r-p+1次就是将两堆牌全部复制回原先的数组中
        int leftTop = 0, rightTop = 0;//两个指针用来遍历两个子数组
        for (int i = p; i <= r; i++)//需要排序的总数是r-p+1
            //找到两堆顶上较小那个放回，此时两堆都是有序的
            //由于最后一个是哨兵值为最大的，所以是不会作为较小的，所以会一直卡在这里指针不会移动也就不会溢出
            A[i] = L[leftTop] <= R[rightTop] ? L[leftTop++] : R[rightTop++];
    }

    public static void mergeSort(int[] A, int p, int r) {
        //如果p>=r则此时需要处理的至多一个元素，一个元素是有序的
        if (p < r) {
            //分治法，对左半边排序，对右半边排序，然后两边有序之后使用merge进行排序
            int q = (p + r) / 2;//处理区间的中间下标
            mergeSort(A, p, q);//左半区A[p...q]
            mergeSort(A, q + 1, r);//右半区A[q+1...r]
            merge(A, p, q, r);//左右都排好序之后就可以使用merge进行归并排序
        }
    }
}

测试代码

public class MergeSortTest {
    @Test
    public void mergeTest() {
        int[] arr = RandomProducer.produceRandom(-500, 100000000, 8000000);
        Date from = new Date();
        MergeSort.mergeSort(arr, 0, arr.length - 1);
//        Logger.getGlobal().info("排序后："+Arrays.toString(a));
        System.out.println("运行了" + (new Date().getTime() - from.getTime()) + "毫秒");
        //使用800,0000个随机数序列进行测试，发现归并排序差不多需要1650ms，这个速度是比快排的1200ms要慢的，
        //但是比希尔排序的2500ms要快很多
    }
}

非递归实现

递归版本通过Master公式T(N) = a * T(N/b) + O(N^d)

T(n) = 2*T(n/2)+O(N)-->log(b,a)==log(2,2)==d==1，所以时间复杂度O(N)=N*logN

通过改写非递归版本可以更加直观看出确实时间复杂度是O(N*logN)

public static void mergeSort1(int[] nums) {
    int N = nums.length;
    int mergeSize = 1;//指的是左边有序的长度
    //每次merge的大小是2*mergeSize,所以若是mergeSize>N/2就表示上一次已经完成排序了
    // (错误，比如数组长度是3,3/2=1，很明显mergeSize=1后还没排序好)
    while (mergeSize < N) {//logN,每次乘以2追赶，相对于求N个节点的树高为logN
        int L = 0;
        while (L < N) {
            //M表示这一次merge的中点，因为上一次完成了mergeSize的merge，所以M要在上一次完成了merge区间的最后
            //M-L+1表示L和M夹起来的区间[L...M]的大小等于mergeSize,M-L+1=mergeSize
            int M = mergeSize + L - 1;
            if (M >= N) break;//表示左边都不够mergeSize了，完成一个merge至少需要区间size>mergeSize
            //R表示这次merge的右边点，应该是一个mergeSize结尾，R-M = mergeSize,这个区间不包括M
            //但是可能这右边可能不够mergeSize大小了
            int R = Math.min(M + mergeSize, N - 1);
            merge(nums, L, M, R);
            L = R + 1;//开始下个区间
        }
        ////太细了，假如N的长度等于Integer.MAX_VALUE,那此时mergeSize乘以2会溢出的
        if (mergeSize > (N >> 1)) break;
        mergeSize <<= 1;//mergeSize *= 2
    }
}