并归排序（mergeSort）

一、什么是并归排序

归并排序 (merge sort) 是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。

通过一张图，我们能看的更为清楚。比如我们要对

int[] arr = {11, 44, 23, 67, 88, 65,77,12,99};

这样一个数组进行排序，如果按照归并排序的思想，我们大致的实现流程是这样的。

并归排序（mergeSort）

其实就是两大步，

第一步我们需要把一个数组拆开，拆成一个一个数

第二步我们把拆开的数进行比较，小的放前面，大的放后面，就得到了两个数的有序数组，然后我们再对这些两个数的有序数组进行比较，以此类推。

二、代码实现

public class MergeSort { public static void main(String[] args) { int[] arr = {11, 44, 23, 67, 88, 65,77,12,99}; int[] tmp = new int[arr.length]; //新建一个临时数组存放 mergeSort(arr, 0, arr.length - 1, tmp); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } / * * @param arr 原始数组 * @param low 左边序列开始索引 * @param mid 中间索引 * @param high 右边结束 * @param tmp 中转数组 */ public static void merge(int[] arr, int low, int mid, int high, int[] tmp) { System.out.println(); int i = 0; //初始化i，记录tmp数组的当前索引 int j = low；//左边序列的起始索引   int k = mid + 1; //右边序列起始索引   //第一步，先把左右两边的有序的数据按照规则填充到tmp数组中   //直到左右两边的有序序列，有一边处理完毕为止 while (j <= mid && k <= high) { //一直继续，直到左右两边的有序序列，有一边处理完毕为止   //如果左边的有序序列的当前元素，小于右边有序序列的当前元素，就把左边的元素插入tmp if (arr[j] < arr[k]) { tmp[i++] = arr[j++]; } else { //反之，把右边的元素插入tmp tmp[i++] = arr[k++]; } } //第二步，把剩余的数据拷贝到tmp中   //若左边序列还有剩余，则将其全部拷贝进tmp[]中 while (j <= mid) { tmp[i++] = arr[j++]; } //若右边序列还有剩余，则将其全部拷贝进tmp[]中 while (k <= high) { tmp[i++] = arr[k++]; } //第三步，将tmp中的数据拷贝回arr数组中 for (int t = 0; t < i; t++) { arr[low + t] = tmp[t]; } }   //这个方法是用来将数组分开的 public static void mergeSort(int[] arr, int low, int high, int[] tmp) { if (low < high) { int mid = (low + high) / 2; mergeSort(arr, low, mid, tmp); //对左边序列进行归并排序，第一个mergeSort mergeSort(arr, mid + 1, high, tmp); //对右边序列进行归并排序，第二个mergeSort merge(arr, low, mid, high, tmp); //合并两个有序序列 } } }

其中，merge方法就是将传入的两段数据进行大小的比较分为以下几步：

1.先把左右两边的有序的数据按照规则填充到tmp数组中，也就是比大小

2.把剩余的数据拷贝到tmp中

3.将tmp中的数据拷贝回arr数组中。

其次是mergeSort方法，这个方法主要是用来将数据拆分开，但是应为使用了递归，第一次看的时候是一脸懵逼，最后静下心来把整个过程梳理了一下，便豁然开朗。我们可以把递归函数当作栈来思考，当一个长度为9的数组进来，他被分成了两段，0～4，5～8，这是拆分的第一步，但是是归并的最后一步，所以它先被压入了栈。接着再拆分，0～1，2～4，再入栈，再拆分。直到mergeSort中的if (low < high)判断不满足的时候，也就是拆到了最后一步，都是一个一个的单数了，就可以一层一层的回去做归并了。我整理mergeSort方法的部分流程以做参考。

我们在代码中加入一下打印参数，可以大致了解整个过程。我们把mergeSort中的第一个调用的mergeSort叫做第一个mergeSort，第二个就叫做第二个mergeSort。

我把上面过程真理部分做了个表格说明，以帮助理解。

次数	low	mid	high	第一次进来的情况	第二次回来的情况	第三次回来的情况
第五次	0		0	这一次没有通过判断，所以就需要弹出mergeSort方法了
第四次	0		1	这次if判断通过了，所以再次进入了第一个mergeSort
第三次	0		2	这次if判断通过了，所以再次进入了第一个mergeSort
第二次	0		4	这次if判断通过了，所以再次进入了第一个mergeSort
第一次	0		8	这个时候是刚从main方法进来，满足if判断，所以会进入第一个mergeSrot

次数	low	mid	high	第一次进来的情况	第二次回来的情况	第三次回来的情况
第六次	1	1	1	这个是从第二个mergeSort方法进来的，这个时候的if判断又不满足，所以又要弹出了
第四次	0	0	1	这次if判断通过了，所以再次进入了第一个mergeSort	弹出后，现在的值是0和1，这个时候要执行第二个mergeSort方法了
第三次	0	1	2	这次if判断通过了，所以再次进入了第一个mergeSort
第二次	0	2	4	这次if判断通过了，所以再次进入了第一个mergeSort
第一次	0	4	8	这个时候是刚从main方法进来，满足if判断，所以会进入第一个mergeSrot

次数	low	mid	high	第一次进来的情况	第二次回来的情况	第三次回来的情况
第四次	0	0	1	这次if判断通过了，所以再次进入了第一个mergeSort	弹出后，现在的值是0和1，这个时候要执行第二个mergeSort方法了	风水轮流转，我们又TM回来了，但是这一次事情发生了转机，这时候的我们要带着0和1这两个值进入merge方法了，merge方法不递归，完事就完事了，完事了就又要弹出了
第三次	0	1	2	这次if判断通过了，所以再次进入了第一个mergeSort
第二次	0	2	4	这次if判断通过了，所以再次进入了第一个mergeSort
第一次	0	4	8	这个时候是刚从main方法进来，满足if判断，所以会进入第一个mergeSrot

次数	low	mid	high	第一次进来的情况	第二次回来的情况	第三次回来的情况
第三次	0	1	2	这次if判断通过了，所以再次进入了第一个mergeSort	现在我们来来到了这里，我们知道，这个时候已经走过了第一个mergeSort方法，现在我们要带着2（因为第二个mergeSort方法传入的第一个值是mid+1），2这两个值，进入第二个mergeSort冒险了
第二次	0		4	这次if判断通过了，所以再次进入了第一个mergeSort
第一次	0		8	这个时候是刚从main方法进来，满足if判断，所以会进入第一个mergeSrot

次数	low	mid	high	第一次进来的情况	第二次回来的情况	第三次回来的情况
第七次	2	2	2	这里我们进入了第二个mergeSort方法，但是这里的if判断不满足2<2，所以我们又被弹出了
第三次	0	1	2	这次if判断通过了，所以再次进入了第一个mergeSort	现在我们来来到了这里，我们知道，这个时候已经走过了第一个mergeSort方法，现在我们要带着2（因为第二个mergeSort方法传入的第一个值是mid+1），2这两个值，进入第二个mergeSort冒险了
第二次	0		4	这次if判断通过了，所以再次进入了第一个mergeSort
第一次	0		8	这个时候是刚从main方法进来，满足if判断，所以会进入第一个mergeSrot

次数	low	mid	high	第一次进来的情况	第二次回来的情况	第三次回来的情况
第三次	0	1	2	这次if判断通过了，所以再次进入了第一个mergeSort	现在我们来来到了这里，我们知道，这个时候已经走过了第一个mergeSort方法，现在我们要带着2（因为第二个mergeSort方法传入的第一个值是mid+1），2这两个值，进入第二个mergeSort冒险了	我们又一次回到了这里，这次，我们都过了第一个mergeSort，也走过了第二个mergeSort，我们要进入merge方法了，等merge完事后，我们就又被弹出了
第二次	0		4	这次if判断通过了，所以再次进入了第一个mergeSort
第一次	0		8	这个时候是刚从main方法进来，满足if判断，所以会进入第一个mergeSrot


次数	low	mid	high	第一次进来的情况	第二次回来的情况	第三次回来的情况
第二次	0		4	这次if判断通过了，所以再次进入了第一个mergeSort	这次我们回到了这里，我们已经进入过第一个mergeSort了，所以这次我们要进入的是第二个mergeSort
第一次	0		8	这个时候是刚从main方法进来，满足if判断，所以会进入第一个mergeSrot

次数	low	mid	high	第一次进来的情况	第二次回来的情况	第三次回来的情况
第八次	3	3	4	这次是进入了第二个mergeSort方法，这里是满足if判断的，所以我们会再进入第一个mergeSort方法
第二次	0		4	这次if判断通过了，所以再次进入了第一个mergeSort	这次我们回到了这里，我们已经进入过第一个mergeSort了，所以这次我们要进入的是第二个mergeSort
第一次	0		8	这个时候是刚从main方法进来，满足if判断，所以会进入第一个mergeSrot

次数	low	mid	high	第一次进来的情况	第二次回来的情况	第三次回来的情况
第九次	3	3	3	这里我们在第一个mergeSort方法，但是不满足if判断，所以弹出
第八次	3	3	4	这次是进入了第二个mergeSort方法，这里是满足if判断的，所以我们会再进入第一个mergeSort方法
第二次	0		4	这次if判断通过了，所以再次进入了第一个mergeSort	这次我们回到了这里，我们已经进入过第一个mergeSort了，所以这次我们要进入的是第二个mergeSort
第一次	0		8	这个时候是刚从main方法进来，满足if判断，所以会进入第一个mergeSrot

次数	low	mid	high	第一次进来的情况	第二次回来的情况	第三次回来的情况
第十次	4	4	4	这里我们在第二个mergerSort方法，发现还是不满足if判断，所以我们还是会被弹出
第八次	3	3	4	这次是进入了第二个mergeSort方法，这里是满足if判断的，所以我们会再进入第一个mergeSort方法	再次回到这里，我们要进入第二个mergeSort方法了
第二次	0		4	这次if判断通过了，所以再次进入了第一个mergeSort	这次我们回到了这里，我们已经进入过第一个mergeSort了，所以这次我们要进入的是第二个mergeSort
第一次	0		8	这个时候是刚从main方法进来，满足if判断，所以会进入第一个mergeSrot

次数	low	mid	high	第一次进来的情况	第二次回来的情况	第三次回来的情况
第八次	3	3	4	这次是进入了第二个mergeSort方法，这里是满足if判断的，所以我们会再进入第一个mergeSort方法	再次回到这里，我们要进入第二个mergeSort方法了	我们又回到了这里，这一次我们要执行merge方法了，执行完，我们就又要被弹出了
第二次	0		4	这次if判断通过了，所以再次进入了第一个mergeSort	这次我们回到了这里，我们已经进入过第一个mergeSort了，所以这次我们要进入的是第二个mergeSort
第一次	0		8	这个时候是刚从main方法进来，满足if判断，所以会进入第一个mergeSrot

次数	low	mid	high	第一次进来的情况	第二次回来的情况	第三次回来的情况
第二次	0		4	这次if判断通过了，所以再次进入了第一个mergeSort	这次我们回到了这里，我们已经进入过第一个mergeSort了，所以这次我们要进入的是第二个mergeSort	经历了这么多，我们又回来了，这一次，我们要执行merge方法了，执行完之后，我们就把数组左半部分完成了
第一次	0		8	这个时候是刚从main方法进来，满足if判断，所以会进入第一个mergeSrot

次数	low	mid	high	第一次进来的情况	第二次回来的情况	第三次回来的情况
第一次	0		8	这个时候是刚从main方法进来，满足if判断，所以会进入第一个mergeSrot	再次回到这里时候，左边的部分已经结束了，我们下面要做的就是进入diergemergeSort方法，来处理右边的部分了，聪明的你不妨自己试试

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/230122.html原文链接：https://javaforall.net

并归排序（mergeSort）

一、什么是并归排序

二、代码实现

关于作者

全栈程序员-站长

发表回复

并归排序（mergeSort）

一、什么是并归排序

二、代码实现

关于作者

全栈程序员-站长

相关推荐

盒模型：CSS 世界的物理法则，margin 塌陷与 padding 的恩怨情仇

RIP和OSPF的区别

千问APP正式上线，阿里要打造AI超级入口！

aop动态代理机制有哪些_aop和动态代理的关系

vue使用js遍历数组和对象

判断Python输入是否为数字

发表回复