00:00
同学们,我们来把刚才的这个快排用代码实现一把,来,我们先写一个类,这个类呢,我的名字就叫quick so。Quick就是快速排序,把主方法勾上。那勾上以后呢,还是我们的老规矩,先把这个数组搞定,先做一个数组对不对,那这个数组呢,我们就用刚才我们分析的这个数组来讲解好吧,这样大家就能看到这个流程嘛,就领会的更加清晰一些。好的,我把这个呢放在这里来。没有问题吧,没问题,好,现在呢,我们开始写这个快速排序法。好,Public static void void quick so,那你干什么呢?你把这个数组传给我,我帮你排序对吧,OK。那么我们这段代码应该怎么做呢?首先同学们看,我们首先呢,先把左边的这个索引拿到。
01:01
哦,对了,我们光有这个数组还是不行的,我们还需要什么呢?你给我指定最左边的索引是什么,然后告诉我最右边的索引是什么啊,这是基本功好上来过后呢,我先把这个左右两边用一个变量记录下来。OK,这是左索引。做。所以。或者左下标也可以啊,左边的下标。这边是我们的右边的下标,右下标。诶,下标没毛病吧,那你有左右过后,根据刚才老师讲的,是不是我们首先要找到中间这个值啊,是不是零了,那中间这个值咱们怎么整呢?各位同学,我们找到中间这个值叫P。Ward。这个P的这个单词是中轴的意思,大家可以看一下这个英文单词啊,中轴的意思,P word是中轴。
02:00
自偶走啊,中轴。中轴。OK,相当于是我说的中间这个值,那怎么拉到中间这个值呢?Very的easy是不是让左边。Left。加上我们的右边。是不是,然后再怎么样,除以二。这个是不是就是我们中间这个值,也就是说P是中轴值。说的再具体点,就是我们第一次进来的话就是零。那拿这个直播干什么呢?各位朋友,我们就开始要while循环了。Y循环,Y号循环退出的条件是,如果我们这个左边的索引还小于右边索引,我就可以一直进行这个这个就是我们所说的这个这个递归的处理,因为你这个数可能很多嘛,对不对,那什么时候开始结束,就是你左边的这个还跟只要,呃,这个右边这个呢,索引开大于它,我就可以继续做这个事情,是这意思吧,好,这个呢,是只要。
03:02
我我这写个注释啊,干什么呢?While循环的目的。哇,循环的这个这边的这个代表这个目的是干什么呢,是让。是让我们这一个pivo。小的是让这样写啊,是让比。比什么呢啊,比这个PT值小的。指小的。放到。放到哪里呢?诶放到它的左边。试一试吧,然后呢,比什么呢?诶比这个PT大的值呢,放在右边,那也就是说我现在用的是从小到从小到大排序。对不对,大的放到它的右边,就是做这个事情,一直做一直做。好,只要这个条件满足,我就一直做,那做的时候呢,我们看看你怎么来体现这个特点呢,我们用一个while循环。
04:06
是不是外循环呢,那外循环怎么做呢?如果大家看这里啊。小于P。这句话什么意思?大家能看出来吗?这句话其实就是在PT的左边一直找,直到找到一个。比pivot。大的或者是大于等于PT的一个字才退出,大家看懂了没有,这这个Y循环的目的是干什么呢?在pivot。的左边。左边一直找。哎,一直找。找什么呢?到找到找到什么呢?诶找到找到一个大于或者等于这个PT的字。才退出。哎,他就说那么怎么找呢,你看如果。
05:03
2L小于它,我就这样做,就让L加一个一。大家看懂了没有?也就是说相当于我从这个PT这个中轴的左边去找,一直找,找到一个,呃,就是大于它的值,不然我就不退出。不然我就不退出。那这边完了过后呢,我们再写一个,你还得从右边找一个是不是,所以说我从这边写个R干什么呢?大于P。这句话的意思又是什么呢?反过来的。反过来的的这句话的意思呢,同学们可以看到是在PT的右边。哎,右边。我们干什么?一直找,找到一个小于。小于等于P才去数,那同样既然是这样的话,那这个R应该是减了。是不是因为你那你你这个R是从这个传进来,肯定是最右边嘛,所以说我在剪的过程中去找他。
06:03
立减,好,那就是这样子,也就是说,呃,如果我们看这个图的话,相当于说这个绿色的线最先在这,这个黄色线最先在这边,然后我从这边开始找找找找一个比零大的,从这边开始找找找找一个比比零小的,明明白意思吧,所以说有个图解比较好理解了。那么找到以后我我要干什么事情呢?对不对,我要干什么事情呢?我要干一件这样的事情。干怎样一件事情呢,就是说。呃,我就要干这样一件事了,干什么了,我就开始交换,是不是我交换了,那就交换,如果说大家看,如果说这个L大于等于R说明什么问题,就是当我。当我,呃,这个退出过后。因为你大不了最多是找到这个P嘛,你看这个地方它肯定是会退出的,所以这么千万不要写等号,因为你从A开始找,你不无论如何你不停找,最终你你一定会找到一个P,比这个在P在P的这个。
07:08
左边一定要一定会找到一个,呃,大于等于它的,因为你最坏的情况下,是不是就找到它本身呢。是不是这个情况啊,明白,好,如果是这样一个情况的话呢,那么我们就干什么事情呢?好,同学们,我们就break了。因为这就说明我们找到了吗?是不是这个道理,如果我们这样找,诶大家看,当我们这个条件成立的时候,比如说如果我们这个L大于等于二成立,说明什么呢?说明pit。的左右,哎,左右两边。的值。值他已经已经按照按照按照什么呢?按照左边全部是。左边全部是什么呢?全部是小于。
08:03
啊,小于说已经是左边全部是小于等于,因为你不停的这个串嘛,是不是小于等于PT的。PT的这个值了,而右边右边全部是什么呀?是大于等于PT的值。P啊,这个单词别写错了啊,P的值大家能理解吧,因为你不停的找,你最终最终的情况下就有可能是L大于零,它当这个条件满足的话,说明说明我就OK,因为你在转的过程中,假设我们这找到一个交换了,交换完了没有停呢,你还会继续往这边找啊。只是我这数量比较小,刚好这就停止了,假设我们这边您这边有三个数,是不是你绿色的和这个黄色交换过后还没有结束,你还得绿色还继续往这边移动,而这个黄色的还得往前移动,再找再交换,是这意思吧?是不是找下一组了?
09:01
那如果这个条件成立的话,说明左右里面都已经满足条件,满足这个条件的话,我就退出。对不对,那如果说。如果说这个条件还没有满足,是不是我们就应该交换?是不是应该交换,交换的时候也非常简单,我们写一个临时的变量进行交换,来把这个在临时变量我们写到这里看。等于零,这个是一个什么呢?临时变量。OK,这个临时变量用来干什么呢?作为这个交换式使用。哎,交换。交换时使用。明白,那我怎么来交换呢?交换我就不用讲了吧,大家在在前面我们已经学过很多很多遍,很多很多这个关于交换的时候的一些。小的这个这个方法和技巧。对吧,方法和技巧,那现在我们有了这样一个东西过后呢,我们来看一下交换的代码,应该是象写的R。
10:02
I。AI写到这里来,R,然后呢,这边怎么着RL。呃呃,这个不不是不是那个IR4,这个是LL,那么这边是谁呢?是这个R给他。试一试吧。给他完了后呢,我们继续写了RR应该等于什么呢?Temp。是不是这个动作就是老师写的这几句话,是不是就相当于假如我们找到一个78,这边找到一个负的,呃,567,是不是这两者。通过一个中间变量把焦,也就说把这个负的567放到了这个位置,把78放到这个位置,是不是相当于这个动作?明白。是不是这意思啊?那交换完了过呢,交换完了过后我们继续往下处理。OK,那这边我们要做一个判断,如果交换完后。完后。干什么呢,发现发现这个P。
11:04
Pit。呃,发现这个值,发现这个值啊,这个左边这个值,发现哪个值呢。这个L。等于了这个P值。那么我们就要往前再走一步,因为你可能下一步还是这个值啊,可能是相同的值,是不是有种这种可能性啊,值相等。那么这个时候呢,我们就让这个R。减减相当于说前移一步对吧,向前移一步。前移。迁移一下,那这个代码我就写到这了,大家可以看到是一。谁呢?L,如果L这个L它等于P。那么这个时候呢,我们需要让这个R,让这个R减一或者叫减减都可以啊,这样我就减一啊比较简单。因为相等的话,我我没有必要再次比较这个右边的嘛,我直接我们移动一下。
12:05
那同样的道理。同样的道理,你如果交换完后,我们看啊,我把这个复制化复制下来。复制下来。对,复制下来,如果说我们发现交换完后发现这个R。R。它和PT相等,那么我们应该怎么样呢?好,这个时候我们应该让L,让这个L往后面移下,相当于L加加,前面是R减减。这个是后移。为什么要后移啊,因为你没有必要再进行下次的这个处理,因为你不你不然的话他就老在这就形成一个死循环了,是不是,那就if r什么呢,它的R。如果等于P。在这个条件情况下呢,我们就让这个L加一。Al加一往后移。
13:02
好,当这个条件做完了以后呢,同学们,我们这个while循环这件事情就搞定了。什么意思啊,就是说当我这个外循环过后,我已然完成了第一次的这个分割。什么意思?就是把P味我们现在选的第一个part把它分成了两个部分,那有些同学是不是这样子呢?来我们打一下,我们先不写那么多啊,来各位同学,当我们完成这个动作,我们看看是不是按照我们这个思路,已经把把这个零的左边是全部小于零的,把0比0大的全部呃放到它的右边了,玩一把呗,试一试呗,来,走一个quick。Short,那么我们首先把R放进去,这边肯定是零了,R是什么呢?Right是不是要减一啊,各位朋友?这个简易不要不要忘了啊,简易不要忘了。好的,那现在呢,我们把这个书出来玩一把呗,看看是不是跟我们想的当年等于加上。
14:04
R,第二,To是string,把谁放进去?把R放进去我们运行之。我们允许吧。各位朋友请看。诶,同学们看零。零是不是,那这个0比0小的是不是都在这边呢。比邻大的是不是在这边跟我们画的这个图是否。一样啊,完全的一样。完全一样的,当然有的人说老师,那那如果说这边多几个呢,一样的道理。有道理,好,这个就完成第一件事情了,那你完成这个事你不算完了,你是不是还有向左递归,向右递归,你没处理啊同学们。也不是说我我把这个把比例小的放在左边,把比例大的放右边,这事就完了,因为你不敢保证。比例小的,它是一个有序的呀,就这两个数是有序的,你不敢保证呢,同样右边你是不是也不敢保证呢。因此你还要继续执行这两条递归的处理,那代码也非常的简单,各位朋友,那打开这里,我们来写一写。
15:07
好,我们在递归之前要有一个判断,判断,如果说如果说这个L等于R这个地方,注意啊,必须。必须让这个LL加加,让这个R减减,为什么呢?否则否则会出现出现这个站异出。那为什么要这样呢?因为你如果L和R相等,你不把它错开,你不把它错开,它就一直在这个这地方去做这个事情,因为你上面这个条件它是满足的,他退不出来。所以这个条件呢,一定要加上啊,各位同学,If,如果我们这个L等于R,在这种情况下呢,我们需要让这个L加等什么呢?一同样我们让这个R减等于。没毛病吧,好,这地方大家应该可以理解,你们待会可以试一下。如果你没有这两句话,后果很严重,那下面呢,诶就可以正式的向左递归。
16:06
向左递归来,我们把向左递归代码写一下,比如说left。如果我们left小于R,我们就继续想左递归,因为你你向左递归有个推出条件啊,你想你不停的左递归,左递归最终是不是就会出现一个什么情况,就是你的这个left它大于等于二了。只有小于等于二,我们才左低柜左低位代码也很简单,Quick。怎么写呢?这个left我们应该填什么,同学们,这个。向左递归,我们填的是R和A,这一向左递归显的是left了。Nap。是不是left而一向左递归右边这个是不是按照这个R来走的呀。按照这个R来做的,因为因为你在处理的时候,你肯定这个就发生变化了,你把这个传进去,这个R会变化嘛,对不对,上面处理完完了过后,就是你上面这个Y循环完了,上面这个Y循环完了过后,这个R是不是已经变化了,所以说要走到这里来。
17:04
OK,好,我们可以试一下向左递归,完了过后,它应该的结果是什么呢?应该是这样子,就是左边这零,左边这边已经变成有序的了,就是负567负九,然后这边是零,右边呢,人们没有处理好,我们来玩一把。那同学们请看代码执行。它应该变成什么呢?它应该变成看零零左边的已经也是有序的了。右边没有洞。右边是不是跟刚才一模一样啊,还是23 78,七七十是不是没动,因为你没有向右递归,也就说你刚才这句话的处理,只是把零左边的变成了一个有序的,但是零右边的没动,因此它仍然是刚才的那个23780,也就是仍然保存的是这个。这这这个这个顺序能理解这意思吧,那现在你是不是应该向右递归玩一把就可以了,那向右递归怎么办呢?也很简单,向右。
18:01
向右递归,向右递归我们有一也有一个条件,你要防止它是一个死地归,对吧,应该是我们的right。你右边要大于L的情况我们才能去做,你不在说右边都已经小于它了,那你还玩啥呀,那不死死在里面了,那相对地位来玩一把相地位,我们把这个同样写进去,这边应该填什么呢?这边我们就应该填啊,我们。啊,我们填L左边嘛,来右边还是填这个r right就可以了,来各位同学我们运行一下这边两边都OK了,运行。好,同学们,可以看到现在代码呢,完全的没有问题是不是。负五九到二三七十七十八。完全OK,那我们现在我们可以多整几个数据来看看到底是否OK。同学们看。好我我整一下啊,现在这边呢,我们多多来几个数吧,负一,然后呢900,然后呢4561玩一把。
19:04
现在有小。有小的有大的,好好我们运行车。我们看一下此时此刻这个结果我们想的一样吗?你看它是一样的,是不是仍然是个有序的呀,看负负九负10239对不对,没有毛病。没有毛病,说明我们这个代码呢是没有任何问题的,就是快速排序法的一个实现。快速排序版的一个事情就说到这里,那待会儿呢,我们可以来测试一下这个快速排序吧的效率,到底真的有没有像传说中的那么快呢?我们下课下个视频为大家讲解,先理解一下啊,我希望同学们自己能够写出这段代码。并不难,并不难,尤其是要把老师这个分析把它搞定。好,这个我们先说到这。
我来说两句