关于后端:归并排序详解及应用

33次阅读

共计 5556 个字符,预计需要花费 14 分钟才能阅读完成。

读完本文,你不仅学会了算法套路,还能够顺便去 LeetCode 上拿下如下题目:

912. 排序数组(中等)

315. 计算右侧小于以后元素的个数(艰难)

———–

始终都有很多读者说,想让我用 框架思维 讲一讲根本的排序算法,我感觉的确得讲讲,毕竟学习任何货色都讲求一个死记硬背,只有对其本质进行比拟粗浅的了解,能力运用自如。

本文就先讲归并排序,给一套代码模板,而后讲讲它在算法问题中的利用。浏览本文前我心愿你读过前文 手把手刷二叉树(纲领篇)。

我在 手把手刷二叉树(第一期)讲二叉树的时候,提了一嘴归并排序,说归并排序就是二叉树的后序遍历,过后就有很多读者留言说醍醐灌顶。

晓得为什么很多读者遇到递归相干的算法就感觉烧脑吗?因为还处在「看山是山,看水是水」的阶段。

就说归并排序吧,如果给你看代码,让你脑补一下归并排序的过程,你脑子里会呈现什么场景?

这是一个数组排序算法,所以你脑补一个数组的 GIF,在那一个个替换元素?如果是这样的话,那格局就低了。

但如果你脑海中浮现出的是一棵二叉树,甚至浮现出二叉树后序遍历的场景,那格局就高了,大概率把握了我常常强调的 框架思维,用这种形象能力学习算法就省劲多了。

那么,归并排序明明就是一个数组算法,和二叉树有什么关系?接下来我就具体讲讲。

算法思路

就这么说吧,所有递归的算法,你甭管它是干什么的,实质上都是在遍历一棵(递归)树,而后在节点(前中后序地位)上执行代码,你要写递归算法,实质上就是要通知每个节点须要做什么

你看归并排序的代码框架:

// 定义:排序 nums[lo..hi]
void sort(int[] nums, int lo, int hi) {if (lo == hi) {return;}
    int mid = (lo + hi) / 2;
    // 利用定义,排序 nums[lo..mid]
    sort(nums, lo, mid);
    // 利用定义,排序 nums[mid+1..hi]
    sort(nums, mid + 1, hi);

    /****** 后序地位 ******/
    // 此时两部分子数组曾经被排好序
    // 合并两个有序数组,使 nums[lo..hi] 有序
    merge(nums, lo, mid, hi);
    /*********************/
}

// 将有序数组 nums[lo..mid] 和有序数组 nums[mid+1..hi]
// 合并为有序数组 nums[lo..hi]
void merge(int[] nums, int lo, int mid, int hi);

看这个框架,也就明确那句经典的总结:归并排序就是先把左半边数组排好序,再把右半边数组排好序,而后把两半数组合并。

上述代码和二叉树的后序遍历很像:

/* 二叉树遍历框架 */
void traverse(TreeNode root) {if (root == null) {return;}
    traverse(root.left);
    traverse(root.right);
    /****** 后序地位 ******/
    print(root.val);
    /*********************/
}

再进一步,你联想一下求二叉树的最大深度的算法代码:

// 定义:输出根节点,返回这棵二叉树的最大深度
int maxDepth(TreeNode root) {if (root == null) {return 0;}
    // 利用定义,计算左右子树的最大深度
    int leftMax = maxDepth(root.left);
    int rightMax = maxDepth(root.right);
    // 整棵树的最大深度等于左右子树的最大深度取最大值,// 而后再加上根节点本人
    int res = Math.max(leftMax, rightMax) + 1;

    return res;
}

是不是更像了?

前文 手把手刷二叉树(纲领篇)说二叉树问题能够分为两类思路,一类是遍历一遍二叉树的思路,另一类是合成问题的思路,根据上述类比,显然归并排序利用的是合成问题的思路(分治算法)。

归并排序的过程能够在逻辑上形象成一棵二叉树,树上的每个节点的值能够认为是 nums[lo..hi],叶子节点的值就是数组中的单个元素

而后,在每个节点的后序地位(左右子节点曾经被排好序)的时候执行 merge 函数,合并两个子节点上的子数组:

这个 merge 操作会在二叉树的每个节点上都执行一遍,执行程序是二叉树后序遍历的程序。

后序遍历二叉树大家应该曾经烂熟于心了,就是下图这个遍历程序:

