高级排序：归并排序（超级详细）

一.概述
归并排序是建立在归并 *** 作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

二.原理
1.尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是
1为止。 (使用递归来分组)
2.将相邻的两个子组进行合并成一个有序的大组,在归并的过程中进行排序。
3.不断的重复步骤2，直到最终只有一个组为止。

总示意图：

下面以一个例子展示归并的过程：
首先假设在归并的过程中，有以下左右两个已排好序的子组，为了将两个子组合并在一起并且在合并的过程中要排好序，这里需要一个辅助数组assist。

在此建立三个指针，分别是辅助数组上的指针i ，左子组的指针p1和右子组的指针p2。
将左子组和右子组指针上的数进行比较，小的数便放到辅助数组中，放完后该子组和辅助子组的指针++。
如上图，左子组指针都指向索引0处数字为5，右子组指针指向索引0处数字为2，2<5，所以将右子组的2放到辅助数组第一个位置，然后右子组和辅助数组的指针后移一位即++。
由上图，右子组指针此时来到索引1的位置，继续将左子组的5和右子组的8比较，5<8，将5放入辅助数组，而后依然是辅助数组的指针i和左子组p1分别++。

由上图，同理将左子组的6和右子组的8进行比较，6<8,将6放到辅助数组，p1和i分别后移一位。

当p1将7放到索引i处后，左子组的索引p1到了最后一位。而此时左子组已经全部放到了辅助数组，说明右子组剩下的数字比左子组最大的数字都要大。所以将右自组剩下的数依次都放到辅助数组就能满足左小右大的顺序。

7<8，将7放到辅助数组，指针后移。

由于左子组已经完事了，将右子组剩下的依次放入辅助数组即可。

最后将辅助数组拷贝回原数组即可。

三.Java代码实现

public class merge {
    public static  int[]assist;   //此处辅助数组assist只能是静态变量，访问实例变量必须要创建对象。
    public static void sort(int[]a) {
        assist=new int[a.length] ;//初始化辅助数组
        int lo = 0;
        int hi = a.length - 1;
        sort(a, lo, hi);}
//使用递归分组，并且每一轮将分好的子组进行merge归并
    private static void sort(int[] a, int lo, int hi) {
        if (lo >= hi) {//安全校验
            return;
        }
        int mid=lo+(hi-lo)/2;
        sort(a,lo,mid);  //将原数组分为两个子组，使用递归。
        sort(a,mid+1,hi);
        merge(a,lo,mid,hi); //分为左右子组后，调用merge进行归并
    }

    //归并的核心代码
    public static void merge(int[]a,int lo,int mid,int hi){
        //定义三个指针
        int i=lo;
        int p1=lo;
        int p2=mid+1;//右子组的第一个索引是mid+1
        while((p1<=mid)&&(p2<=hi)){ //左右自组任意指针越界即退出循环
            if(a[p1] 
运行结果：
 
[1, 2, 3, 4, 5, 6, 7, 8]
 
需要注意的地方：
 1、这里使用了sort方法的重载，sort（）只是为了输入的时候更方便一点，可以在测试时自己加入lo和hi参数而不是用sort（）方法。
 2、这里使用了递归调用，初学者需要自己体会下
 3、排序的过程在merge方法中，每分完一次都会进行归并。
 4、递归一定要有终止条件，否则栈溢出，这里的终止条件是lo>=hi ，即分组分到 只剩下一个数时不满足if条件，直接return。
 5、分组时 ，int mid=lo+(hi-lo)/2; 和 int mid=(lo+hi)/2 看似效果一样，但当数据较大时后者可能会更容易超出int的数据范围。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5685201.html