图解归并排序，带你彻底了解清楚！_归并排序算法

写在前面：

大家好，我是时光。

今天给大家带来的是排序算法中的归并排序，这种排序需要拆分归并。 我采用图解方式讲解，争取写透彻。话不多说，开始！

思维导图：

归并排序思维导图

1，归并排序的概念

1.1，算法介绍

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

1.2，基本思想

基本思路就是将数组分成二组 A，B，如果这二组组内的数据都是有序的，那么就可以 很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将 A，B 组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

1.3，归并的定义

将两个或两个以上的有序序列合并成一个新的有序序列：

2路归并

3路归并：将3个有序序列归并为一个新的有序序列，称为3路归并；

多路归并：将多个有序序列归并为一个新的有序序列；，称为多路归并；

1.4，如何合并有序序列

只要从比较两个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据一次取出即可。

2，算法思路

我们先搞清楚这个归并排序思想，先把逻辑搞清楚，不着急写代码。

我们首先有一个无序数组，比方说

int[] arr={4,2,8,0,5,7,1,3,9};

2.1，第一个步骤，拆分数组

我们采用2路归并，(start+end)/2处为临界点，将初始无序数组拆分成两个无序序列，然后依次循环拆分，最后再归并为一个新的有序序列；

拆分过程

首先我们来思考下判断条件，当start=end时，此时序列只有一个元素，所以这是临界点； 然后就是分组，拆分，采用递归的方式。最后再把所有拆分好的元素进行归并！

拆分代码：

public static int[] Merge_Sort(int[] arr, int start, int end) {
        //当start==end时，此时分组里只有一个元素，所以这是临界点
        if (start < end) {
            //分成左右两个分组，再进行递归
            int mid = (start + end) / 2;
            //左半边分组
            Merge_Sort(arr, start, mid);
            //右半边分组
            Merge_Sort(arr, mid + 1, end);
            //递归之后再归并归并一个大组
            Merge(arr, start, mid, end);
        }
        return arr;
    }

拆分到最后一步，每一个小序列都是单独的元素，在第二步我们再把这些元素进行归并。

2.2，第二个步骤，归并序列

拆完以后，我们需要将这些单独的元素放入一个额外空间储存，再进行排序。因此，归并排序是需要占用额外空间的。

我们这里以第一次拆分的两个分组为例，其实也就是归并的最后一步。第一次拆分之后的两个序列就是[4 2 8 0 5]和[7 1 3 9]了；但是大家要注意，我们在对这两个序列进行归并时，他们应该是早就排好序了！因为是递归拆分，在最后一次拆分的时候序列都是单独的元素，所以到归并的最后一步时，也就是左边的序列应该是[0 2 4 5 8]，右边的序列应该是[1 3 7 9]。

归并过程

归并代码：

//归并方法
public static void Merge(int[] arr, int start, int mid, int end) {
    //左边分组的起点i_start，终点i_end，也就是第一个有序序列
    int i_start = start;
    int i_end = mid;
    //右边分组的起点j_start，终点j_end，也就是第二个有序序列
    int j_start = mid + 1;
    int j_end = end;
    //额外空间初始化
    int[] temp=new int[end-start+1];
    int len = 0;
    //合并两个有序序列
    while (i_start <= i_end && j_start <= j_end) {
        //当arr[i_start]<arr[j_start]值时，将较小元素放入额外空间，反之一样
        if (arr[i_start] < arr[j_start]) {
            temp[len] = arr[i_start];
            len++;
            i_start++;
        } else {
            temp[len] = arr[j_start];
            len++;
            j_start++;
        }
    }
}

这里有个代码小技巧，注意上面合并有序序列的这个循环里面的代码，其实只要一行代码就可以搞定：

//合并两个有序序列
while (i_start <= i_end && j_start <= j_end) {
    temp[len++]=arr[i_start]<arr[j_start]?arr[i_start++]:arr[j_start++];
}

**注意：**这里还有个小问题，无论是第一个序列还是第二个序列，在比较元素大小最后的时候，有可能会多出来元素。比如说上面的第二个序列的元素9，它在与元素8比较，元素8被存入到额外空间之后，那么它自然就多出来了，我们默认把它放在额外空间的最末尾处；所以我们还需要添加以下代码，写在归并方法里面；

