00:00
我们先看看,我们现在来看一下规定排序的它的一个基本思想。归并排序呢?它的名字叫merge sort,这个merge合并的意思,它的思想是呃,利用归并的思想思线排序,该算法采用经典的分制算法。同学们在学大数据的时候呢,应该学过那个一个reduce的操作,Map reduce一个操作,这有点类似于这个,它把它化简化简,比如打一个数据,先先把它分割分割,最后分完了过后再把它组合起来。就大数据的一个排序呢,有点类似于这个规定,它是怎么做的呢?首先它采采用的策略是先分分成一些小的问题,然后递归求解。而字。就是。而质的阶段,就将分的阶段的各个答案修补在一起,然而然后分而治之。那这个呢,我们这儿有一个有有一张图啊,这张图呢,其实还是特别形象的,这张图非常好,画的很清晰,我们来看这么一个图啊,归并排序啊,我们先来看它大一个整体的思路,同学们看这里。
01:12
这边呢,有一个数组显示啊,没有顺序的。他先分,怎么分呢?你看它把它分成一半。再把这边也分成一半,就说他找到中间这个位置,把它分成两个部分。分成两个部分以后呢,再把这个又分成两个部分,你看其实我在说又的时候,就是递归的一个过程。要用,哎,他又做这个事儿。那同学这边也是一样的。也是一样的,注意啊,它在分的时候并没有完成排序的过程哦,再说一遍啊,在分的时候可没有排序。那么这边再一分,把八和四的又分成两个部分,其实大家看到这个分的过程,其实就是把它打散的过程。就把他打散。
02:01
打散完了过后再怎么办呢?合并,合并的时候就注意听,在这个字的过程就叫合并的merge的过程呢,就包含了排序的过程,当然我们在代码里面能够看到这个思想的体现,那怎么排呢?如果你是从小到大排,它就会在合并时。来把这个,因为这个合并的时候,它就怎么,待会再看这个怎么合的啊,它把四和八,因为4比8小,它排在这五和七放这。OK,这边也一样,一三和二六。那么这个四和八合并完了过后,他再把四八和五七进行合并时呢,它会进行一个排序处理,那当然有些同学说了这个字怎么完成的,这点是比较麻烦的,就这里面呢,它思想很多,待会儿我们再看下张图,没有图是说不清楚的啊,那么四和八在合并的时候呢,你看合并完了就是4578,当然有同学可能有疑惑了,说老是诶,他怎么就合并完了就能搞一个有序的东西出来呢?下张图会说的很清晰一样,这边也是一样的道理,最后这边。
03:07
有四个已经有序了,这边也是有序,那么两个都是有序,它又合并一个新的,注意听这句话啊,在合并的时候,不是简单的把前面这个和后面这个加一下就完事了,不是因为你加的过程,你不敢保证这里面的数据都比它大。是不是不敢保证,所以说从这个字的过程里面来看,这个肯定是一个复杂点,就是它的核心。啊,同学们可以看到它的这个,呃,规定排序的核心应该还是在merge这个过程。这就是为什么把它叫做归并的一个原因,那从左边这个图可以看到,这种结构很像一棵完全二叉树,本文的规定排序采用的递归去实现。那么我们。我们来看看,就是这个字到底是怎么制起来的,来看下张图,下面呢,我有两这张图,很经典的一张图啊,来,我们一起看。
04:05
跟着我的这个思路来说啊,这个。这个就是你把代码写出来,你你如果不看这个也看不懂,来看这里,我们再来看字的阶段,我们需要将两个已有的子序列合并成一个有序序列,比如大家看我说的是比如,但也说我只找了一个字的过程。啊,我找的是哪一个字呢,我我找的是最后。这个字的过程,当然你最后这个字的过程和前面这个这个字的过程,就是合并的过程和后面这个一样,所以说我找一个比较复杂的来看啊,找最后这一次,注意啊,我再说一遍,不是这个合并的过程只有一次,合并过程是很多次的。他在这个过程中,他你看他合并几次了。这一次,两次,三次,四次,五次,六次七次。我只讲。最后这一次,那么最后一次呢,他是怎么做的呢?来看代码。
05:01
首先你看他是怎么玩的啊。它这里会有个指针。这个指针呢,到时可能在代码里面叫L。OK,这边。因为它在合并的时候,这两边是分开的,这边有个指针L,这边有个L。啊,那当然他有可能叫做,哎,我把这个名字叫啊,这个地方它取的名字叫I。叫I这边叫杰。那么他怎么办呢?他先比较四合一,谁大谁小。如果他发现是这个一小于四,那说明谁应该放到一个数组里面,它这边做了一个临时数组,看到没有这个temp,这个temp是一个临时数组,是个是个空数组。这个数组的大小会和你最初始的那个数据的大小一样,就好像呃,我我我事先整了一个空数组,这个空数组跟你原先那个带排序的数组大小一样,于是他把这个一就先扔过来。
06:00
这个很简单,直接赋值就行了。这个做这个做完了以后呢,这边就要这个结就就往后面移动一把。为什么要移动呢?因为你这个移不是已经进去了吗。说到一个移动,但这边不要动。为什么不要动,因为你还没有比较呢,还没有进去呢,好,再进行这两个比较,就是就是就是四和这个二的比较,那四和四和二的比较呢,发现二还小,于是把这个二再往里面扔到我们temp的第二个位置。同时把这个勾继续往后面移一下,因为我谁进去了,我就往往后面移一下。再进行比较,发现这个呃,这个这个右边的。这个这个数组,这个有序数组呢,三还比四小,于是把这个三再扔进去。把这个三再扔进去过后,注意听这个再往后面移一下,再往后面一下呢,我们再进行下值比较,发现你这个六和四比较四小,于是这边就把四扔到了第四个位置。
07:02
看清楚了,好,以此类推,以此类推,最后呢,呃,最后看到这里啊,这种这种比较要重复的不停的填入,这时将左边剩余的七和八再填入,大家看,最后我我们看啊呃,当我们比到七和八的时候,请问是不是这个六也会扔到这里面去啊啊五五克林进去了。五进去的时候,这个这个又这个I就已经指到七了,走到七了,那么呃,七和六比较,这个六也进去了。六也已经到这个位置了,但是这个不不能再移了,因为这边已经做完了,当做完了过后,我们继续判断哪一个就是哪一个,这个有序列表还没有,还还有数据,如果还有数据,就把这个七和八统一的再扔,按照这个顺序扔到这个后面去就完事了。所以你看它分了几个步骤,这是第一个大的步骤。
08:00
就是按照这个比较把这个事情搞定,第二个最后还有一个步骤是什么呢?就是把剩余的。到底是哪边剩余不知道,可能是左边这个有序列表是有剩余,也可能是右边,到时候你代代码里面肯定有代码体现,然后把这个这个是第二个步骤,第二个步骤就是把剩余的部分再拷贝过去。第三个步骤还有一个大家看最后这个步骤是什么呢?最后大家看,最后要将这个temp的内容全部拷贝到。我们这个数组里面去。因为你最终是动的这个数组嘛,而不是要得到一个新的数组。说它还有一个拷贝的过程,而且我再给他说一遍啊,拷贝过程不是只有一次,它每合并一次都有一个拷贝的工作来完成。好,这个我觉得这个图已经画的很清晰了,就比较比较清晰了,那这样子的话呢,就意味着我们这个归并排序呢,其实会写两段代码。
09:03
为什么要写两端两个函数呢?因为它有两个过程,一个是分的过程,一个是质的过程。好了,我们多说无益,我们直接来看一下这个代码啊,思路我觉得大家应该理解了吧,大体应该理解了啊,这个就已经讲的很清晰了,那么我先截断。
我来说两句