联合上述根本剖析,咱们把 nums[lo..hi] 了解成二叉树的节点,srot 函数了解成二叉树的遍历函数,整个归并排序的执行过程就是以下 GIF 形容的这样:

这样,归并排序的外围思路就剖析完了,接下来只有把思路翻译成代码就行。

代码实现及剖析

只有领有了正确的思维形式,了解算法思路是不艰难的,但把思路实现成代码,也很考验一个人的编程能力

毕竟算法的工夫复杂度只是一个实践上的衡量标准,而算法的理论运行效率要思考的因素更多,比方应该防止内存的频繁调配开释,代码逻辑应尽可能简洁等等。

通过比照,《算法 4》中给出的归并排序代码兼具了简洁和高效的特点,所以咱们能够参考书中给出的代码作为归并算法模板:

class Merge {

    // 用于辅助合并有序数组
    private static int[] temp;

    public static void sort(int[] nums) {
        // 先给辅助数组开拓内存空间
        temp = new int[nums.length];
        // 排序整个数组(原地批改)sort(nums, 0, nums.length - 1);
    }

    // 定义:将子数组 nums[lo..hi] 进行排序
    private static void sort(int[] nums, int lo, int hi) {if (lo == hi) {
            // 单个元素不必排序
            return;
        }
        // 这样写是为了避免溢出,成果等同于 (hi + lo) / 2
        int mid = lo + (hi - lo) / 2;
        // 先对左半局部数组 nums[lo..mid] 排序
        sort(nums, lo, mid);
        // 再对右半局部数组 nums[mid+1..hi] 排序
        sort(nums, mid + 1, hi);
        // 将两局部有序数组合并成一个有序数组
        merge(nums, lo, mid, hi);
    }

    // 将 nums[lo..mid] 和 nums[mid+1..hi] 这两个有序数组合并成一个有序数组
    private static void merge(int[] nums, int lo, int mid, int hi) {// 先把 nums[lo..hi] 复制到辅助数组中
        // 以便合并后的后果可能间接存入 nums
        for (int i = lo; i <= hi; i++) {temp[i] = nums[i];
        }

        // 数组双指针技巧,合并两个有序数组
        int i = lo, j = mid + 1;
        for (int p = lo; p <= hi; p++) {if (i == mid + 1) {
                // 左半边数组已全副被合并
                nums[p] = temp[j++];
            } else if (j == hi + 1) {
                // 右半边数组已全副被合并
                nums[p] = temp[i++];
            } else if (temp[i] > temp[j]) {nums[p] = temp[j++];
            } else {nums[p] = temp[i++];
            }
        }
    }
}

有了之前的铺垫,这里只须要着重讲一下这个 merge 函数。

sort 函数对 nums[lo..mid]nums[mid+1..hi] 递归排序实现之后,咱们没有方法原地把它俩合并,所以须要 copy 到 temp 数组外面,而后通过相似于前文 单链表的六大技巧 中合并有序链表的双指针技巧将 nums[lo..hi] 合并成一个有序数组:

留神咱们不是在 merge 函数执行的时候 new 辅助数组,而是提前把 temp 辅助数组 new 进去了,这样就防止了在递归中频繁调配和开释内存可能产生的性能问题。

再说一下归并排序的工夫复杂度,尽管大伙儿应该都晓得是 O(NlogN),但不见得所有人都晓得这个复杂度怎么算进去的。

前文 动静布局详解 说过递归算法的复杂度计算,就是子问题个数 x 解决一个子问题的复杂度。对于归并排序来说,工夫复杂度显然集中在 merge 函数遍历 nums[lo..hi] 的过程,但每次 merge 输出的 lohi 都不同,所以不容易直观地看出工夫复杂度。

merge 函数到底执行了多少次?每次执行的工夫复杂度是多少?总的工夫复杂度是多少?这就要联合之前画的这幅图来看:

执行的次数是二叉树节点的个数,每次执行的复杂度就是每个节点代表的子数组的长度,所以总的工夫复杂度就是整棵树中「数组元素」的个数

所以从整体上看,这个二叉树的高度是 logN,其中每一层的元素个数就是原数组的长度 N,所以总的工夫复杂度就是 O(NlogN)

力扣第 912 题「排序数组」就是让你对数组进行排序,咱们能够间接套用归并排序代码模板:

class Solution {public int[] sortArray(int[] nums) {
        // 归并排序对数组进行原地排序
        Merge.sort(nums);
        return nums;
    }
}

