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

骑猪看日落 2023-10-01 21:12 5阅读 0赞

##  ##

**目录**

归并排序介绍:

归并排序图解：

示意图1

示意图2

归并排序详细步骤：

1.组合

2.分组

完整代码

--------------------

##    **归并排序**介绍: ##

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

## **归并排序图解：** ##

#### **示意图1** ####

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

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_11_color_FFFFFF_t_70_g_se_x_16][]

####  ####

#### **示意图2** ####

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

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_17_color_FFFFFF_t_70_g_se_x_16][]

## **归并排序详细步骤：** ##

归并排序的应用实例:  
给你一个数组, 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**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_17_color_FFFFFF_t_70_g_se_x_16 1][]

**可以看一下示意图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));
    		
    		
    		
    	}
    	
    		
    
    }

运行结果:

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_8_color_FFFFFF_t_70_g_se_x_16][]

### **2.分组** ###

**写黑框里面的代码：**

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

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_12_color_FFFFFF_t_70_g_se_x_16][]

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

**方法：**

/**
    	 * 分
    	 * @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);
    	  
    		
    	}

**结果：**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_13_color_FFFFFF_t_70_g_se_x_16][]

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

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

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

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

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

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

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_11_color_FFFFFF_t_70_g_se_x_16 1][]

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

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_6_color_FFFFFF_t_70_g_se_x_16][]

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

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

**然后你再看下图：**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_20_color_FFFFFF_t_70_g_se_x_16][]

故此递归的顺序：

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_6_color_FFFFFF_t_70_g_se_x_16][]

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

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

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_11_color_FFFFFF_t_70_g_se_x_16 2][]

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

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

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

不理解的话，看图：

这是我们开头组合的：

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_6_color_FFFFFF_t_70_g_se_x_16 1][]

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

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

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

![d7c8ef80d14e4cfe899c6958400a2048.png][]

![ced4a674b8ed47baab4fa70bdbd853d3.png][]

**故此：**

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

**之前的：**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_11_color_FFFFFF_t_70_g_se_x_16 3][]

**通用的：**

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

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

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

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

## 完整代码 ##

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++;
    		   
    	   }
    	  
    
    		
    		
    		
    	}
    	
    		
    
    }

**结果：**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_12_color_FFFFFF_t_70_g_se_x_16 1][]

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

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_11_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/472de38e39244a95aa4cb954934a16c6.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_11,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_17_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/b31a824d7fb14ea8931ea9c9e0eed1ac.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_17,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_17_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/70d000bffa3e4e8aaff5e7f9811f8c73.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_17,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_8_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/ce16fa23f7334c4688c9e7227b8b5e2f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_8,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_12_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/7bbf1848fc3d42cf92f1332f10bd824f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_12,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_13_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/876b8a9346814658b1ba3e2e360f3732.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_13,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_11_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/1aaf56a34d9e49e09a3217c3e7c85e4e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_11,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_6_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/1a5e0f50d62b4eb08d18446af9412a5c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_6,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/d78ce40c71ff40c8874b4763ee922dfd.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_11_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/0b257c51576042edb8ed88fb838960ac.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_11,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_6_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/ff89f5f4f2574f1bbaf8925a39075ada.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_6,color_FFFFFF,t_70,g_se,x_16
[d7c8ef80d14e4cfe899c6958400a2048.png]: https://img-blog.csdnimg.cn/d7c8ef80d14e4cfe899c6958400a2048.png
[ced4a674b8ed47baab4fa70bdbd853d3.png]: https://img-blog.csdnimg.cn/ced4a674b8ed47baab4fa70bdbd853d3.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_11_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/18443b664c414f3bac9b6150204f71f9.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_11,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/486427ffcede4c039c61ae4495f600dc.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_12_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/19d396b840f74538b71b564fec9e8728.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_12,color_FFFFFF,t_70,g_se,x_16
[Java_bilibili]: https://www.bilibili.com/video/BV1E4411H73v/?spm_id_from=333.337.search-card.all.click