【算法】---归并排序（递归非递归实现）

参考

左程云算法
算法导论

前言

本篇介绍

• 归并排序
• 分治法

前置知识

• 了解递归， 了解数组。

引入

归并排序
归并排序最早是由公认的现代计算机之父John von Neumann发明的， 这是一种典型的分治思想应用。

我们先介绍分治思想
分治思想
分治思想的想法基于递归， 许多算法可以通过自身调用， 来降低问题的规模， 又获得与原问题类似的子问题。可见， 分治法本质是递归思想的一个分支，分治法还要额外进行处理， 先进行递归地求解子问题， 然后合并这些子问题的解求出原问题的解。

通过一个简单的例子， 来讲解分治思想。
给定一个int类型的数组， 求解该数组的最大值。
你可能已经很熟悉了， 线性遍历即可。

public static int getMaxValue1(int[] arr) {int n = arr.length;//max，初始默认为系统最小值。int max = Integer.MIN_VALUE;//无序数组， 直接遍历for(int i=0;i<n;i++) {max = Math.max(max, arr[i]);}return max;}

分治思想如何运用呢？ 原数组区间范围在[0, arr.length - 1],求解原数组的大小可以被递归解决吗？
很有可能的想法， 直观上， 我们求解原数组的最大值就是求解在原数组序列中最大值。只需要等分序列即可， 将原数组序列的最大值，分解成左右子序列的最大值问题， 从递归上，对子序列可以同样这样处理，直到不需要递归继续降解规模了（递归模式结束， 处理基线条件，以防止死递归了）。
问题在于， 规模确实减小了，但左序列的最大值不一定是整个数组的最大值。 直觉上， 将左右序列的最大值进行比较，决定合并两个序列的最大值。
为此， 我们可以写出分治法的求解子问题的写法。

public static int getMaxValue(int[] arr) {if(arr==null||arr.length==0) {return Integer.MIN_VALUE;//处理值为null，传参为空数组的情况。}return process(arr, 0, arr.length-1);}public static int process(int[] arr, int l, int r) {if(l>r) {return Integer.MIN_VALUE;}if(l==r) {return arr[l];//直接返回值}//递归条件， 降低规模//分治的过程int mid = (l+r)/2;int lmax = process(arr, l, mid);int rmax = process(arr, mid+1, r);//合并的过程。return Math.max(lmax, rmax);}public static void main(String[] args) {int[] arr = {3,5,1,7,8,9,11,2};//对比两种方法， 观察结果是否一致。 相互验证！System.out.println("最大值:"+getMaxValue1(arr));System.out.println("最大值:"+ getMaxValue(arr));}
/***  output:*  最大值:11*  最大值:11*/

总结
对于每层递归：
分治法有三个步骤

• 分解原问题为若干子问题（不一定像上述例子二等分）， 子问题是规模减小的原问题。
• 递归地处理这些子问题， 核心是什么时候继续递归分解， 什么时候直接求解。—写递归时必须想明白， 否则StackOverflow等着你。
• 合并处理子问题的解进而求出原问题的解。

能不能降低规模， 处理好递归，以及合并这个操作具体怎么写。写好分治法的难点。

归并排序

归并排序也是一种分治思想的体现。
基本思想就是，左边有序，右边有序。然后调整为整体有序。

• 分割： 将数组序列二等分， 利用递归不断分解。
• 合并: 合并两个有序序列，保持原来的元素的相对顺序不变。

结合代码和下面图片

	public static void mergeSort(int[] arr) {//无效值null, 数组元素不为2，不需要排序。if(arr==null || arr.length<2) {return ;}//开始process(arr,0, arr.length-1);}public static void process(int[] arr, int l, int r) {//基线条件处理if(l>=r) {return ;}//选中分割下标， 直接取中值即可int mid = (l+r)/2;//左边递归调用process(arr,l, mid);//右边递归调用， 注意参数process(arr,mid+1,r);//合并操作merge(arr,l,mid,r);}public static void merge(int[] arr,int l,int m, int r) {int i = 0;int a = l;int b = m+1;//拷贝一个临时数组int[] help = new int[r-l+1];//比大小的过程while(a<=m && b<=r ) {help[i++]=arr[a]<=arr[b]?arr[a++]:arr[b++];}//处理剩余的序列while(a<=m) {help[i++] = arr[a++];}while(b<=r) {help[i++] = arr[b++];}//将数据拷贝回原序列。for(i=l;i<=r;i++) {arr[i] = help[i-l];}}//测试用例。public static void main(String[] args) {int[] arr= {4,1,6,23,8,9,11,0,2,3,4,4,4,4,10};System.out.println("排序前:"+Arrays.toString(arr));mergeSort(arr);System.out.println("排序后："+Arrays.toString(arr));}/*** output：* 排序前:[4, 1, 6, 23, 8, 9, 11, 0, 2, 3, 4, 4, 4, 4, 10]* 排序后：[0, 1, 2, 3, 4, 4, 4, 4, 4, 6, 8, 9, 10, 11, 23]*/

开始有一个主方法，mergeSort，只需要传递一个int数组即可。
process这一函数是不断递归地分解问题。merge函数是服务当前的process函数。
比如，[4,8],[5,7]给定两个子序列， 通过分离双指针和临时数组help进行比较，原理是拷贝完较小的数组，然后拷贝完剩余的数组。
先将两个序列的比较结果拷贝进help数组，help=[4,5,7]，此时还剩下一个元素8，因为没有数可比了，序列[5,7]的指针已经走到了尽头。只需要挨个检查将剩下的元素依次拷贝进help数组即可。
以上就是对这行代码的解释:

		//比大小的过程while(a<=m && b<=r ) {help[i++]=arr[a]<=arr[b]?arr[a++]:arr[b++];}//处理剩余的序列while(a<=m) {help[i++] = arr[a++];}while(b<=r) {help[i++] = arr[b++];}

最后， 将临时数组help存储的有序序列依次拷贝回原数组的对应序列即可。注意这里是原数组进行修改。

		//将数据拷贝回原序列。for(i=l;i<=r;i++) {arr[i] = help[i-l];}

递归版的复杂度

时间复杂度:$O(nlogn)$, 系统压栈高度为logn,merge函数时间$O(n)$， 乘起来就是$O(nlogn)$。
空间复杂度:$O(n)$， 借助了一个临时数组help.

非递归实现

public static void mergeSort(int[] arr) {int n = arr.length;//step分组数， step为1，说明左右区间各有一个数（除非区间已经越界， 则相应调整）//先两两分组， 再以4个为一组， 8个为一组...直到单次分组已经超过数组总的元素个数就终止。for (int l, m, r, step = 1; step < n; step <<= 1) {l = 0;//后面就是讨论区间while (l < n) {//确定区间的中间下标m = l + step - 1;//判断右边界是否存在if (m + 1 >= n) {//无右侧， 不用后续merge了。break;//不存在说明单层的归并排序结束。}//求右边界r = Math.min(l + (step << 1) - 1, n - 1);//确定好了，l,m,r的值，进行合并merge(arr, l, m, r);//内层while循环进行调整l = r + 1;}}}public static void merge(int[] arr,int l, int m,int r) {int a = l;int b = m+1;int[] help = new int[r-l+1];int i = 0;while(a<=m && b<=r) {help[i++] = arr[a]<=arr[b]?arr[a++]:arr[b++];}while(a<=m) {help[i++] = arr[a++];}while(b<=r) {help[i++] = arr[b++];}for(i=l;i<=r;i++) {arr[i] = help[i-l];}}//测试用例。public static void main(String[] args) {int[] arr= {4,1,6,23,8,9,11,0,2,3,4,4,4,4,10};System.out.println("排序前:"+Arrays.toString(arr));mergeSort(arr);System.out.println("排序后："+Arrays.toString(arr));}/*** output：* 排序前:[4, 1, 6, 23, 8, 9, 11, 0, 2, 3, 4, 4, 4, 4, 10]* 排序后：[0, 1, 2, 3, 4, 4, 4, 4, 4, 6, 8, 9, 10, 11, 23]*/

归并排序为什么如此高效， 左神说过是因为比较排序中的比较次数没有浪费。 确实如此， 比较排序可以抽象为决策树模型， 比较次数最少就是$nlogn$, 而对于三大平方的‘傻瓜式’排序算法， 因为浪费了比较次数，导致时间复杂度变高了。

练习

	//请用递归和非递归方法实现。//阐述一下归并排序的思想。public static void mergeSort(int[] nums) {/*write code here! */}

你已经学会了归并排序了， 快速试试吧!。

总结

本篇并不涉及算法的严格分析， 因为算法导论一书中已经写好了严谨有力的证明（算法导论第二章和第4章）。
下次见！