00:00
下面给大家讲一下另外一种排序算法,叫归并排序。那么归并排序它是一个什么样的东西呢?它是一种什么样的排序思想呢?我们来看一下。那么归并排序呢?叫merge sort,它是利用归并的思想实现的一种排序方法。那么该算法采用经典的分制策略,什么叫分制策略呢?分支策略它的核心的思想就是把一个大的问题分解成小的问题,然后再递归求解,这个就是它的核心思想,那么后边我们有一个算法。叫做分支算法,还会再次提到这一个分支算法。那么分制算法,它的分就是拆字呢,就制就是这个阶段呢,就是将分得的阶段得到的各个答案进行修补及分而治之,那这样讲呢,特别的抽象,就是很多同学呢,也不太明白老师在说什么,好了,我们举一个实际的案例来理解规定排序的思想,大家可以看到。
01:08
待会儿呢,我们会有一个数组,这个数组是84571362,这个数组呢,大家可以看到是一个无序的。现在我们希望它由小到大进行一个排序,大家看此时此刻这个排序的算法。他。有什么特点?它是这样子的,首先大家看它先将这个数组分解成两个部分,8457和1362,注意只是分解,并没有做任何处理啊。然后把三四、五七再分成两个部分,八四和五七。那么再把八四分成8457,然后这边是1362,也就是说它这个分的过程只是达到了一个将我们一个大的。一个部分分解成了八个小的部分,但是我要说清楚啊,同学们,它这个分的过程其实主要是为了治。
02:01
而提供一个地递归。递归的条件。这这个有点不太好理解,因为你这个分的过程其实没有干什么事,你分解的过程其实就做了一件事情,就是让他把这个,把这个递归的这个就是这个函数,比如说我们原先是这样子的,它分解分解分解分解分解到顶级的这个站的时候,那么这个时候这个每一个站的情况就不一样了,就是这个L和R左右两边就分解成最小了。然后在回来的过程中,才是一个真实的最核心的过程,也就是说分的过程比较简单,其实没有做什么实际性的工作,它主要是为了治,下一步的治而提供。这个呃,这这个条件。啊,当然有些同学说老师我还是没有听明白,没关系啊,待会儿呢,我们可以走代码的时候呢,可以再来验证一下。
03:00
啊,就再说一遍,这个分的过程其实没有什么实质性的动作。再说一遍啊,分的过程没有什么实际实质性的工作,他只主要是为了将来这个字在合并的时候提供条件,那么合并多少次呢?大家可以看到这个合并的过程。其实一共有很多次,大家看八和四它会合并。五和七会合并,五一和三会合并,六和三合并,也就是说这一次一共合并了四次。那下面四和八,五和七是两个部分,那么又合并一次,一和三和二和六合并在一起,这边又合并了两次。那最后这个地方合并了几次呢?他这个地方合并了多少次,大家可以看到。它合并了一次,因此整个合并的次数是七次。那大家可以看到它八个数据合并了七次。那大家知道意味着什么吗?意味着他这一个时间复杂度其实是很低的,你比如说我们有8万个数据。
04:04
8万个数据。那么它合并一共是多少次呢?相当于是8万减一次就可以了。那大家想假设我我这个数据量在这个基础上加了一个零,那么它这个加加了一个零,就是80万次,它合并的次数就在这个地方减一,也就说它其实是个线性增长。就它合并的次数是个线性增长,那如果这个地方你用冒泡或者是插入排序,它可是一个平方的增长,那就很恐怖了啊,待会我们再做这个说明。好,那么我们现在呢,重点来谈一下,他这个合并就是这个字,它是怎么做的,这个是个核心,我们以最后一次为例,注意啊,我以最后一次为例大家讲解,大家看这里有一张图。说的比较清晰。那那这个地方呢,我们看这个字的阶段,我们将我们需要将已经有序的子序列合并成一个有序序列。
05:04
那么比如上图的最后一次合并,注意啊,我这个这边这个图呢,显示的是最后一次合并,但并不代表我们这个合并只有一次。我刚才讲了,一共有要合并七次。明白我的意思吧,也就说我们现在研究最后一次,比如说最后一次我们是得到了,呃4578,还有一个1236是吧。是不是这样子的,然后呢,把4578和1236合并成有序子序列,它怎么合并的,大家看,首先它这有个I。大家有没有看到我我我我把这个放大一点。放大一点,大家再看呢,就看的比较清晰了,同学们可以看到。嗯,这个这这个颜色的是一个有序的,因为它分完了过后,他不停的合嘛,最后在最后一步得到了一个有序的,这边也是有序的,然后在这边有个I。有一个有一个索引,I指向左边这个有序序列的最前面,这边有个节,看清楚了,节有,呃,指向了右边这个有序序列的最前面。
06:09
然后干什么呢?他让这个II和截指向的这个数据进行比较,他发现截指向的更小一些,于是把这个一放在这个临时的一个数组中,这个数组是一个中转数组。要专门创建。好,把一放进,放进来过后呢,让这个结往后面移一下。为什么要移下呢?因为。这个一已经处理过了。把这个结处理完了过后呢,让这个新的这个结指向指向的值和这个I比较,发现二仍然比四小,于是把二又放进去。第三一步,它放完了过后,把这个结往后面再一下,让这个三跟左边这个I指向的势比较,发现三仍然小,又放进去。好,继续继续,当我们把这个节移移移到六的时候,发现呢,这个四。
07:01
就是左边这个I指向的元素呢小于六,于是把四放进去。好,然后同样道理,你这个I呢,就往后面移一下,让这个。真让这个五和指向,那么这个时候就把五填进去了。五填进去过后呢,这边继续后移,后移过去这个I就指到这了,那么I指向这里呢?让I和。这个节指向的发现六更大,把六放进去,这个时候注意听啊,关键点来了节再往后后面移一步已经没有数据了,没有数据怎么办呢?那后面不是你左边的这一个有序序列,还留了七和八怎么办?怎么办呢?把七和八分别是就按这个顺序把它拷贝到或者叫填充到我们七这个temp数组里面去,大家看清楚了没有。那么做完这个静音以后,是不是如果是最后一次的话,注意听,如果是最后一次合并的话,那么这个12345678就已经是有序了,然后再把这个临时数组里面的内容噼里啪啦一下拷贝到原数组。
08:04
这样我们最终就得到一个有序的。这个数列了。他的思想就这样子的。但是这个呃,规定排序呢,并不是像我们想的那么简单啊,就是你千万有几点大家要理解,就是千万不要理解成好像我们这个只是进行了一次合并,其实大家看到前面他一共合并了有七次。就说它分解到最后一步,不能再分解的时候,就已经开始合了,怎么合的呢?让让这个,让这个八和四进行比较,看谁大谁小,他八和四进行做的,做做这个事情的时候,也是会利用到这个temp数组。也是按照刚才那个流程,把四放进去,把八搬进去,然后再回回头,再再再把它拷回。只拷贝的时候只拷贝这前面两个数而已,明白我的意思吧。好,那么这边也是一样道理,因此它合并其实一共是七次,千万不要理解成只有一次啊啊,不要说A老师只有最后一次,不是这样子的。
09:04
好了,那么这个呢,就是我们这个归并排序的一个最基本的思想,大家也看到了,其实这里面最难的归并思想里面最难写的代码应该是哪一个过程呢?就是如图写所示的这一个并的过程,就是合并的这个过程,过程是最难的,待会儿呢,我们用代码给大家走一遍,你们就会清晰很多,而且刚才我分析到规定排序它的这个时间复杂度是比较低的。是不是因为呃,它的合并的合并的这个次数呢,其实只是你数据数据链的减一这么多次。好了,那关于归并排序的思想,我们先给同学们讲解到这里,一会儿呢,我们代码实现之。
我来说两句