java算法OJ（5）归并排序
#1024程序员节|征文#
目录
1.前言
2.正文
2.1概念
2.2递归实现
2.3非递归实现
2.4时间与空间复杂度
3.小结
1.前言
哈喽大家好吖，今天来给大家分享Java中一个比较高效的算法——归并排序，这个相比于最初学的所谓的“三傻排序”（选择排序、冒泡排序和插入排序）在复杂度上优化了许多，那让我们废话不多说，开始今天的学习吧。
2.正文
2.1概念
归并排序的基本思想是将待排序的数组分成两半，采用分治法来将一个数组分成更小的子数组，递归地排序这些子数组，然后将已排序的子数组合并起来，从而得到整个列表的排序结果。
这个思路其实很容易让人想到递归，当然用递归实现起来代码也是相对比较清晰，当然也可以用非递归的方式来替换，下文都会讲解，接下来对归并排序的核心部分先进行讲解：
假设我们现在已经拿到了俩半的有序数组，那我们如何实现将俩个数组有序合并呢，这里我们采用了双指针，看图解：
假设我们现在有这样俩半数组，一个help数组用于临时存储排序过后的数组，其中a指针指向左侧的1，右指针指向左侧第一个元素2。比较这俩个元素，将较小者移入help数组，并且将指针移动，图解如下：
再继续比较当前a，b指针所指向的元素，继续进行上一步的操作，一直持续到下面这种情况：
此时a指针遍历到头已无数字，则将剩下的右侧数组的数字依次放入help数组，最后再将help数组中已经有序的元素依次拷贝进原数组即可，代码实现如下：
public static void merge(int l,int m,int r){int a = l;//左侧指针int b = m + 1;//右侧指针int i = l;//这个l适用于往help数组拷贝数字使用//这个while采用双指针的策略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++];}//最后再依次拷贝进arr数组for(int x = l;x <= r;x++){arr[x] = help[x];}}（博主是一个灵魂画手，请不要在意）
2.2递归实现
核心问题讲解完毕，接下来就是如何实现一次接着一次分半的过程了，思路如下：
- 首先传入左右边界，若当前左右边界一致，意味着当前只有一个数，天然有序
- 分半先找到中点在(l + r) / 2。
- 接下来就是分左一半，右一半
- 到最后调用核心排序的实现即可
语言上直接描述可能不太清晰，接下来我画递归决策树可能会比较清晰，还是拿上文的数组：
（我这画的很难绷啊我去）这个递归决策图还少一个向上的箭头我就先不画了，空间有限，每一次向下都是在继续分半找仍未排序的数组元素，向上即为返回来已经排序过的数组元素，代码如下：
public static void mergeSort1(int l,int r){if(l == r){return;//如果仅有一个数，则该天然有序}int m = (l + r)/2;mergeSort1(l,m);mergeSort1(m + 1,r);merge(l,m,r);}2.3非递归实现
我们也许听过一句话，任何递归的代码都可以转化为非递归，那么非递归又如何实现呢，看思路：
- 初始间隔设为1
- 进入循环，循环跳出条件为当间隔已经倍增到大于数组本身大小是，则已排序完可以跳出。
- 接下来主要的就是找左中右边界，以便传入merge方法中，唯一要注意的就是不要越界
- 最后传入即可。
代码如下：
public static void mergeSort2() {int gap = 1; // 初始间隔为1// 当gap小于n时，继续合并for (; gap < n; gap <<= 1) {for (int i = 0; i < n; i += gap * 2) {int left = i;int mid = Math.min(left + gap - 1, n - 1); // 确保mid不会越界int right = Math.min(mid + gap, n - 1); // 确保right不会越界merge(left, mid, right);}}}另外还有一种非递归实现方式，如下（这个思路也很厉害）：
public static void mergeSort2(){for(int l,m,r,step = 1;step < n;step <<= 1){l = 0;//进入循环条件是左侧仍没有跃出数组while(l < n){m = l + step - 1;if(m + 1 >= n){break;//即右侧无数字，直接返回进入下一次循环}//当右侧有数字为r赋初值r = Math.min(l + (step << 1) - 1,n - 1);//寻找真正的边界merge(l,m,r);l = r + 1;//为下次循环找好左边界}}}这里我再附上完整代码：
import java.util.Scanner;public class test {public static int MAXNUM = 100001;public static int[] arr = new int[MAXNUM];public static int[] help = new int [MAXNUM];public static int n;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();for(int i = 0;i < n;i++){arr[i] = scanner.nextInt();}//mergeSort1(0,n - 1);//递归排序mergeSort2();//非递归实现排序for(int i = 0;i < n - 1;i++){System.out.print(arr[i] + " ");}System.out.print(arr[n - 1]);}public static void mergeSort1(int l,int r){if(l == r){return;//如果仅有一个数，则该天然有序}int m = (l + r)/2;mergeSort1(l,m);mergeSort1(m + 1,r);merge(l,m,r);}public static void mergeSort2(){for(int l,m,r,step = 1;step < n;step <<= 1){l = 0;//进入循环条件是左侧仍没有跃出数组while(l < n){m = l + step - 1;if(m + 1 >= n){break;//即右侧无数字，直接返回进入下一次循环}//当右侧有数字为r赋初值r = Math.min(l + (step << 1) - 1,n - 1);//寻找真正的边界merge(l,m,r);l = r + 1;//为下次循环找好左边界}}}public static void merge(int l,int m,int r){int a = l;//左侧指针int b = m + 1;//右侧指针int i = l;//这个l适用于往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++];}//最后再依次拷贝进arr数组for(i = l;i <= r;i++){arr[i] = help[i];}}}2.4时间与空间复杂度
讲完了算法的具体实现，那它的优点到底有哪些呢
归并排序的时间复杂度是稳定的O(n log n)，无论输入数据是已经排序的还是完全逆序的。此外，归并排序的空间复杂度为O(n)，因为需要额外的空间来存储临时数组。就拿三傻排序的时间复杂度O(
)来比较，数据量一大差别就显现出来了。
那么归并排序的时间复杂度为何低呢，那是因为比较行为没有浪费！
3.小结
今天的分享到这里就结束了，喜欢的小伙伴点点赞点点关注，你的支持就是对我最大的鼓励，加油！