00:00
好,我们先来看一段代码,这有一段代码,把这个代码我们拿过来用一下啊,好,我直接拿过来给他看。Merge shot。Me OK。写上一段代码。OK,好,我先把这个代码写到这里,那这边代码先不要看这个merge,我们先对这个代码做一个说明。这段代码是什么呢?是呃,是一个这个规定。规定排序。好,这个规定排序,我们来做一点说明。首先看第一个R,这个R呢,就是你带排序的那个数组。待排序的数组。很简单,第二个同学们可以看到left right left和right呢,也是要指定你左边最初的左边的下标和最初的右边的下标,当然一个是零,一个是数组的长度减一。
01:03
啊,这个也很好理解,LA就是最初的。最初的左边啊,左边的这个下标,那当然是零了。那么第三一个这边right呢,就是我们最初的右边的下表。OK,最初的右边的下标。也很好理解,那这边呢,肯定到现在就是还是我们的N减一。好,第第四一个,诶同学们看到第四一个就跟刚才我说的这个,就是我们的临时数组,这个数组呢,事先你要表达。呃,从给他开辟好。这个就是我们哪哪个数组呢,同学们,这个就是我们刚才画的这个图的这个数组,就是蓝色的这个数组。因为规定排序它是这么干的。好的,那这个temp大家不要忘了啊,这个temp就是我们那个临时数组。
02:01
啊,就是。就是诶写到这儿啊,就是那个临时数组。临时宿主。那么这个数字大小不能乱写,这个数字大小呢,一定要跟你带排序的数组大小一样,事先你就把这个空间分配好,不要让它反复的进行创建,效率就会就会提高啊,这个它的大小。他是事先事先就就开辟好的,就开辟开辟好的。好的,大小呢,大小。大小和我们这一个AR保持一致。一样,这样你在排序过程中就不会去,呃出现问题,因为如果你大小不一样,它一定会报数据越界,OK,好,那这边大家看分的过程是怎么写的呢?只要我这个right大于left,我就不停的分。就是不停的分,分分分成什么样的呢?分成这个样子。
03:00
就是分成单个单个的。单个单个的啊,这就是分的过程,只要啊就是说如果。如果这个left还小于right,因为你在分的过程中,肯定left在不停的变大,而right在不停减小啊,只要这个条件还满足,就可以继续分。OK就可以去分,那代码呢,你看我怎么分的,我先你看刚才我们不是讲了吗,找到中间这个值。分一把穿进去,继续分,再分,再分,就是最后,最后不停的分的过程,肯定是right,就慢慢就不大于这个left。好,我以中间这个字,那下面这个合并的代码是在这写的。这个合并的代码是在哪里体现的呢?合并代码就是体现出整个这个流程,一共有三个节奏,第一步就是这个移动的过程不停在考,第二步就是把剩余的部分整体拷过去,第三步就是把这个temp再拷回去的三个三个节奏,好,我们看一下这个病的过程。
04:01
好,我写到这里啊,Merge。Merge是合并。是合并合并的操作,那具体来看这个代码是怎么走的呢?啊,这段代码呢,看起来有点有有点绕啊资源代码你们看一下,它里面有三个while循环。还有递归。好,我们把这个代码拿过来用一下。然后呢,我们来分析一下这个代码。OK。这边。整理一下啊好,我们看一看,看看是不是我们三部曲,首先看这里。这个I。就是左边的。左边的这个下标。哦,叫左边的指针也可以。这个I是哪一个,同学们就是。同学们看到这个东西,大家看啊,把这个画大一点,就这个。就这个一次为例,这个I就这个节,就是右边这个有序的数组的这个节,所以一个是左边的指针,一个是右边的指针。
05:07
啊,这个是是左边的指针,也可以认为是左边的索引。索引。OK,那下面这个呢,同学们看这个节就是右边的指针,为什么是,为什么是me的加一呢?因为你中间加一个一刚好就是左边,呃,右边的那一个第一第一个那个下标啊,这个就是就是右边的右边的指针。好,那么这个T是干什么的呢?再看啊,这个T是我们那个临时宿主的那个下索引,这个T是那个temp的啊这个T。T是那个temp数组的那个索引。啊,或者叫指针都可以,那这个T代表是哪一个呢?如果按照这个图来看的话,就代表我们这相当于这个T就是它。
06:01
因为你你在这做的过程中,其实也会你加了一个加了一个下次再往里面放的时候,你怎么知道加第几个呢?肯定这个T也要在不停的移动吗。啊,这个也很好理解这个T,那么我们来看看下面代码是怎么走的啊,我们看第一个while循环,第一个while循环它的作用是干什么。来看一下第一个while循环的作用。其实。它就是在找值,看到没有,你看这I就密,只要大于等于IJ在这个right大于大于这个J,看这段代码,这这个大家能看到是在做什么事吗。这个if else,大家能看到他在做什么事吗?他是不是,呃,在找左这个左边的。就是他在找,在找左边。就是从左边,呃,它是这样子的啊,就是就是从如果啊就是。
07:03
就是从这个左右两边,从左边左边的有序。有序啊,有序数组有序有序列表吧,有序列表。啊和右边的右边的有序列表。干什么呢,找到就是你看啊,如果我这这个结结这个结不是右边的吗。右边的那个那个指针,如果它大于这个I,是不是,是不是就从就从这个,就把这个这个I付给这个T啊。看到没有,就是这个应该这样讲,就是如应该这样写啊,就是说如果。如果是这个,呃,如果这个这个左左边的当前啊,这样说,如果当前的左边的有序列表的这个值小于小于当前的。
08:05
当前的右边有序列表,列表。的。的值,就将这个值拷贝到temp里面去,看到没有。这个应该能还是能看懂的啊,不是很难,所以这句话呢,有点绕啊,就是把当前左边的有序列表值,如果小于当前右边列表的值就拷贝。就把这个值,这个值拷贝到哪里去,Temp。速度中。啊,你看这个就是就是把几这个I给了这个temp,那同样你这样做了过后,Temp这个T是不是要加一啊,因为你你下一个不能再在这覆盖了,你不做,那同样这个I是不是就再往后面移动一下呀。OK,那这个L呢,就刚好就就就相反的,就是说如果。同样的道理啊,如果当前右边的。
09:03
右边的有序列表值小于当前,左边的你,你反过来一个逻辑嘛,左边的有序列表值就把这个值拷贝到temp里面去。对,是这意思吧,然后这个是不是这边就TT还是要加一对吧,T还是要加一,但是这个时候是结在往后面挪一下。哦,所以说你看这个这个外循环其实就做了这么一件事情。就不停的在干这个事儿。不停的干,就也就是说这个Y循环执行完毕以后呢,其实他就把这个事情就做完了,能能看懂吗?不是很难哈,下面来。这两句话大家能看懂是干什么吗?诶,大家看,如果幂大于I。Me大于就是me的大于I或者是J大于,那说明说明如果这个条件满足的话,是不是说明我们左边的这个有序列表还有剩余数据。能看懂吗?
10:00
就是如果这个条件满足,就是说你整个拷拷贝完了过后,相当于进入到最这个阶段。因为你左边还还留了七和八吗。对,就是这个条件,就是说如果左边还有剩余数据。如果左边有序列表,还有还有剩余数据。剩余数据就依次就依次注意看啊,这个很重要,依次拷贝啊到这个temp数组。你看你这个十分上干的,你看你个I给他了,T加1I加一知道什么条件满足了,就是这个这个I小于等于me的了啊,就是I大于这个密的了,大于I mid的,就说已经全部考完了吗。很好理解,那下面是不是一样的道理啊,如果是右边。这个大家看是不是右边有序列表,还有顺序,就一次拷贝到temp输出去。这个就是完成了我们第二个节奏。
11:02
也不是很难理解。好的,那下面这段代码我们先先看啊,这段代码其实大家也知道在干什么事,这段代码其实就是在将temp那个有序,把temp那个数据拷贝到我们那个元素组去。那大家看是怎么做的,这点有点不好理解,说老师那你这说的有点不对啊,大家看我先把这个写出来啊,下面代码,下面的代码是完成将temp。的数据拷贝到。二中。2A中,但是呢,呃,但是有些同学可能在这就看不懂了,说老师不对啊。你你说的把这个temp数据拷贝到这,那你怎么这个这个就应该是大家都从零开始走吗?你这个T从零没有问题,但是为什么你这个是从temp left走的呢?
12:00
大家注意啊,我刚才讲过了,我刚才讲过,因为你在进行这个拷贝过程,不是说最后整个这个temp步有序才一次性拷进去的,而你这个合并的过程中,其实它是在递归执行的,它是相当于把本次这样理解就对了,就是将本次。代码是完成将本次本次的temp的数据啊拷贝到二中,所以说你你这个temp确实是将样来玩的,那有些同学老师这个temp为什么从零开始走的呢?因为。你每次都是往零去走的,也就是说这个temp其实在某个合并阶段,他并没有把这个空间全部用完。但是你为了防止。假设走了狗屎运了,它刚好必须用完是吧,所以说这个temp步总是从零开始走的,但是你这个R其实是每次从这个left开始往这个累积的。这个有点不好理解,因为这个东西你就是画图写代码,你不让分析,很难分析出来。
13:04
我再说一遍啊。再说一遍,就是这个temp。他每次合并都用的是这个temp。但是每次合并的时候呢,不管是哪次合并,它都是往这个臀部的零,往零的位置往里面扔,扔完了过后。这个那个left就是指向了那个left始终是在哪里呢?那个left始终是在元素组那个位置。好,以前说你第一次合并了这有个数据,它就从这儿开始往面拷贝,再来第二次又又得到一个有有些数再往里面拷贝,它是这样来做的啊,所以说同学们这个地方看起来是有点晕,就是为什么这个并不是从零开始考的。如果如果像你们理解,可能是我把这个temp等于零,那可能同学们会这样说,哎,那temp等于零,我就整体拷贝,不是这样子的,不这样子的,因为它是将本次temp的数这个数组拷贝到R中,而二呢,应该是从left开始往这边走。这个代码。要这么去理解啊,好同学们,那这个代码呢,我们就走完了,再把这写个注释。
14:05
这个注释是将这样写啊递归递归将左边的左边的这个数据啊做成啊做做成一个有序列表。OK,这边呢是递归,将右边的这个数据啊做成有序列表。OK。好的,那呃,取决于你将来是从小到大还是从大到小,主要是看这个位置。好的,那老师这个就说完,现在说完过后呢,同学们,现在我们来测一下,那我开始写代码了,首先我先做一个比较简单的测试啊,我先写一个数据数组啊OK,呃,就以前面这个快排的数据来用一下吧。好,注意听啊,各位同学好的,那这是一个数组,同时我还要开辟一个临时的数据空间,就是六一个位。
15:07
然它的类型是int,大小呢就得是点。对吧,诶是需要减一吗,同学们。不需要检疫,不需要检疫,这个就是我们的临时数据啊。啊,临时的这个数组没有任何问题。好,下面呢,我们就来排一把排一把帽。OK,直接调me short,然后呢,我们从零开始走,然后呢,它的大小应该是点N减一,所以这个地方一定要减一啊,同学们,你如果不减一,直接数据越界。然后这个零时速度给它扔进去。代码就写完了,然后呢,我们来测一下,叫做规定排序后。规定。排序后的代码各位,那我们就来走一个吧,R点。
16:02
Make。好,同学们,先看一下代码的结果对不对?肯定是对的,没有任何问题。好,我们看到数据的确如此,下面我们来测试一下这个规定排序的一个效率问题,它到底它跟这个快牌到底哪个更快一些呢?好,我们仍然把这个代码跑过来。好的。排序前。我把这个时间进行一个输出,那同样道理啊,这个地方就要注意了,我们把这个去掉。把这个去掉,把这个去掉呢,好的。诶,我们把这个拿过来。啊,现在先不要这么狠啊,就8000万个数据可能太多,我们先整一个8万吧,先整一个8万,看看这个先先温柔一点啊,8万个数据啊,8万个数据,然后这个temp呢,自然也就变成8万了,对吧,好的,那这个地方我排序完了,我可能就不敢打了,呃,打打印这个速度太慢了,好这边就是调用的看啊调用的。
17:05
调用的规定排序法。OK,这个规定排序呢,我把我把这个时间也给大家打出来,哪里呢,就这各位。好,我们输出规定排序后的时间,好,这是排序前的时间。哦,不行,这个还不能这么干。因为真正排序应该只。统计他的时间是吧,不能把人家这个开辟数组时间算进去,所以我要把这个时间呢,往下面是不是应该挪一下才更合理一点啊。是不是因为你你这段代码不是也得花时间吗?说白了就是,呃,把这个时间打出来,其实更准确的应该。这个这句话输不输出也无所谓啊,这个应该也不是特别浪费时间,无所谓了。好,那这个时间我们进行一个比对,来各位同学。执行8万个数据看实验。
18:01
怎么样啊,我们可以看到是不是基本也是秒杀。基本就是秒杀,那现在呢,我们把它调整到。80万。80万是不是快速排序,它大概是也是不是也是零秒啊好走一个。是不是差不多啊,我们再来800万,大家还记不记得快牌是多少时间?三秒左右对不对,我们看他的时间大概怎么样呢?应该这两者的速度差不了太多。OK,但是不是他稍微好像快一点点,那也看不出来这个,呃,我们再测一下,再测一下啊。稳定一下吧。诶,他好像真的还快一点,那么这个看不出来,就8000万来测一下了。8000万,8000万,8000万快牌是多少时间?还记得吗?15秒,OK,好,我们来整一个8000万的吧,走一个。看他花了多少时间,好吧。
19:10
15秒,他呢?不知道多少时间,我们看一下可能会稍微快一点,对吧。诶多长时间呢。是不是他们的机制,因为都是大同小异嘛,其实都是按照这二分来走的是吧,所以你看时间还是比较稳定的,你是15秒,我也15秒,说他们两个效率从速度来看呢,基本上保持一致,所以以后别人问规定快还是快速排序快,那你说其实速度就是几乎是一样的,因为他的整体的机制都是按照什么呀,按照这个二分,就是分开分割,然后再合并这样一个流程。好,那关于我们这个规定排序呢,老师就给大家讲到这儿,那么这段代码,呃,如果同学们写不出来,你至少能够保证能把这个代码看懂,或者别人问规定是什么。
20:04
核心思想是什么?一个是分,一个是和,和的时候呢,分三大步,我们再整理一下。第一步就是。先把。从左右里面找到数据,往这个temp走,走完了过后呢,再把剩余的部分拷贝过去,最后将temp这一部分再把它拷回元素组。它是这么一个流程,好,我把规定给大家简单的阐述一下,那刚才我们讲的规定它的一个思路,好吧。这是规定排序的一个基本介绍。基本介绍,那规定基本介绍说完了过后呢,我们就直接来说一下规定排序的基本思想。他的一个基本思想。首先看基本思想的第一张图。这张图呢是一个概述,概述图就是可以看到它是先分成小部分,然后再把它合合并起来,它是这样一个思路。
21:07
好,然后这边完了过后呢,我们又画了一张图,这个图是合并相邻有序子序列的这么一个示意图。好,也把它放到这里来。那这个下面这个图就显得非常重要了,我把这两个图一起放过来好吧。这两个图就显得比较重要了,至少你别人说规律排序的思想,你是要答上来的。好,那么有了这个思想过后呢,我们就实行这个规定排序。排序的一个代码实现规训。排序。排序的代码实现。好的规定排序代码实现,然后我把这段代码给大家拷贝过来,Me。好,给各位同学放到这个位置。好,那关于归并排序,我们就讲到这里。
我来说两句