00:00
好,同学们,我们现在呢,就来开始用代码给大家写一遍这个归并排序,大家认真听,仔细的理解,呃,归并排序呢,我们叫merge short。没问题吧,Mar shots。好了,那现在呢,我们同样的道理,我们还是以刚才这个数组来为大家进行一个演示,大家看清楚了。那么这个数组呢?我们就以刚才讲解的这个数组为例来说,这个数字最先前是84571362。走一个啊,8457845。71362。好同学们,这个没有问题啊,8457啊写错了,84571362,好,那现在呢,我们先来写哪一部分呢?我们先来写这个合并的过程,合并的这个这这个方法,因为这个地方写的是最最难的这个合并方法,也就是说我要用代码把刚才的这个流程给大家写出来理解吗?
01:08
是有一定难度的啊,那认真听讲就可以了,来,老师开始写代码了,首先呢,我先写一个方法叫public static void什么呢?Me。啊,M me GE,好,这个单词merge,那首先你要给我传什么东西呢?首先你得把数组给我传过来,这个没问题吧?那你从哪个索引开始做,Left和这个right,你要给我中间还,我还需要一个中间值,那这个mid是干什么的呢?这个mid就是用来定位我们有序。呃,右边这个有序的。的这个这个序列的前面一个位置啊,前面这个位置好,待会会用到,所以说mid呢,我们也写到这来,还有一个呢,就是最右边right。好,把这个全屏一下吧,这样好好写一点,Write完了后呢,我们还需要一个临时数组,是这样子吧,同学们好,我先呢把这个方法的参数做一下,这个就是我们需要排序的原始数组。
02:14
就带排序的数组,这个left表示左边的,就是左边这样写啊左边。左边这个有序序列的序列的什么呀,初始索引。初始索引。当然这个是中间索引,我就不说了啊,中间索引。这个索中间索索引。待会待会大家可以看到这边是右边,右边的最右边的那个索引。这个是干什么呢?这个是用来做中转的,做。做这个中转。的这个数组就是哪个数组啊,就是同学们刚才看到的这个蓝色的这个数组,因为它所有数据要拷过来,然后他还倒持过去,它相当于是用来做中转的理解。
03:07
好,这个写完了以后呢,我们就开始来写东西了啊,首先呢,我们先把I定下来,是不是我们首先拿到这个东西,就是刚才老师讲的最左边的这个有序序列的I和最右边这个节我们要拿到,是不是,你理解我意思吧,好,现在这个I呢,我们就是。注意听讲啊,这个有点难,那么我们叫初始化,初始化什么呢?I这个I表示什么呢?表示左边,注意听啊,左边这个有序有序序列的这个。有序序列的那个初始索引。啊,初始,所以也也说再明白一点,就是它如果第一次的话,这个I就等于零,就这个你们看到的,但是这个ID有可能变化,它会移动,同样道理,有了这个东西呢,我们再写一个节,节应该等于什么呢?显然me的加一,为什么me加一啊。
04:02
因为你是右边的这个节,是不是它中间加一个一,因为你除以中间是在前面,我再加一个一就是它了,明明白意思吧,好,这个呢是初始化解。初始化节它表示什么呢?右边它其实是右边有序序列的这一个初始索引。能理解啊右边。那么有了左右两边,现在我们就还需要一个索引,T等于ten等于I。大家知道这个是干什么的吗?大家这个这个T是代表什么?大家还记不记得刚才我们在讲的时候,我们说这一个当我们找到一个合适的数据的时候,我们要把它放到这个temp来,那你想temp这边是不是也也应该有个缩影,比如说我第一次放到是temp的下边为零的位置,那下一次再放是不是temp应该放到下一个,那你怎么知道放到下一个呢?是不是应该也也有个索引指向我们temp啊?
05:01
这个能理解吧,好,我写到这里来啊,那么我写到这这个是什么呢?这个是我们T是指向写到啊指向哪里呢?指向。指向这个temp,注意听temp数组的当前索引。什么叫当前索引呢?就是变化的该是哪就是哪,好这这个初始化做完了之后,下面我们先做第一件事情,我们第一件事情是不是这样做的,要把要把左边的第一件事情是不是要把要把这个左边或者右边的数据往里面不停的拷。考完了过后,第二步是把剩余的部分再拷,再拷进去,第三步是把temp补再拷回去,其实它是分成三个流程的。是不是意思啊,第一步我们先干什么呢?先把先把左右两边两边的这一个数据。数据这个左右两边其实已经是有序的了啊,因为你在合并的时候,最小的时候不就一个数嘛,对吧,左右边这是已经有序的了的数据干什么呢?按规则。
06:06
按照规则,规则拷贝到哪里去呢?或者叫哦填充到叫填充好填充填充到哪里去呢?Temp数组。直到什么时候结束呢?直到。直到。直到左右两边有一边全部处理完毕,是不是直到左右两边。两边的这个有序序列,有序序列有一有一帮有一边处理完毕。处理完毕为止。是不是这是我做的第一第一个工作。这是我们做的第一件事情。第二件事情我们该做什么呢?大家还记不记得第二件事情是不是就应该把把如果,如果哪边有剩余,就把那边拷贝到呃,填充到依次填充到temp去,这个第二件事情是不是,诶我把这个写到这,大家认真听,第二件事情是干什么呢?将如不呃,就是一做完了过后,是不是总有一边有剩余,然后把什么呢,把有剩余的。
07:15
剩余数据的一方。一方。一边吧,一边。到。的数据依次依次全部啊,全部填充到。填充到哪里去呢?Temp去,这是第二步,第三一步是不是刚才我们分析的,第三步是干什么呢?将我们的temp数组重新拷贝到我们的,是这意思吧。第三步是干什么呢?将。将temp数组的元素元素拷贝到,拷贝到。是不是这样好,这个思路有了过后,我们开始走代码,首先这边有个Y循环。
08:00
那么什么时候结束呢?就是I如果小于,在小于等于M的这个情况下,并且。并且解小于等于right的情况下,说明我这个工作还没有结束。大家理解理解吧,就说明只要这个条件满足。就同学们看到这个条件满足,所以我们还要继续做。就继续。啊,继续。继续。那继续,我怎么怎么继续呢?同学们可以看到现在呢,我们有一段代码先写出来啊R,如果R小于等于R节。各位同学,请看这句话是什么意思?能看出来吗?这句话的意思就是说,如果左边有序序,有序序列的当前元素小于右边序列当前元素,就把谁呢?就把左边的。拷贝到数字里面去,我把这个代码写完大家看啊,这个可能需要写完大家看起来才才比较的,呃,明白。
09:04
I写完,然后呢,这边T加一,这边I加。等于一这句话呢,大家这样好理解了啊,我写到这儿就是什么呢,如果。如果我们发现左边的有序序列。的当前元素。当前元素干什么呢?诶小于或者是等于就是左边的啊,是左边的一些小于或者等于什么呢?右边的。右边有序序列的当前元素我们干什么呢?我们就把左边的这个I就是AI不是左边的吗?把左边的元素填充到temp去,即。即将左边的这一个元素,当前元素啊,这样写当前元素干不懂啊,靠背到靠背到哪里去呢?吞吐数组。
10:05
考不到这么说的,哪个位置你要这踢的。哦,这个大家看理解G就是这句话。就是O方局,然后还要做一件事情,干什么呢?要后移。因为你做完了过后,然后干什么呢?然后注意听啊,然后这个T要往后移一下。而我们这个I呢,也要往后移一下,因为你要,呃,你假如打个比方,打个比方啊,假如我们遇到这样一个情况了,这个地方还不好举例,因为这边都不是I,比如这个情况。啊,比如这个情况啊,五和六比较,五五和六比较,那么五是不是要小啊。五小是不是拷贝这边来,拷贝完了,这个I是不是要往后边移一下,就是你们现在看到的这假设是五啊,那么这个要后移一下,同时这个T是不是要后一下,准备为下一个做工作啊,明明白意思吧。应该很好理解对不对。好,那但是有一种可能性不是这样子的,是个else啊。
11:03
是不是有一种可能性是要是A就是反之嘛,就是反之怎么处理反之。反之。反之就是说现在呢,是右边的,右边的有序序列,当前元素小于左边的。有序序列,当全元素是不是我们,我们应该把右边的拷贝到temp数组去,或者叫填充到啊叫填充。这个有这个大家认真理解啊,反之将什么呢,将我就简写了啊,将右边有序有序序列的当前元素干什么拷贝到,而且拷贝到哦,我叫填充道。填充到这个temp输入。这个代码是不是跟前面很像啊,那就应该是temp什么T等于什么呢?R什么呀。是什么呢?是不是应该是熬了呀。愿意考右边的吗?
12:00
结同时呢,T是不是要后面加一没毛病,那同时结是不是要要往后面移一下。为什么呢?就跟我们刚才讲的一样的道理,比如说现在这个一是小于四的,那么我们把这个节拷贝到这边去,同时节往后移,同时T往后移。能理解吧,好,那么当我们这个Y循环结束以后,同学们想。是不是我们我们这第一件事情就做完了呀。有问题吗,同学们?没没有问题吧,这个应该大家还是比较好理解的,那么第二步呢,那但是你做完了过后,有没有一种可能性,就是呃,有一边剩了很多数,你比如像这个情况下,像左边就会剩七和八呀,你是不是还把把剩余的东西考填充到一,依次填充到我们的temp数组,是不是这意思,好这边代码呢,我们就要开始写了,那就写了啊,如果我们的Y循环开写了Y循环,如果这个节。
13:01
如果这个I啊,应该是判断I,如果密这种情况,各位同学,如果这个情况成立,说明什么,说明我们左边的。左边的这个有序序列还有剩余的,剩余的元素实验什么,然后就那就需要干什么呢?全部填充过去就全部就。全部。全部填充到哪里去呢?好,那这个也很简单,那就怎么写呢,叫temple。找一个什么呀,T等于什么呢?等于R什么呀,等于I。试一试吧,那呃,这个做完了以后,是不是你仍然还还要填充,因为你不知道有没有填充完T就怎么样加一。同时我们这个I是不是也要往后挪一下。
14:00
是不是,诶这个少了一个等号。没问题吧,同学们,那你反过来还有一种可能性啊,因为你右边有可能剩余,但是也也有可能是。你这说的是左边剩余,但也有可能是右边剩余啊,那右边剩余是怎样一个条件呢?是不是就是这样写的你的,如果你的节小于等于right,因为right是在后面吗?这个我就不多说了啊,也就是说这边如果是右边的。又虚了,就全部到他,那这个应该是这个没有变化,应该是解怎么样解加一。能清楚吧,那经过这一段代码过后呢,同学们。是不是我们相当于完成到了。完成到哪一步啊,完成到这一步了。那是不是还有工作把这个temp再拷回去,但是要注意啊,Temp步把它拷回去。其实呃,你不能理解成是每一次都是把temp的所有数据拷贝过去,为什么不是所有的呢?同学们想一想,你在这个进行合并的时候,是不是只有最后一次?
15:05
才是,呃,这个temp才是满的呀。那如果说你看我前面第一次,如果我们前面第一次的时候,你你真正要拷贝过去的是不是只有这个四和八拷重新拷贝到,而且它下标是要要有确定的,在这个地方是不是只是五和七拷贝到原拷贝到O瑞去,而在这一次实际上是4578拷贝到二去,并不是每一次都是考八个。明白我在说什么吗?好,如果不明白,我们写代码。那这个时候呢,把分步速度考回去,你要考虑啊,注意注意并不是每次都拷贝八个。拷贝所有的啊所有的,那那因为你每你在并的过程中,它是一个过程,所以说你看我这做一个优化,我怎么写呢,T肯定是等于零。这个没有问题。但是呢,我们这个临时左边的这个值,就是你要往那边拷贝的,我做一个临时的left,它应该等于几呢?它就等于left,因为从左边开始拷。
16:11
所以说这个temp步呢,你会发现,呃,它是这样子的,第一第我我要讲一下第一次应该是。第一次应该是这个,我我写完啊,我写完。呃,那么我们写个Y循环,先把代码写完,同学们才能理解啊,Temp left,如果它小于等于right。在这种情况下呢,我们就依次拷贝,怎么拷贝。R,然后这里面呢,是我们的pump left,是不是同学们等于什么呀?Pump t,我待会写完了你们再来看啊,我说了有时候写算法呢,你需要把代码写出来再回头思考。如果我们自己去想。一个这样的算法是想不出来的。
17:00
我在刚开始是不是说了,我们学降龙十八掌,我们有一种是理解应用,还有一种就是自创18掌。自创是很难的,所以我们现在学算法一样,你先把它写出来,然后再看理解好不好,T加一找一个,然后temp left。Turn left干什么呢?加等于一就可以了,那这句话是在做什么事情呢?我们来看一下啊,同学们。如果你理解的话,你会发现第一次。第一次你会发现呢,呃,第一次,第一次合并,注意听第一次合并时。合并时你会发现temp left其实是等于零的,而我们right呢,其实是等于一的,为啥为啥?因为你来看第一次你往回考的时候,是不是其实就这两个数。一个是零,一个是一。是这样子吧,第二次是不是二和三呢?
18:00
那第三次是谁呢?第三次其实就是他了,就应该是这个应该是零。013这样子的,也就是说第一次是零一拷贝过去,第二次合并完了后是二三这两个索引的位置拷贝过去,第三次是又把这个零三重新再拷过去,因此其实我们待会如果要要看的话,第一次是这个,第二次我我我简单写一下第二次这个temp。其实它是什么呢?它是二,这个right呢是三。Right 13,那第三次又是什么呢?第三次是零到三,因为他他把这两个合并过后,再重新考核过去,是不是就是零三了,有第三次你会看到temp。我我写不了那么多了啊哦,简写啊,Temp turn呢,它应该等于几呢?等于零,而我们的right呢?简写啊,等于几呢?等于三。那最后一次说老师最后一次呢,你这做完了,这边也可以推出来,最后一次才是真正的零和七,因为这个边是零,这边是七。
19:05
是不是最后一次才是零和七,明白吗?也就是说我可以给你们明确的说,他一共有七次进来啊。那么而且我告诉你,这是第一次,这是第二次,第三次,最后一次。最后一次,我可以负责任的告诉大家,他这两个值分别是什么呢?一个是零二,一个是七,这次才是最后一次把它拷贝过去的。明白。好,代码就写完了。那代表写完过后呢,这个合并就是我们所说的关于这个合并的方法就写完了,那么我们还差一个什么方法呢?分解的过程。是不是我们还差,还差一个什么方法呢,就是差一个分。分的分。和分加和的一个一个方法,那我开始写了啊同学们,那现在呢,写个public static什么呀,VO。Merge merge shot。
20:02
那me里面你给我传一个什么呢?好的,你给我传一个数组,仍然要传进来,好,你把你告诉我,你要left是什么,Right是什么,还得把临时数组给我传进来,是不是这个道理,因为分的过程中,我我们就要开始利用它了。好分的过程,那分的过程中我就直接写代码,只要我们的left的这个索引它小于right索引。总总是这样子的,在这个条件下呢,我就可以继续分,分的时候我先把中间这个中间这个索引拿到,就是我们的left加上right,然后再除以二,我做一个注释。这个是中间的索引。就是后面要传给人家的中间的这个索引。好。这个地方没问题了,没问题过后呢,同学们,我们这边先向左递归进行分。向左递归进行分解。
21:05
分解好进行分解呢,其实就是同学们所说的这样子,Me。少的递归的嘛,那OA传进去这个应该等于几呢?这个left。当然还等于left mid这个right呢,就等于我们传接成mid了,因为你是分成两个部分嘛,你是左右嘛,那你这个mid到到这个向左的时候,它其实就是我们最右边的那个下标,能理解吗?好,这是向左分,这个是向左分,这个是向向哪个方向呢?向右递归,递归分解。就向右递归,向右递归进进行分解。对不对。那先由递归进行分解,那是me short。等于什么玩意呢?好,显然这个地方就应该写成什么了呀,同学们是不是应该应该写成我们的M加一了呀,为什么M加一呢?
22:02
琢磨琢磨这事,你想想你这是中间这个值。是这个数中间值,那你左边是不是M加一才是,右才是右边的最左边呢?这个right要改吗?Right不用改。正补加进去,好,递归完了过后,同学们看啊同学们看,我问大家,如果我现在调用。我现在调用妹纸。请同学们思考。这个left显示零,Right是多少呢?是r.ne减一。对了,我们还差一个temp temp是不是你要把它。创建起来呀,这个temp应该有多大呢?各位朋友是不是应该等于六,我们的int谁呀,同学们。是不是应该是R点这么大。所以我们可以看到和这个这个规定排序是需要一个额外的空间。开销的说明,这说明什么呢?我们的规定。
23:03
规定排序。排序需要一个额外的。额外的这个空间没问题吧,那我问大家,我这样调用完了过后,这个数字有没有变化。请同学们思考。就是你这样做其实就做了一件什么事啊,各位同学看啊,我们叫做归并排序后。学校啊,归。归并排序后这个结果是多少呢?各位同学给大家看一下R。认识点图视病我可以负责人告诉大家,你这样做完了过后,你会发现宿主仍然是长的这个德行,因为你你你相当于这样,这你如果这样做,你就做了一件什么事情呢?你就相当于说只完成到了。这一步。那这个数组顺序没有做任何改变,大家看啊,便利给他家运行一下,你们可以看到代码呢,跟我们想的一样,看还是84571362,但是我加一句话就搞定了。
24:03
怎么呢,每分解一次就合并一次,注意这句话啊,每就是到到什么呢?到到这个合并一次。合并。啊合并,那这个合并大家想你这个递归是不是最终不停的分解分解分解分解分解到最后了,然后合并的并的时候是不是按照我们这个站的机制是从上往下,那么他最先合并的是最顶级的这个站,因为你你这两个分批分配完了845期,其实他已经是占顶了。那么这里我在合并的时候,其实先合的8457,然后是4578,然后这边这边这边最后这边。好,那如果这样子的话呢,我们可以看合并,合并的话,我们其实就调用一下merge。谁呀,刚才这个方法,那这个应该应该填什么呢?同学们,这个地方填left没有问题,这边填me也没有问题,这边填right也没问题,好到此为止,其实把这个一做。
25:05
其实这样一做的话呢,其实代码已经OK了,大家看我运行值。有点不好理解啊,你看。是不是已经OK了,或者说说怎么这么神奇呢?来我们看一下是不是我们一共一共合并了七次,我给大家先打一下。为那么我在这呢?给同学们打出我一个特别简单的一句话,叫做。笑脸。啊。叫一个笑脸吧。笑脸。啊,干脆就不管那么多了啊,我们就想一个呃,叉叉叉,我们看这个叉叉一共输出几次呢?可以告诉大家一共有七次。运行车。看一下1234567。为什么?其实刚才那个图解已经说的很清楚了,那我问大家,如果我现在这个地方再多加两个数。零再来读一下值啊零,然后呢234,请问合并多少次,那你现在是几个数啊,你现在一共是啊八个数,再加两个数,十个数,那也就是说他应该合并九次。
26:09
是么样子的呢?当然是这样子的,看啊123456789。没问题吧,好,这第一个要给他验证的,第二个我要验证是每次我们在拷贝的时候,其实他这个数据呢,呃,每次拷贝的时候,拷贝的时候并不是总是零和七是第四是零一,第二次是二三,第三次是零三,第四次应该是哪一个,第四次是这两个的下标。第五次这个第六次是这个,第七次才是最后这个明白吗?好,我可以给你给你们看一下,那现在呢,我还把这个数据再撤回去,因为这个规定不是很好理解啊,我多说两句。那现在呢,我在这儿可以给同学们打印出。我给同学们打印出这个就是temple left,等于加上我们的temple left,再加上我们的这一个什么样right,我们看一下它是不是跟我们分析的一样呢?
27:12
来,同学们运行时。我们运行我们可以看到啊,同学们看的确给我们分析一下,看第一次零一,因为你第一次合并完了过后,其实就是对零,因为你拆解到最后实际上是零一的合并,第二是零三的合并,大家看这特点看012303这个零三是怎么来的呢?是你这边这个零和这边这个三来合并的,这边是不是4567,然后4747是什么呢?是这个和这个来的。最后才是我们最顶级的零和,最后这个七把它拷贝过去,你理解吗?最后我们得到1234,诶规定排序,我看这有问题啊。怎么会有两个二呢?我们看代码是不是有有点问题,我再运行一下。怎么会有两个二啊?
28:00
呃,我再运行看看代码是哪里出了问题,运一下。诶,这个地方有问题,同学们看啊,1232457,那这个代码是有问题的,一共有几个数呢?我们少了一个数好像啊,我们再运行一下,哪个地方写错了,调一调这个很正常啊,少了应该12345678,好像少了一个六吧。六不见了,那六上哪去了呢?我们来看一下代码出的问题在什么地方。肯定是哪个地方咱们写的写错了是吧,哪个地方写错了,否则的话它不会出现这个问题,我们来看看哪里有问题呢。哪里有问题,我们来排除一下。排错一下,一下就搞定啊,出现个错误也很好,咱们刚好可以调一调,刚好可以调一调。看一下吧,哦,这个调出有点难度对不对,有点难度。
29:00
我们再看一下到底是哪出了问题,在运行运营啊,再我再看看少了一个六。六在哪边呢?六在他的这一头。那对在这一头的话,我想啊,我们往下搂一搂看看merge merge,这个没问题,不可能错,这边是进行这个两边的拷贝,应该也没有错,这边是把剩余的数把呃,右边把左边的拷贝过去,填充过去是吧,这边是把右边的填充过去,那么这边是把A填到T去,这边是把A瑞诶。这边怎么还是A呢,写错了。应该是解吧,诶你看这个地方对不对,好,没问题,调过来了,跑一跑吧,问同学看代码看到吗?看O不OK,整体没有什么思路,没有什么问题啊,大家看是不是仍然跟刚才一样零三。003完了,这边是这样子啊,456747,总体思路没问题,这是刚才我写错了一个。
30:01
下标写下标没没什么大的问题,思路完全正确啊,是这完全正确,仅仅是刚才我们写代码的时候呢,把这一个地方,嗯,把这个这个I和节,这写的时候我不小心写错了,但是整体思路完全的OK。完全OK,好,同学们,那关于我们这一个规定排序的一个实现呢,就给同学们先说到这里。好,那待会儿呢,同学们可以先把老师这段代码理解,然后呢,自己想一想哈,有什么问题,有什么想不明白的,对照代码来走一走就OK了。
我来说两句