mergeSort 并归排序

一、什么是并归排序
归并排序 (merge sort) 是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。
通过一张图，我们能看的更为清楚。比如我们要对
int[] arr = {11, 44, 23, 67, 88, 65,77,12,99};
这样一个数组进行排序，如果按照归并排序的思想，我们大致的实现流程是这样的。
其实就是两大步，
第一步我们需要把一个数组拆开，拆成一个一个数
第二步我们把拆开的数进行比较，小的放前面，大的放后面，就得到了两个数的有序数组，然后我们再对这些两个数的有序数组进行比较，以此类推。
二、代码实现
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) { //一直继续，直到左右两边的有序序列，有一边处理完毕为止//如果左边的有序序列的当前元素，小于右边有序序列的当前元素，就把左边的元素插入tmpif (arr[j] < arr[k]) {tmp[i++] = arr[j++];} else { //反之，把右边的元素插入tmptmp[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); //对左边序列进行归并排序，第一个mergeSortmergeSort(arr, mid + 1, high, tmp);//对右边序列进行归并排序，第二个mergeSortmerge(arr, low, mid, high, tmp);//合并两个有序序列}}}
其中，merge方法就是将传入的两段数据进行大小的比较分为以下几步：
1.先把左右两边的有序的数据按照规则填充到tmp数组中，也就是比大小
2.把剩余的数据拷贝到tmp中
3.将tmp中的数据拷贝回arr数组中。
其次是方法，这个方法主要是用来将数据拆分开，但是应为使用了递归，第一次看的时候是一脸懵逼，最后静下心来把整个过程梳理了一下，便豁然开朗。我们可以把递归函数当作栈来思考，当一个长度为9的数组进来，他被分成了两段，0～4，5～8，这是拆分的第一步，但是是归并的最后一步，所以它先被压入了栈。接着再拆分，0～1 ， 2～4，再入栈，再拆分。直到中的if (low < high)判断不满足的时候，也就是拆到了最后一步，都是一个一个的单数了，就可以一层一层的回去做归并了。我整理方法的部分流程以做参考。
我们在代码中加入一下打印参数，可以大致了解整个过程。我们把中的第一个调用的叫做第一个，第二个就叫做第二个。
这是第1次进入方法,这次的的值-->low：0high:8desc：这个是从main方法进来的
这是第2次进入方法,这次的的值-->low：0high:4desc：这个是从第一个进来的
这是第3次进入方法,这次的的值-->low：0high:2desc：这个是从第一个进来的
这是第4次进入方法,这次的的值-->low：0high:1desc：这个是从第一个进来的
这是第5次进入方法,这次的的值-->low：0high:0desc：这个是从第一个进来的
这是第6次进入方法,这次的的值-->low：1high:1desc：这个是从第二个进来的
这是第 1 次合并方法，这次合并的数据是-->low=0mid=0high=1
这是第7次进入方法,这次的的值-->low：2high:2desc：这个是从第二个进来的
这是第 2 次合并方法，这次合并的数据是-->low=0mid=1high=2
这是第8次进入方法,这次的的值-->low：3high:4desc：这个是从第二个进来的
这是第9次进入方法,这次的的值-->low：3high:3desc：这个是从第一个进来的
这是第10次进入方法,这次的的值-->low：4high:4desc：这个是从第二个进来的
这是第 3 次合并方法，这次合并的数据是-->low=3mid=3high=4
这是第 4 次合并方法，这次合并的数据是-->low=0mid=2high=4
这是第11次进入方法,这次的的值-->low：5high:8desc：这个是从第二个进来的
这是第12次进入方法,这次的的值-->low：5high:6desc：这个是从第一个进来的
这是第13次进入方法,这次的的值-->low：5high:5desc：这个是从第一个进来的
这是第14次进入方法,这次的的值-->low：6high:6desc：这个是从第二个进来的
这是第 5 次合并方法，这次合并的数据是-->low=5mid=5high=6
这是第15次进入方法,这次的的值-->low：7high:8desc：这个是从第二个进来的
这是第16次进入方法,这次的的值-->low：7high:7desc：这个是从第一个进来的
这是第17次进入方法,这次的的值-->low：8high:8desc：这个是从第二个进来的
这是第 6 次合并方法，这次合并的数据是-->low=7mid=7high=8
这是第 7 次合并方法，这次合并的数据是-->low=5mid=6high=8
这是第 8 次合并方法，这次合并的数据是-->low=0mid=4high=8
11 12 23 44 65 67 77 88 99
我把上面过程真理部分做了个表格说明，以帮助理解。
次数
low
mid
high
第一次进来的情况
第二次回来的情况
第三次回来的情况
第五次
这一次没有通过判断，所以就需要弹出方法了
第四次
这次if判断通过了，所以再次进入了第一个
第三次
这次if判断通过了，所以再次进入了第一个
第二次
这次if判断通过了，所以再次进入了第一个
第一次
这个时候是刚从main方法进来，满足if判断，所以会进入第一个
次数
low
mid
high
第一次进来的情况
第二次回来的情况
第三次回来的情况
第六次
这个是从第二个方法进来的，这个时候的if判断又不满足，所以又要弹出了
第四次
这次if判断通过了，所以再次进入了第一个
弹出后，现在的值是0和1，这个时候要执行第二个方法了
第三次
这次if判断通过了，所以再次进入了第一个
第二次
这次if判断通过了，所以再次进入了第一个
第一次
这个时候是刚从main方法进来，满足if判断，所以会进入第一个
次数
low
mid
high
第一次进来的情况
第二次回来的情况
第三次回来的情况
第四次
这次if判断通过了，所以再次进入了第一个
弹出后，现在的值是0和1，这个时候要执行第二个方法了
风水轮流转，我们又TM回来了，但是这一次事情发生了转机，这时候的我们要带着0和1这两个值进入merge方法了，merge方法不递归，完事就完事了，完事了就又要弹出了
第三次
这次if判断通过了，所以再次进入了第一个
第二次
这次if判断通过了，所以再次进入了第一个
第一次
这个时候是刚从main方法进来，满足if判断，所以会进入第一个
次数
low
mid
high
第一次进来的情况
第二次回来的情况
第三次回来的情况
第三次
这次if判断通过了，所以再次进入了第一个
现在我们来来到了这里，我们知道，这个时候已经走过了第一个方法，现在我们要带着2（因为第二个方法传入的第一个值是mid+1），2这两个值，进入第二个冒险了
第二次
这次if判断通过了，所以再次进入了第一个
第一次
这个时候是刚从main方法进来，满足if判断，所以会进入第一个
次数
low
mid
high
第一次进来的情况
第二次回来的情况
第三次回来的情况
第七次
这里我们进入了第二个方法，但是这里的if判断不满足2
第三次
这次if判断通过了，所以再次进入了第一个
现在我们来来到了这里，我们知道，这个时候已经走过了第一个方法，现在我们要带着2（因为第二个方法传入的第一个值是mid+1）， 2这两个值，进入第二个冒险了
第二次
这次if判断通过了，所以再次进入了第一个
第一次
这个时候是刚从main方法进来，满足if判断，所以会进入第一个
次数
low
mid
high
第一次进来的情况
第二次回来的情况
第三次回来的情况
第三次
这次if判断通过了，所以再次进入了第一个
现在我们来来到了这里，我们知道，这个时候已经走过了第一个方法，现在我们要带着2（因为第二个方法传入的第一个值是mid+1），2这两个值，进入第二个冒险了
我们又一次回到了这里，这次，我们都过了第一个，也走过了第二个，我们要进入merge方法了，等merge完事后，我们就又被弹出了
第二次
这次if判断通过了，所以再次进入了第一个
第一次
这个时候是刚从main方法进来，满足if判断，所以会进入第一个
次数
low
mid
high
第一次进来的情况
第二次回来的情况
第三次回来的情况
第二次
这次if判断通过了，所以再次进入了第一个
这次我们回到了这里，我们已经进入过第一个了，所以这次我们要进入的是第二个
第一次
这个时候是刚从main方法进来，满足if判断，所以会进入第一个
次数
low
mid
high
第一次进来的情况
第二次回来的情况
第三次回来的情况
第八次
这次是进入了第二个方法，这里是满足if判断的，所以我们会再进入第一个方法
第二次
这次if判断通过了，所以再次进入了第一个
这次我们回到了这里，我们已经进入过第一个了，所以这次我们要进入的是第二个
第一次
这个时候是刚从main方法进来，满足if判断，所以会进入第一个
次数
low
mid
high
第一次进来的情况
第二次回来的情况
第三次回来的情况
第九次
这里我们在第一个方法，但是不满足if判断，所以弹出
第八次
这次是进入了第二个方法，这里是满足if判断的，所以我们会再进入第一个方法
第二次
这次if判断通过了，所以再次进入了第一个
这次我们回到了这里，我们已经进入过第一个了，所以这次我们要进入的是第二个
第一次
这个时候是刚从main方法进来，满足if判断，所以会进入第一个
次数
low
mid
high
第一次进来的情况
第二次回来的情况
第三次回来的情况
第十次
这里我们在第二个方法，发现还是不满足if判断，所以我们还是会被弹出
第八次
这次是进入了第二个方法，这里是满足if判断的，所以我们会再进入第一个方法
再次回到这里，我们要进入第二个方法了
第二次
这次if判断通过了，所以再次进入了第一个
这次我们回到了这里，我们已经进入过第一个了，所以这次我们要进入的是第二个
【mergeSort并归排序】第一次
这个时候是刚从main方法进来，满足if判断，所以会进入第一个
次数
low
mid
high
第一次进来的情况
第二次回来的情况
第三次回来的情况
第八次
这次是进入了第二个方法，这里是满足if判断的，所以我们会再进入第一个方法
再次回到这里，我们要进入第二个方法了
我们又回到了这里，这一次我们要执行merge方法了，执行完，我们就又要被弹出了
第二次
这次if判断通过了，所以再次进入了第一个
这次我们回到了这里，我们已经进入过第一个了，所以这次我们要进入的是第二个
第一次
这个时候是刚从main方法进来，满足if判断，所以会进入第一个
次数
low
mid
high
第一次进来的情况
第二次回来的情况
第三次回来的情况
第二次
这次if判断通过了，所以再次进入了第一个
这次我们回到了这里，我们已经进入过第一个了，所以这次我们要进入的是第二个
经历了这么多，我们又回来了，这一次，我们要执行merge方法了，执行完之后，我们就把数组左半部分完成了
第一次
这个时候是刚从main方法进来，满足if判断，所以会进入第一个
次数
low
mid
high
第一次进来的情况
第二次回来的情况
第三次回来的情况
第一次
这个时候是刚从main方法进来，满足if判断，所以会进入第一个
再次回到这里时候，左边的部分已经结束了，我们下面要做的就是进入方法，来处理右边的部分了，聪明的你不妨自己试试