归并排序介绍:

归并排序图解：

示意图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 6public 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 6public 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>rightwhile(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++;}}}

结果：