归并排序

面试官: 聊聊归并排序

归并排序是建立在归并操作的一种高效的排序方法,该方法采用了分治的思想,比较适用于处理较大规模的数据,但比较耗内存,今天我们聊聊归并排序

排序思想

一天,小一尘和慧能坐在石头上,眺望着远方

师傅,我听山下的柳公子说他们导员要管理五六百的学生,这么多学生怎么管的过来呀

一尘

慧能

这么多人一块管理肯定是不行的,需要分开来管理

哦?分开来管理

一尘

慧能

你看每个班是不是都会选一个班长,班长把班里的学生管理好,导员把班长管理好,这不就全部学生都管理好了

慧能

这种方法其实就是分而治之,所谓分而治之就是把一个复杂庞大的问题分解成一个个小的问题去解决

分而治之: 分开来去治理

慧能

这种思想在编程中非常重要,归并排序就是一个典型的应用

哦,什么是归并排序?

一尘

慧能

所谓归并排序,就是将待排序的数分成两半后排好序,然后再将两个排好序的序列合并成一个有序序列

归并即合并之意

慧能随手画了一张图解释了一下

治:治理,这里就是将数组排序

哦,怎么去治(排序子数组),又怎么去合(合并两个有序子数组)?

一尘

慧能

至于治,你只需不断地分,一直分到只有一个元素的时候,这个时候就不治而治了(一个元素认为它有序)

慧能

对于合并,其实非常简单,我只要不断地取出两个有序数组中比较小的那一个放在一个辅助数组中(通过比较),直到把两个有序数组中的元素取完

哦,我懂了,原来是这样

一尘

代码

慧能

懂了就写一写代码吧

哦!

一尘

一尘已经了解了师傅的固定套路了

既然是不断地分,那用递归就非常简单了,什么时候终止递归呢?递归到只有一个元素的时候。一尘随手写下了如下代码

关于center = (left+right)/2的改进可看:二分查找(代码讲解块有)

很快,一尘写下了merge函数的代码

先把 arr 数组子数组合并到辅助数组,然后再把有序的辅助数组copy到 arr 数组中

一尘

一尘解释道

时间复杂度

慧能

时间复杂度分析必不可少

一尘想到:这个有点烧脑啊,元素个数为 n,运行时间是多少啊?递归,递归,再递归...

慧能

不用想递归了

师傅一下看出了一尘的心思

那怎么算呢?

一尘

慧能

其实并不复杂

假设处理的数据规模大小为 N

运行时间设为:T(N)

① 当把 N 分为两半时,那么处理大小为 N/2 子数组花费时间为:T(N/2)

② 合并花费时间与数据规模成正比:N

所以处理规模大小为N的数据所需要花费两个大小为 N/2 的子数组加上合并花费的时间

即:T(N) = 2T(N/2) + N

对于 N = 1,T(1) = 1

慧能

那么现在只需要求出T(N)即可

假设N是2的幂

慧能

对于N不是2的幂的情况,答案几乎一样

哦,复杂度原来这样算

一尘

关于时间复杂度可以看:

算法分析神器—时间复杂度

稳定性

慧能

最后说以下稳定性吧

是稳定的,因为在合并的时候,如果相等,选择前面的元素到辅助数组

一尘

关于稳定性可以看:冒泡排序(文末有)

此时太阳已经下山,一尘和师傅走在回家的路上,在路上,一尘脑子又想了一下归并排序的全过程(点击视频观看)

视频内容

原文发布于微信公众号 - 趣谈编程(gh_51e791ad9174)

原文发表时间:2018-03-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏学习力

《Java从入门到放弃》JavaSE入门篇:运算符

1646
来自专栏更流畅、简洁的软件开发方式

《你必须知道的.net》读书笔记 002——1.2 什么是继承

    1.2 什么是继承     “对于继承,就应该着手从这些容易误解与引起争论的话题来寻找关于全面认识和了解继承的答案。一点一滴摆出来,最后在对分析的要...

1889
来自专栏懒人开发

(2.5)James Stewart Calculus 5th Edition: Continuity

如果在一个区间中,不包括a, 则在 a点不连续(f is discontinuous at a)

1074
来自专栏趣谈编程

选择排序

面试官: 聊聊选择排序 选择排序是一种简单直观的算法,今天我们聊聊选择排序的思想,代码以及复杂度 排序思想 一天,小一尘和师傅下山去了,在集市中路经一个水果摊,...

3338
来自专栏技术之路

设计模式:抽象工厂方法模式

今天说一下抽象工厂模式:提供一个接口,用于创建相关或依赖对象的家族,而不需要明确指定具体类。 抽象工厂允许客户使用抽象的接口来创建一组相关的产品,而不需要知道实...

2095
来自专栏醒者呆

融会贯通——最常用的面向对象设计原则“合成复用原则”

复用一个类的时候,多使用对象的组合/聚合的关联关系,而不是继承。 之前提到的“依赖倒转原则”,是以里氏代换原则为基础的实现开闭原则目标的手段,这一条路线涉及到的...

2988
来自专栏爱撒谎的男孩

快速排序算法

1896
来自专栏专知

【专知-关关的刷题日记16】Leetcode 88. Merge Sorted Array

题目 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as on...

37010
来自专栏NetCore

驳“反驳老赵之“伪”递归”

晚上看到鹤冲天的“反驳老赵之“伪”递归”,大概看了一下,主要是反驳老赵提出的“伪”递归的概念,特别是“伪”,看起来说的都很有道理,但我个人认为,老赵说的没有错,...

2285
来自专栏C语言C++游戏编程

C语言内置运算符丰富到令人头皮发麻,C语言基础教程之运算符篇

运算符是告诉编译器执行特定数学或逻辑函数的符号。C语言内置运算符丰富,并提供以下类型的运算符 -

1291

扫码关注云+社区

领取腾讯云代金券