//i这个序列还有剩余元素
while(i_start<=i_end){
    temp[len] = arr[i_start];
    len++;
    i_start++;
}
//j这个序列还有剩余元素
while(j_start<=j_end){
    temp[len] = arr[j_start];
    len++;
    j_start++;
}

2.3，第三个步骤，额外空间覆盖原始空间

这第三个步骤就比较简单了，经过前面两个步骤之后我们就把一个无序数组拆分为两个序列，再把两个序列归并成一个有序的数组，并存放在我们开辟的额外空间里面。最后一步操作就是要把额外空间里面的元素覆盖到原空间输出即可。

我们先来看代码，再来分析：

//额外空间数据覆盖到原空间
for(int i=0;i<temp.length;i++){
    arr[start+i]=temp[i];
}

循环我们很好理解，可能大家不太明白为什么arr数组里面是从start+i开始的，首先我们来分析下：

这个i只是temp里面元素的数组下标，而arr数组下标是从start开始，比如说当我们要把分好的两个序列覆盖到原空间：

额外空间与原空间的元素位置对比

所以元素覆盖要从start+i这个位置开始，而不是简单的i开始。

3，完整代码

import java.util.Arrays;
 
public class Merge_Sort {
    public static void main(String[] args) {
        int[] arr = {4,2,8,0,5,7,1,3,9};
        System.out.println(Arrays.toString(Merge_Sort(arr, 0, arr.length - 1)));
    }
 
    /**
     * @param arr   初始数组
     * @param start 开始分组
     * @param end   结束分组
     * @return
     */
    public static int[] Merge_Sort(int[] arr, int start, int end) {
        //当start==end时，此时分组里只有一个元素，所以这是临界点
        if (start < end) {
            //分成左右两个分组，再进行递归
            int mid = (start + end) / 2;
            //左半边分组
            Merge_Sort(arr, start, mid);
            //右半边分组
            Merge_Sort(arr, mid + 1, end);
            //递归之后再归并归并一个大组
            Merge(arr, start, mid, end);
        }
        return arr;
    }
 
    //归并方法
    public static void Merge(int[] arr, int start, int mid, int end) {
        //左边分组的起点i_start，终点i_end，也就是第一个有序序列
        int i_start = start;
        int i_end = mid;
        //右边分组的起点j_start，终点j_end，也就是第二个有序序列
        int j_start = mid + 1;
        int j_end = end;
        //额外空间初始化，数组长度为end-start+1
        int[] temp=new int[end-start+1];
        int len = 0;
        //合并两个有序序列
        while (i_start <= i_end && j_start <= j_end) {
            //当arr[i_start]<arr[j_start]值时，将较小元素放入额外空间，反之一样
            if (arr[i_start] < arr[j_start]) {
                temp[len] = arr[i_start];
                len++;
                i_start++;
            } else {
                temp[len] = arr[j_start];
                len++;
                j_start++;
            }
            //temp[len++]=arr[i_start]<arr[j_start]?arr[i_start++]:arr[j_start++];
        }
 
        //i这个序列还有剩余元素
        while(i_start<=i_end){
            temp[len] = arr[i_start];
            len++;
            i_start++;
        }
        //j这个序列还有剩余元素
        while(j_start<=j_end){
            temp[len] = arr[j_start];
            len++;
            j_start++;
        }
        //辅助空间数据覆盖到原空间
        for(int i=0;i<temp.length;i++){
            arr[start+i]=temp[i];
        }
    }
}

运行结果：

结果

4，算法分析

4.1，时间复杂度

归并排序把集合进行层层拆半分组。如果集合长度为n，那么拆半的层数就是logn，每一层进行归并操作的运算量是n。所以，归并排序的时间复杂度等于每一层的运算量×层级数，即O(nlogn)。

4.2，空间复杂度

归并排序是需要用到额外空间的，但是每次归并所创建的额外空间都会随着方法结束而释放，因此单次归并操作开辟的最大空间是n。所以，归并排序的空间复杂度是O(n)。

4.3，算法稳定性

归并排序是稳定的排序算法。temp[len++]=arr[i_start]<arr[j_start]?arr[i_start++]:arr[j_start++];，这行代码可以保证当左右两部分的值相等的时候，先复制左边的值，这样可以保证值相等的时候两个元素的相对位置不变。