【数据结构与算法】：带你熟悉归并排序（手绘图解+leetCode原题）

.29.

发布于 2022-11-15 13:15:25

2990

发布于 2022-11-15 13:15:25

文章被收录于专栏：个人技术博客

手绘图解，带你了解归并排序。

归并排序

什么是归并排序？

归并排序，就是建立在“归并操作”基础上的一种排序方法。

归并操作：将两个有序的子序列合并成一个有序序列的过程。

我们可以把归并排序简单地理解成———将两个或两个以上已经排序好了的子序列“归并”为一个有序序列的过程。

“归并操作”（合并子序列）原理图解：

（文章中图解均由作者亲手绘制，诚意满满，请多多鼓励…） 1.首先需要申请额外的空间（L3）用来放置归并后结果，然后就是设置指针分别指向有序子序列的首位置元素：

2.比较指针指向元素的大小，较小的元素取出来，放置于提前申请好的空间当中，最后将指针向后挪动一格，之后重复操作即可：

3.当某一个指针指向了子序列的结尾，我们就可以将另一个子序列剩余的元素通通放到额外申请的空间（L3）中啦！（为了让效果更加明显，我将为L2提供增高服务( •̀ ω •́ )✧）

归并排序实现原理+图解

基本原理：将大小为N的序列分割成N个长度为1的子序列，将相邻的一对子序列进行“归并操作”，形成N/2（+1）个长度为2(或1)的有序子序列；不断重复相邻子序列的“归并操作”，直到剩下一个长度为N的有序序列。图解：当我们将图中一步步合并操作拆分开来单独看，不难发现这正是上文提到的“归并操作”，即将两个有序的子序列合并成一个有序序列。

在实现代码时，我们换个角度理解，使用分而治之的思想，即将原序列分成两个等长的子序列，再使用递归排序，最后用“归并操作”合并成完整的有序序列。

归并排序代码实现

import java.util.Arrays;

