vlambda博客
学习文章列表

图解归并排序,带你彻底了解清楚!

写在前面:

大家好,我是时光。

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

思维导图:

归并排序思维导图

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++];,这行代码可以保证当左右两部分的值相等的时候,先复制左边的值,这样可以保证值相等的时候两个元素的相对位置不变。

-- End --


分享点赞在看,给个 3连击呗!