class Merge {// 见上文}

其余利用

除了最根本的排序问题,归并排序还能够用来解决力扣第 315 题「计算右侧小于以后元素的个数」:

拍脑袋的暴力解法就不说了,嵌套 for 循环,平方级别的复杂度。

这题和归并排序什么关系呢,次要在 merge 函数,咱们在合并两个有序数组的时候,其实是能够晓得一个数字 x 后边有多少个数字比 x 小的。

具体来说,比方这个场景:

这时候咱们应该把 temp[i] 放到 nums[p] 上,因为 temp[i] < temp[j]

但就在这个场景下,咱们还能够晓得一个信息:5 前面比 5 小的元素个数就是 jmid + 1 之间的元素个数,即 2 个。

换句话说,在对 nuns[lo..hi] 合并的过程中,每当执行 nums[p] = temp[i] 时,就能够确定 temp[i] 这个元素前面比它小的元素个数为 j - mid - 1

当然,nums[lo..hi] 自身也只是一个子数组,这个子数组之后还会被执行 merge,其中元素的地位还是会扭转。但这是其余递归节点须要思考的问题,咱们只有在 merge 函数中做一些手脚,叠加每次 merge 时记录的后果即可。

发现了这个法则后,咱们只有在 merge 中增加两行代码即可解决这个问题,看解法代码:

class Solution {
    private class Pair {
        int val, id;
        Pair(int val, int id) {
            // 记录数组的元素值
            this.val = val;
            // 记录元素在数组中的原始索引
            this.id = id;
        }
    }
    
    // 归并排序所用的辅助数组
    private Pair[] temp;
    // 记录每个元素前面比本人小的元素个数
    private int[] count;
    
    // 主函数
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        count = new int[n];
        temp = new Pair[n];
        Pair[] arr = new Pair[n];
        // 记录元素原始的索引地位,以便在 count 数组中更新后果
        for (int i = 0; i < n; i++)
            arr[i] = new Pair(nums[i], i);
        
        // 执行归并排序,本题后果被记录在 count 数组中
        sort(arr, 0, n - 1);
        
        List<Integer> res = new LinkedList<>();
        for (int c : count) res.add(c);
        return res;
    }
    
    // 归并排序
    private void sort(Pair[] arr, int lo, int hi) {if (lo == hi) return;
        int mid = lo + (hi - lo) / 2;
        sort(arr, lo, mid);
        sort(arr, mid + 1, hi);
        merge(arr, lo, mid, hi);
    }
    
    // 合并两个有序数组
    private void merge(Pair[] arr, int lo, int mid, int hi) {for (int i = lo; i <= hi; i++) {temp[i] = arr[i];
        }
        
        int i = lo, j = mid + 1;
        for (int p = lo; p <= hi; p++) {if (i == mid + 1) {arr[p] = temp[j++];
            } else if (j == hi + 1) {arr[p] = temp[i++];
                // 更新 count 数组
                count[arr[p].id] += j - mid - 1;
            } else if (temp[i].val > temp[j].val) {arr[p] = temp[j++];
            } else {arr[p] = temp[i++];
                // 更新 count 数组
                count[arr[p].id] += j - mid - 1;
            }
        }
    }
}

因为在排序过程中,每个元素的索引地位会一直扭转,所以咱们用一个 Pair 类封装每个元素及其在原始数组 nums 中的索引,以便 count 数组记录每个元素之后小于它的元素个数。

你当初回头领会下我在本文结尾说那句话:

所有递归的算法,实质上都是在遍历一棵(递归)树,而后在节点(前中后序地位)上执行代码。你要写递归算法,实质上就是要通知每个节点须要做什么

有没有品出点滋味?

最初总结一下吧,本文从二叉树的角度讲了归并排序的外围思路和代码实现,同时讲了一道归并排序相干的算法题。这道算法题其实就是归并排序算法逻辑中夹杂一点私货,但依然属于比拟难的,你可能须要亲自做一遍能力了解。

那我最初留一个思考题吧,下一篇文章我会讲疾速排序,你是否可能尝试着从二叉树的角度去了解疾速排序?如果让你用一句话总结疾速排序的逻辑,你怎么形容?

好了,答案下篇文章揭晓。

点击我的头像 查看更多优质算法文章,手把手带你刷力扣,致力于把算法讲清楚!我的 算法教程 曾经取得 100k star,欢送点赞!

正文完
 0