/**
 * @author .29.
 * @create 2022-09-07 7:25
 *
 *  L / l: 数组的第一个元素下标（left左边）
 *    R：  数组的最后一个元素下标（right右边）
 * mid / M:数组中间位置下标
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {44,12,59,36,62,43,94,7,35,52,85};//初始数组
        //调用递归函数排序数组：Msort(arr,0,arr.length-1)
        //使用toString方法将数组转化为字符串，方便打印：
        String arrayBefore = Arrays.toString(arr);
        String arrayAfter = Arrays.toString(Msort(arr,0,arr.length-1));
        System.out.println("排序前数组："+arrayBefore);
        System.out.println("排序后数组："+arrayAfter);
    }

    //递归排序方法（函数）
    public static int[] Msort(int[] arr,int L,int R){
        if(L == R)                                   //判断，如果数组只有一个元素，直接返回
            return arr;
        //当初始数组长度未知时，上面步骤不可或缺。

        //中间下标：(L + R) / 2 相当于 L+((R-L)/2) 相当于 L+(R-L) >> 1
        //mid = L + ((R-L) >> 1) 不易出错且运行速度更快
        int mid = L + ((R-L) >> 1);                   //中间下标

        //递归排序左半边子序列，使其有序
        Msort(arr,L,mid);
        //递归排序右半边子序列
        Msort(arr,mid + 1,R);
        //归并操作两个排序好的子序列（合并子序列）
        Merge(arr,L,mid,R);
        return arr;
    }

    //归并操作方法（函数）
    public static void Merge(int[] arr,int L,int M, int R){
        //申请额外的空间（temp[]）来存放归并后的序列
        int[] temp = new int[R-L+1];               //数组大小与初始数组一致
        int index = 0;                             //记录temp[]的下标
        int r = M + 1;                             //r代表右半子序列的首元素下标
        int l = L;
        while(l <= M && r <= R)
            //比较大小，较小的元素放入申请的空间中，同时位置向后挪动一格
            temp[index++] = arr[l]<=arr[r]?arr[l++]:arr[r++];
        //左半子序列先抵达结尾，将右子序列剩余元素放入空间
        while(r <= R)
            temp[index++] = arr[r++];
        //右半子序列先抵达结尾，将左子序列剩余元素放入空间
        while(l <= M)
            temp[index++] = arr[l++];
        //将排序好的完整序列放入原数组中
        for(int i = 0;i < R-L+1; i++){
            arr[L+i] = temp[i];
        }

    }
}

控制台输出结果：

算法分析

时间复杂度

因为算法当中运用了递归，所以我们可以借助master公式。

master公式：也叫主定理。它提供了一种通过渐近符号表示递推关系式的方法。应用Master定理可以很简便的求解递归方程。

master公式（ T [n] = a*T[n/b] + O (N^d) ）

master公式结论： ①当d<logb a时，时间复杂度为O(N^(logb a)) ②当d=logb a时，时间复杂度为O((N^d)*logN) ③当d>logb a时，时间复杂度为O(N^d)

前文递归函数中有两个子问题：

        //递归排序左半边子序列，使其有序
        Msort(arr,L,mid);
        //递归排序右半边子序列
        Msort(arr,mid + 1,R);

因为两个子序列由原始序列平等划分而来，所有两个子问题的规模一样都为n/2

有两个递归子问题，即a =  2

子问题规模为 n / 2，即b = 2

函数中剩下的过程：

        //归并操作两个排序好的子序列（合并子序列）
        Merge(arr,L,mid,R);

即：

//归并操作方法（函数）
    public static void Merge(int[] arr,int L,int M, int R){
        //申请额外的空间（temp[]）来存放归并后的序列
        int[] temp = new int[R-L+1];               //数组大小与初始数组一致
        int index = 0;                             //记录temp[]的下标
        int r = M + 1;                             //r代表右半子序列的首元素下标
        int l = L;
        while(l <= M && r <= R)
            //比较大小，较小的元素放入申请的空间中，同时位置向后挪动一格
            temp[index++] = arr[l]<=arr[r]?arr[l++]:arr[r++];
        //左半子序列先抵达结尾，将右子序列剩余元素放入空间
        while(r <= R)
            temp[index++] = arr[r++];
        //右半子序列先抵达结尾，将左子序列剩余元素放入空间
        while(l <= M)
            temp[index++] = arr[l++];
        //将排序好的完整序列放入原数组中
        for(int i = 0;i < R-L+1; i++){
            arr[L+i] = temp[i];
        }

不难看出，剩下过程的时间复杂度为O(n).

这里n的指数为1，即：d = 1

也就满足条件：②d=logb a时，时间复杂度为O((N^d)*logN)

时间复杂度：O（nlogn）

空间复杂度

需要用到一个临时数组，单次归并操作开辟的最大空间是n

空间复杂度： O（n）

稳定性

归并排序是一种稳定的排序算法。当遇到两个元素相等的情况时，优先将左半边子序列的元素放入额外申请空间中，保证相对位置不变即可。

归并排序在实际题目中的运用

题目一、排序数组

LeetCode原题链接：排序数组

题目描述：给你一个整数数组 nums，请你将该数组升序排列。

代码实现：此题思路以及实现与上文提到的归并排序代码实现基本一致，我就再敲了一遍当作复习。

class Solution {
    public int[] sortArray(int[] nums) {
        if(nums == null || nums.length < 2)
        return nums;

        Msort(nums,0,nums.length-1);
        return nums;
    }

    public int[] Msort(int[] arr,int L,int R){
        if(L == R)//数组只有一个元素，直接返回。
        return arr;
        
        int mid = L + ((R - L) >> 1);//中间元素下标
        //递归排序左子序列
        Msort(arr,L,mid);
        //递归排序右子序列
        Msort(arr,mid+1,R);
        //归并操作
        Merge(arr,L,mid,R);
        return arr;
    }

    public void Merge(int[] arr,int L,int Mid,int R){
        //创建临时数组
        int[] temp = new int[R-L+1];//尾元素下标-头元素下标+1为数组长度
        int index = 0;//表示临时数组下标
        int l = L;//首元素下标
        int r = Mid + 1;//右有序子序列首元素下标

        while(l <= Mid && r <= R)
        temp[index++] = arr[l] < arr[r]?arr[l++]:arr[r++];
        while(l <= Mid)
        temp[index++] = arr[l++];
        while(r <= R)
        temp[index++] = arr[r++];

        for(int i = 0;i < R-L+1; ++i){
            arr[L+i] = temp[i];
        }
    }
}

LeetCode提交结果如下：

题目二、剑指Offer 51.数组中的逆序对

LeetCode原题链接：数组中的逆序对题目描述：

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组，求出这个数组中的逆序对的总数。

思路：在“归并操作”比较两个子序列元素大小时，只需要在每次出现左子序列元素>右子序列元素情况时，即达成逆序对情况时，记录并累加出现的次数即可。其余思路与上文提到的的归并排序代码实现基本一致。

注意：如下图，当左子序列元素>右子序列元素时，因为两个子序列是有序的，所以应该记录的逆序对个数：

count = mid - l + 1;

class Solution {
    public int count = 0;//设置全局变量，记录逆序对个数
    public int reversePairs(int[] nums) {
        if(nums == null || nums.length < 2)
        return 0;
        
        return Msort(nums,0,nums.length-1);
    }

    public int Msort(int[] arr,int L,int R){
        if(L == R)//数组只有一个元素，直接返回。
        return 0;
        
        int mid = L + ((R - L) >> 1);//中间元素下标
        //递归排序左子序列
        Msort(arr,L,mid);
        //递归排序右子序列
        Msort(arr,mid+1,R);
        //归并操作,返回count
        return Merge(arr,L,mid,R);
    }

    public int Merge(int[] arr,int L,int Mid,int R){
        //创建临时数组
        int[] temp = new int[R-L+1];//尾元素下标-头元素下标+1为数组长度
        int index = 0;//表示临时数组下标
        int l = L;//首元素下标
        int r = Mid + 1;//右有序子序列首元素下标

        while(l <= Mid && r <= R){
            if(arr[l] <= arr[r]){
                temp[index++] = arr[l++];
            }else if(arr[l] > arr[r]){
                //左序列元素大于右序列元素，达成逆序对条件
                temp[index++] = arr[r++];
                //左子序列结尾下标-当前匀速下标+1即为达成逆序对的个数
                count += Mid-l+1;
            }
        }
        while(l <= Mid)//右子序列抵达结尾，剩余元素存入临时数组
        temp[index++] = arr[l++];
        while(r <= R)//左子序列抵达结尾，剩余元素存入临时数组
        temp[index++] = arr[r++];

        //将归并排序好的完整有序序列覆盖原序列
        for(int i = 0;i < R-L+1; ++i){
            arr[L+i] = temp[i];
        }
        //返回逆序对数量
        return count;
    }
}

提交结果：

题目三、计算右侧小于当前元素的个数

（更新于：2022.9.8） LeetCode原题链接：计算右侧小于当前元素的个数

题目描述：给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例 
输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

解题思路：功能实现的思路与上一道逆序对的算法题相似，都是以归并排序为基础，在特定情况下记录符合条件的元素个数。特定条件：当左序列元素需要放入临时空间时，就说明右序列元素前的元素都小于左序列当前元素，可画图辅助理解。需要注意的细节是，count[i] 的值需要与初始序列相应元素下标保持一致，但实际上归并排序后初始序列元素的下标已经发生改变。于是难点就在如何让记录下来的 count[i] 的值放置在对应位置。为了解决这一难点，我们需要申请空间来存放初始数组的下标，让元素与下标同步移动，从而解决下标不匹配的问题。

代码：

class Solution {
    int[] index;          //存放元素下标的数组
    int[] counts;         //用于记录右侧小于当前元素个数
    int[] tempIndex;      //临时存放排序后的下标
    int[] temp;           //临时存放归并排序后的完整序列
    public List<Integer> countSmaller(int[] nums) {
    //数组的空间与初始序列长度保持一致
        this.index = new int[nums.length];
        this.counts = new int[nums.length];
        this.tempIndex = new int[nums.length];
        this.temp = new int[nums.length];
        
        //记录初始序列各元素下标
        for(int i = 0;i < nums.length; ++i){
            index[i] = i;
        }

        Msort(nums,0,nums.length-1);//递归排序序列
         
        //创建集合对象，用于存放counts数组元素
        List<Integer> list = new ArrayList<Integer>();
        //增强for循环，将counts数组的元素依次放入集合中
        for(int num: counts){
            list.add(num);
        }
        return list;
    }

    //递归函数
    public void Msort(int[] arr,int L,int R){
        if(L == R)//数组长度为1，直接返回
        return;

        int mid = L + ((R-L) >> 1);//中间元素下标,相当于(R+L)/2
        //递归排序左子序列
        Msort(arr,L,mid);
        //递归排序右子序列
        Msort(arr,mid+1,R);
        //归并排序函数
        Merge(arr,L,mid,R);
    }

    public void Merge(int[] arr,int L,int Mid,int R){

        int l = L;//左子序列起点
        int r = Mid+1;//右子序列起点
        int p = L;//临时空间起点

        while(l <= Mid && r <= R){
            if(arr[l] <= arr[r]){//当左序列元素小于等于右序列元素
                temp[p] = arr[l];//复制入临时空间
                tempIndex[p] = index[l];//对应下标也复制入临时空间
                //右序列元素前面的元素满足条件，累加进临时空间内的对应位置
                counts[index[l]] += (r-Mid-1);
                //指针向后挪动一格
                l++;p++;
            }else{
                temp[p] = arr[r];
                tempIndex[p] = index[r];
                ++p;++r;
            }
        }
        while(l <= Mid){
            temp[p] = arr[l];
            tempIndex[p] = index[l];
            counts[index[l]] += (r-Mid-1);
            ++p;++l;
        }
        while(r <= R){
            temp[p] = arr[r];
            tempIndex[p] = index[r];
            ++p;++r;
        }

        for(int j = L;j <= R;++j){
            arr[j] = temp[j];//排序后序列覆盖初始序列
            index[j] = tempIndex[j];//排序后下标顺序覆盖原始下标顺序
        }
    }
}

提交结果：

这是我人生中的第一篇技术博客，十分感谢能读到最后的你，你的认同与支持就是对我最大的鼓励。我正行走在成长的道路上，希望能一直坚持下去，也希望这一路能有你的陪伴，共勉，屏幕前的友人。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-09-11，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度