并归排序（mergeSort）

并归排序（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数组中。

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

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

这是第1次进入mergeSort方法,这次的的值-->low：0    high:8    desc：这个是从main方法进来的
这是第2次进入mergeSort方法,这次的的值-->low：0    high:4    desc：这个是从第一个mergeSort进来的
这是第3次进入mergeSort方法,这次的的值-->low：0    high:2    desc：这个是从第一个mergeSort进来的
这是第4次进入mergeSort方法,这次的的值-->low：0    high:1    desc：这个是从第一个mergeSort进来的
这是第5次进入mergeSort方法,这次的的值-->low：0    high:0    desc：这个是从第一个mergeSort进来的
这是第6次进入mergeSort方法,这次的的值-->low：1    high:1    desc：这个是从第二个mergeSort进来的
这是第  1  次合并方法，这次合并的数据是-->low=0   mid=0   high=1
这是第7次进入mergeSort方法,这次的的值-->low：2    high:2    desc：这个是从第二个mergeSort进来的
这是第  2  次合并方法，这次合并的数据是-->low=0   mid=1   high=2
这是第8次进入mergeSort方法,这次的的值-->low：3    high:4    desc：这个是从第二个mergeSort进来的
这是第9次进入mergeSort方法,这次的的值-->low：3    high:3    desc：这个是从第一个mergeSort进来的
这是第10次进入mergeSort方法,这次的的值-->low：4    high:4    desc：这个是从第二个mergeSort进来的
这是第  3  次合并方法，这次合并的数据是-->low=3   mid=3   high=4
这是第  4  次合并方法，这次合并的数据是-->low=0   mid=2   high=4
这是第11次进入mergeSort方法,这次的的值-->low：5    high:8    desc：这个是从第二个mergeSort进来的
这是第12次进入mergeSort方法,这次的的值-->low：5    high:6    desc：这个是从第一个mergeSort进来的
这是第13次进入mergeSort方法,这次的的值-->low：5    high:5    desc：这个是从第一个mergeSort进来的
这是第14次进入mergeSort方法,这次的的值-->low：6    high:6    desc：这个是从第二个mergeSort进来的
这是第  5  次合并方法，这次合并的数据是-->low=5   mid=5   high=6
这是第15次进入mergeSort方法,这次的的值-->low：7    high:8    desc：这个是从第二个mergeSort进来的
这是第16次进入mergeSort方法,这次的的值-->low：7    high:7    desc：这个是从第一个mergeSort进来的
这是第17次进入mergeSort方法,这次的的值-->low：8    high:8    desc：这个是从第二个mergeSort进来的
这是第  6  次合并方法，这次合并的数据是-->low=7   mid=7   high=8
这是第  7  次合并方法，这次合并的数据是-->low=5   mid=6   high=8
这是第  8  次合并方法，这次合并的数据是-->low=0   mid=4   high=8
11 12 23 44 65 67 77 88 99 

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