00:00
同学们,我们继续来学习下面一种排序算法,叫快速排序。那快速排序呢?大家听其名而知其意。就是它排。排序的速度很快,所以说取个名字叫做快速排序,又叫quick shot。那么这个快速排序它是什么意思呢?我们简单看一下它的介绍和它的排序思想,那快速排序呢,是对冒泡排序的一种改进。他是对冒泡排序的一种改进,也就是说他的这一个基本的思想呢,仍然是以冒泡的方式来处理的,那么我们来看一下他是怎么做的啊,通过一趟排序,将要排序的数据先分割成两个部分。待会儿我们有一个图可以看得更清晰,其中有一部分的数据呢,比说其中一部分的所有数据比比另外一部分所有数据要小,也就是说我们先找一个基准的值,然后把它分成两波,打个比方。
01:04
比如说现在我有一个数组,打个比方啊,比如说3235。啊,然后呢,咱们整一个呃一,然后这边。呃,再找一个,我看比这个一小一点的啊嗯。呃,举个例子吧,就这样子。我看这边有,我们这应该有一个图啊,有这个数,用这个数来举例更好一点啊,更好一点,比如说打个比方,我们先找零为这个。奇数值,然后呢,干什么呢?我把比零小的数调到零的左边,再把比零大的数调到零的右边。啊,就这个意思,那当然具体来说,它还有很多步骤要走,对不对啊,所以说他说按照这个此方法呢,把就说分成分成两拨过后呢,再按这个此方法对两部分数据进行快速排序。
02:02
相当于是个递归的过程,就是你先以零的为基准,先把比零小的放在零的。左边再把比零大的放在零的右边,但是你把比零小的放在左边过后,你不敢保证比零小的这一部分它仍然是个有序的,对不对?所以说还要对零左边的这些数进行一个快速排序的处理,当然右边的数呢,也要进行相应的处理,好我们看一个图吧。大家看这里有个图。嗯,这个图呢,它是对快速排序法的一个示意图,比较简洁。那这个图呢,它是怎么做的呢?大家看这是一个原始的数据。这是一个原始的数组,这个原始数组是20什么什么什么到11,然后这个地方呢,它跟我刚才讲的有一点区别,它是以11,它是以数组的最后这个数作为基准线来分解问题的,但思路也是一样。只是我刚才举的例子呢,是找中间这个值作为基准来进行这个分割的,好我们先看他的思想,待会儿呢,我们再具体举例,比如说他以11为基准分解,那么他先把11。
03:13
放到这,然后呢,把比11小的数扔到这边来。是不是这边都是比11小的数啊,同学们看。然后再把比11大的数扔到这边来。但是呢,你这样做完了过后,你敢保证比11小的这边的数据,就是你们看到这一头它是一个有序的吗?不敢保证。同样,右边你也不敢保证,你只敢保证这边的数比11大而已,但是你不敢保证右边的是一个有序的数列,对不对?那怎么办呢?就按刚才这个思想继续这样。处理,那你看这儿他又以五为基准线。那么把比五小的呢放在五的左左边,把比五大的呢?放在五的右边。好,你看这边只有一个数的时候呢,我就不需要再去做这个快速排序把的处理了,你你这边十和八呢,仍然用刚才这个方式,继继续进行这个分割,但看到这以八为基准,再把八呢,呃,比八大的放在八的右边,比八小的放在八的左边,那八没有,那你当然就没法放了,所以说这边做完了归是二五八四八八十,这边呢,也是按照刚才的一个思路走。
04:25
这边排完了过后就是12。21 22 28最后。当他做完了以后呢,这个结果就出来了,就是二五八十,11 12 21 22 28 30,这个就是快速排序吧的。基本示意图,但是我刚才讲过这个示意图呢,他跟我后面要举的例子有有一点不一样,它是以最后这个数做基准来进行分割的,我呢会以中间,我们后面讲的题呢,是以中间这个数来基准,那这样子啊,我再把刚才这个图再画一遍,大家就明白了,来画出这个图。
05:02
注意听讲了,思路其实是最重要的。我们来看看快速。快速排序法的一个呃,算法的排序法的一个思路分析。那么我们就以。我们就以就是待会我要做题的这个数组来讲好不好,这样大家看的比较清晰一点,好,我先把数组呢拿过来。对,这是待会我们要用的这个数组,我把它放稍微放大一点,这太小了。好梦想。那待会我我会怎么做呢?听我的思想,第一步我先找到中间这个值,那么你看这个下标为零,大家看九的下标是不是零呢?十的70的下标是几呢?012345 012345,那就是五,那就是什么呢?五除以二,五除以二,那么我们找到这个基准值呢,就是零。
06:01
明白啊,你明白的意思吧,就这个意思找你,然后我怎么办呢?我设置两个注意听啊,我会设置两个索引值,一个是指向左边的一个索引值,一个是指向右边的一个索引值。啊,比如说我从这边开始找。啊,右边我再找一个索引值。那我怎么办呢?那怎么怎么办呢,我就从左边。注意听这句话啊,我就从左边找一个比零大的数,比如说我找到了。这个字。啊,我应该从这边开始找啊,我应该从这边开始找。比如说我从这边找呢,我找到一个比零大的数是78,我从这边找比零小的数是。负的。呃,负的560,负的567。
07:00
呃,那也就是说我现在已经找到什么东西呢,我把这个颜色换一个啊,这个颜色老是相同的就不好看了。好,这个还是蓝色的,那么这个时候我从零的左边找到一个比零大的数,嗯,从呃,零的右边找到一个比零小的数,这个时候我就让他们两个交换。好,那也就是说,呃,我在交换完了过后呢,同学们看啊。我对上面这这个进行交换完了过后,我得到的数组呢是这个样的。注意听讲哈。是这个样儿的,是怎样子的呢?就是78。变这边变成了负的,呃,567好,这边放大一点,而这边这个负的567变成了多少呢?变成了78。大家发现没有?好,但是这个事情没有完成,为什么?因为你这边就是零的这边这这个数组。就是你们看到的零的这边这个书桌。它呢,不一定是一个有序的。
08:02
哦,就这边哦,这这个序列啊和零的。左边的这个呢,也不敢保证是一个有序的,因此呢,他会把刚才这个逻辑继续。往下走。继续往下走。那也就是说,假如我们这边走的话,就是相当于向右向左递归去处理负九和负的这个,呃567,那这样子处理完了后呢,我们可以看到它会得到一个什样的数组呢。啊,同学们可以看到。他这样处理完了过后,如果向右递归啊,同学们向右递归这边就会把负九和负的。呃。负的567进行一个交换,因为你这边只有两个数,于是这边呢,就会拿到这样一个值。好,这边会拿到一个怎样的数字,就是负的567,而这边是负九。如果向右向左递归,是不是这样子把它给处理完毕了,当然你处理完毕过后呢,这边如果我们是先向右处理的话,那就走这条线对不对,那如果我们向左处理会怎么办呢?同学们看向左处理是不是会把负啊这个。
09:15
2378进行处理,2378处理的时候呢,显然我照78座椅中间这个值,我把比78的数呢,调到78的右边,把比78的小数调到78的左边,以此类推,那最后这个结果我就我就简单写一下啊,我就没有去写那么清,写那么多了,最后这边呢,也将会是一个有序的,但这个地方它78条的时候呢,会有一个过程。会有个过程啊,比如说这边我们调完了过后就应该是呃,23,然后70。然后是什么呢?然后是78。对不对,那中间这个数是零。那这样子呢,我们最后得到的,因为这个中间数呢,我们没去没没有去处理,那这样子就是最后得到的这个结果呢,大家看到可以看到。
10:08
诶,我算法说了一个大概啊。然后这边。得到这个数组呢,就把这个顺序串起来就可以了,得到怎样一个数组呢?大家可以看到就是负的。567,然后负的九零,这边是23,这边是70,这边是78 OK了。好,大体就是这样的意思,那我们把这个过程称什么呢?这条线我们把它称之为向左递归。OK,这边叫做向左。向左递归。而我们这边呢,这条线就是大家看到的这这条线呢,叫做向右递归,但是它它有个顺序啊,你是向左递归和向右递归不能同时进行。就是它肯定是向左递归完了过后再向右递归,明白意思吧,我们这个是按递归的方式来处理的,它是至于你先先向左还是先向右,那么这个可以你自己来处理就就完了。
11:12
反正左边递归呢,就把左边的进行一个有序的处理,向右递归呢,就把右边的这个数组进行一个有序处理。最后。左右递归结,你左右递归结束以后,最后这个数组就是一个。有序的。游戏的,所以说我这呢,说了一个待会我们可以看到效果,待会呢我可以通过验验证,通过我们算法的这个测试,可以看到这样一个流程的。过呃,流程的一个体现明白。好,同学们,那关于我们这一个就是所谓的快速排序法的一个思路,它的大体的一个思路和图解,我就给大家讲到这儿,一会儿呢,我们就代码来实现刚才所说的这个快速排序法。OK,好,那快速排序版呢,我们下一个视频为大家实现。
我来说两句