归并排序java（内附超详解图文讲解）_java 归并排序

目录

归并排序介绍:

归并排序图解：

示意图1

示意图2

归并排序详细步骤：

1.组合

2.分组

完整代码

---

归并排序介绍:

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法，该算法采用经典的分治(divide- and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

归并排序图解：

示意图1

归并排序思想示意图1-基本思想:

示意图2

归并排序思想示意图2-合并相邻有序子序列:
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后- -次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤:

归并排序详细步骤：

归并排序的应用实例:
给你一个数组,  arr= Array(8, 4,5,7, 1,3,6,2),请使用归并排序完成排序。

为了便于大家理解 我把步骤分开：

先把最难的组合部分写完

1.组合

1.我们先写黑框的代码，也就是数组已经成为(4, 5,7,8, 1,2,3,6) 我们如何把它合成1 2 3 4 5 6 7 8

可以看一下示意图2

package suanfa;
 
import java.util.Arrays;
import java.util.Scanner;
 
public class xishuarr {
	
	public static void main(String[] args) {
		int arr[]= {8,4,5,7,1,3,6,2};
		
		//假设已经到最后一步
		int arrys[]= {4 ,5 ,7 ,8,1 ,2, 3, 6};
		int[] add=new int[8];
		//第一个参数表示传入数组{4 ,5 ,7 ,8,1 ,2, 3, 6}
		//第二个参数表示这个数组的第一个位置 即是0
		//第三个参数表示这个数组的中间位置  （0+7）/2=3
		//第四个参数 存放临时数组的
		merge(arrys,0,3,7,add);
	  
		
	}
	
/**
 * 
 * @param arr  排序的原始数组
 * @param left  左边有序序列的初始索引
 * @param mid   中间索引
 * @param right    右边索引
 * @param temp    做中转的数组
 */
	
	//4 5 7 8   1 2 3 6
	public static void merge(int[] arr,int left,int mid,int right,int[] temp) {
		int i=left;  //初始i,左边有序序列的初始索引
		int j=mid+1;  //初始j,右边有序序列的初始索引
		int t=0;       //指向temp数组的当前索引
		
		//1.
		//先把左右两边(有序)的数据按照规则填充到temp数组
		//直到左右两边的有序序列,有一边处理完毕为止
		while(i<=mid&&j<=right) {
			if(arr[i]<arr[j]) {
				temp[t]=arr[i++];
				/**
				 * 这里我们这里是：temp[t]=arr[i++];
				 * 如果不好理解，你可以写成这样：
				 * temp[t]=arr[i];i++;
				 */
				}
			else {
				temp[t]=arr[j++];
			}
			//因为无论执行if里面的语句还是else里面的语句,t都要加1,所以把t移出来.
		     t++;
		}
		
		//2.
		//把有剩余数据的一边的的数据依次全部填充到temp
		//由上述循环条件：i<=mid&&j<=right 可知 
		//此时要么要么j>right i>mid 
		while(i<=mid) {
			temp[t]=arr[i];
			t++;
			i++;
			
		}
		while(j<=right) {
			temp[t]=arr[j];
			t++;
			j++;
			
		}
		
		//3.
		//把temp的数组转移到arr上
		int n=0;
	   while(n<arr.length){
		   arr[n]=temp[n];
		   n++;
		   
	   }
	   System.out.println(Arrays.toString(arr));
		
		
		
	}
	
		
 
}
 

运行结果:

2.分组

写黑框里面的代码：

又回到初始,我们如何从把数组分成 黑框这样子呢？

 运用了递归的思想进行分：

方法：

	/**
	 * 分
	 * @param arr  排序的原始数组
	 * @param left  左边有序序列的初始索引
	
	 * @param right    右边索引
	 * @param temp    做中转的数组
	 */
		
	public static void mergeSort(int[] arr,int left,int right,int[] temp) {
		//求中间索引
		int mid=(left+right)/2;
		
 
 
		if(left<right) {
			//左边递归分解
			mergeSort(arr,left,mid,temp);
			
			//右边递归分解
			mergeSort(arr,mid+1,right,temp);
			
			System.out.println(" 最左边索引:"+left+"\t最右边边索引:"+right+"\t"+Arrays.toString(arr));
		}
	
	}

主函数：

	public static void main(String[] args) {
		int arr[]= {8,4,5,7,1,3,6,2};
		
		//假设已经到最后一步
		int arrys[]= {4 ,5 ,7 ,8,1 ,2, 3, 6};
		int[] add=new int[8];
		//第一个参数表示传入数组{4 ,5 ,7 ,8,1 ,2, 3, 6}
		//第二个参数表示这个数组的第一个位置 即是0
		//第三个参数表示这个数组的中间位置  （0+7）/2=3
		//第四个参数 存放临时数组的
//		merge(arrys,0,3,7,add);
		mergeSort(arr,0,7,add);
	  
		
	}

结果：

 

或许有一部分同学,看到 结果会有疑问。那就是 你递归基础比较差，别怕，我给你做详细讲解。

如果没有问题的，可以跳过以下疑问：

疑问1：为啥数组没有变化？

因为 我们只是分,而没有改变数组的位置

疑问2：为啥为输出7次？

如下图所示,我们总共分了7次,所以输出7次

 疑问3：最左边索引 和 最右边索引 是啥意思？

 这是为了方便大家理解 递归的顺序 特意加上去的

第一行的  左：0  右:1      表示：  最左边索引为:0  最右边索引为:1

然后你再看下图：

故此递归的顺序：

相信此时,同学们会加深对递归的顺序的了解

我们来，分析一下,我们完成的部分：

 我们完成了 数组 分 的部分,然后→   治（组合）  我们是把 2个含4个有序数字组合成 1个有序的数组。

我们可以把先前的   治（组合）从原来：把 2个含4个有序数字组合成 1个有序的数组。修改成：

把 2个含n个有序数字组合成 1个有序的数组

不理解的话，看图：

 这是我们开头组合的：

那么以下这2步 和上面那个图的区别在于：

上图：2个含有4个有序数字 组成一个有序数组

下2个图：2个含有2个有序数字 组成一个有序数组

故此：

 我们把之前只适用一种情况的代码修改成通用的

之前的：

通用的：

	
		//3.
		//把temp的数组转移到arr上
	   int n=0;
       int tempLeft=left;
	   while(tempLeft<=right){
		   arr[tempLeft]=temp[n];
		   n++;
		   tempLeft++;
		   
	   }

改好后我们在分的方法中 加入组合：

这样就能实现 每分一次 组合一次

完整代码

import java.util.Arrays;
import java.util.Scanner;
 
public class xishuarr {
	
	public static void main(String[] args) {
		int arr[]= {8,4,5,7,1,3,6,2};
	    int[] add=new int[arr.length];
	    System.out.println("排序前:"+Arrays.toString(arr));
	    System.out.println("排序过程:");
	    mergeSort(arr,0,add.length-1,add);
	    System.out.println("排序后:"+Arrays.toString(arr));
	    
	    }
	
	
	/**
	 * 分
	 * @param arr  排序的原始数组
	 * @param left  左边有序序列的初始索引
	
	 * @param right    右边索引
	 * @param temp    做中转的数组
	 */
		
	public static void mergeSort(int[] arr,int left,int right,int[] temp) {
		//求中间索引
		int mid=(left+right)/2;
		
 
 
		if(left<right) {
			//左边递归分解
			mergeSort(arr,left,mid,temp);
			
			//右边递归分解
			mergeSort(arr,mid+1,right,temp);
			
			merge(arr,left,mid,right,temp);
		
			
			System.out.println(" 最左边索引:"+left+"\t最右边边索引:"+right+"\t"+Arrays.toString(arr));
		}
	
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
/**
 * 
 * @param arr  排序的原始数组
 * @param left  左边有序序列的初始索引
 * @param mid   中间索引
 * @param right    右边索引
 * @param temp    做中转的数组
 */
	
	//4 5 7 8   1 2 3 6
	public static void merge(int[] arr,int left,int mid,int right,int[] temp) {
		int i=left;  //初始i,左边有序序列的初始索引
		int j=mid+1;  //初始j,右边有序序列的初始索引
		int t=0;       //指向temp数组的当前索引
		
		//1.
		//先把左右两边(有序)的数据按照规则填充到temp数组
		//直到左右两边的有序序列,有一边处理完毕为止
		while(i<=mid&&j<=right) {
		
			if(arr[i]<arr[j]) {
				temp[t]=arr[i++];
				/**
				 * 这里我们这里是：temp[t]=arr[i++];
				 * 如果不好理解，你可以写成这样：
				 * temp[t]=arr[i];i++;
				 */
				}
			else {
				
				temp[t]=arr[j++];
			
			}
			//因为无论执行if里面的语句还是else里面的语句,t都要加1,所以把t移出来.
	
			t++;
		 	
		}
		
		//2.
		//把有剩余数据的一边的的数据依次全部填充到temp
		//由上述循环条件：i<=mid&&j<=right 可知 
		//此时要么i>mid 要么j>right
		while(i<=mid) {
			temp[t]=arr[i];
			t++;
			i++;
			
		}
		while(j<=right) {
			temp[t]=arr[j];
			t++;
			j++;
			
		}
 
		
		
		//3.
		//把temp的数组转移到arr上
	   int n=0;
       int tempLeft=left;
	   while(tempLeft<=right){
		   arr[tempLeft]=temp[n];
		   n++;
		   tempLeft++;
		   
	   }
	  
 
		
		
		
	}
	
		
 
}

结果：

来自：【尚硅谷】数据结构与算法（Java数据结构与算法）_哔哩哔哩_bilibili