一、什么是并归排序

归并排序 (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) { //一直继续，直到左右两边的有序序列，有一边处理完毕为止
            //如果左边的有序序列的当前元素，小于右边有序序列的当前元素，就把左边的元素插入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。

这是第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

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

次数	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://blog.csdn.net/hhy8545259/article/details/105773184

一、什么是并归排序

二、代码实现

你可能也喜欢