00:00
好,因为这段代码呢,它没有办法就是一步一步的来类推了,咱们直接就看这个代码。啊,大家看一下这个代码,这个代码呢,也非常简单,我们把它拿过来啊分析一把。那么我在这呢?写一个文件叫quick sort。要quick so。快速排序,来一个object。好的,然后呢,这边我们写一个。哦,主方法。好主方法,然后我在这里面把这个方法拿过来,我们看一下它是怎么实现的啊。我在这里先把。先把我们需要的一个包引入一下ul包,点CTRl.breaks。点下划线。好,我们来看看他的思路跟我刚才说的是不是一样的,来,我给大家分析一下。首先第一个我们可以看到这边left。
01:01
这个life的代表,待会你在传输的是代表从左边的第几个元素开始进行快排,那对应这个图大家应该可以看到,待会应该是从这个,如果我们分析出来就应该是从这开始走,这边一个是左,一边是右。啊,所以说待会儿呢,这个left就是指定。从数组数组。数组的左边,左边的这个下标,左边的下标当然,呃,一般就是零。对的,第二个,呃,Right呢,一样的道理了,Right呢,就是指定我们数组最右边的下标,当然这个就应该是我们的长度怎么样减一对不对数组的右边。右边的这么一个下标,那一般来说是N减一。N减一没问题,第三个参数,第三个参数大家猜也猜的出来,这个就是我们的数组。
02:00
就是你要进行排序的数组啊,进行排序的数组。排序的数组没问题,好,那下面呢,我们就来看它是具体怎么操作的,首先同学们看一下这个left和这个right,这边就是我把传进去的这个left传给L和R,这个大家也猜出这就是左边的下标,这就是右边的下标啊,这个很好,很好理解左下标。左下标和右下标。右边的下标。好,下边。那么这个地方跟我刚才这这个是右边的下标啊右边。这个现在这段我写的代码呢,跟我刚才不一样,我原先写的是以这个最后这个数为基准来进行,呃左右分割,那现在呢,我找的是中间这个值,大家看这里。这个这个people,这个就是我的一个这个。
03:00
呃,这个中间这个基准基准,那么我走的是中间这个是为什么呢?看这里。就是left加right除以二,这显示中间这个下标,那中间这个下标我把这个值拿到了,就以什么呢?相当于说以中间中间这个值为这个基准。啊,以以以为这个基准进行进行这个分割。分割,那我怎么分割的呢?好,同学们看这篇代码。同学们看这里,嗯,这段代码呢,我稍微整理一下。啊,这个break,这个break语句从这里到这结束,其实这边套了一个while语句,那这个while语句做了一个什么事情,大家看这里啊,同学们。这段代码只要这个R是大于这个L,我做一件什么事情,大家看到是不是能能看到这段代码是在做什么事吗。这段代码是不是从我这这从我这个左边的这个数组找到一个小于这个PI的一个值。
04:06
是一个下标,也就说也也就什么意思呢,就是从我这边。从这从就是假设中间这个值啊,我从左边找一个比它小,比它这个,呃,就比如说我以中间为五,找一个比它大的,从这边找一个比他小的,大家看这里,这边就是从。从什么呢?从左边左边找到一个找一个啊。找比个比比谁呀,比这一个power,只要你看我只要我这个只要小于你,我就不停找,那什么时候才会退出来,就是我大于零才会退出来是吧,就是从左边找一个比这一个PI大的数。大的。大的值对应的对应的下标。很好理解,那同样道理,这边一样可以这样理解了,这个是从右边。
05:06
从右边。从右边找一个比这个part小的纸。对应的下标。那为什么要这样做呢?因为我想交换。就是我从我相当于说我从这个嗯,这个PI的左左边找一个比它大的,从这边从页面找一个比他小的,这样我就交换它啊交这其实这这个Y整个这个Y语句的作用是干什么呢?整个这个Y的语句的作用就是要进行一个交换。啊,我把这个地方写一下啊,这个地方while语句的作用,这个while语句的作用,作用就是就是将将什么呢?将这个比就是就是把比这个piratet对吧?Pivot啊把这个pit小的数。数放到左边,OK,然后比啊比这个bib的大的数。
06:08
大的数放到哪里啊,放到右面,那那他怎么怎么来做的呢,他不能说没有规章制度嘛,他就是怎么说呢,他他从这个左边找一个大的,从这边找一个小的,然后交换。就这样干。那这样肯定就快了。对吧,那找的时候这两这两条这个外语就始终找一个,找到了一个过后我们判断一下。判断什么呢?如果这个L大于R了,说明什么意思?说明被这一次。这一次的这个整个这个嗯,这个交换就结束了。啊,注意一下,我说的是这一次的递归,因为它这个递归不是递归完了过后,下面还要分割过后再进行递归吗。对,只有如果这个条件满足,说明。说明本次。本次的这个交换结束。
07:01
结束。啊,就说呃,比打个打个比方吧,就说比如说我们找到中间这个值,这个中间值我们我我们把我们写一个,写一个数组啊,我就随便写一个啊,我把这个数字先写到这。V。There。R,我写一个数字在这R,然后呢,我随便放一些没有,比如放放一个一负一。好,然后呢,九下面放一个大一点的,比较大一点的,不然的话这个暴弄十,比如说我写一个相对容易好看的啊,比较小一点的一。复议。OK,你呃可以这样理解,就是说我以这个九为中间这个值,呃,然后这个left,这个L呢,就从这边开始扫。找到一个比,呃,找到一个比它大的,找到了就停到这儿,从右边这个找一个比他小一个,找到了好,又说找到11和这个负一值干什么呢?交换。交换过这个L,就是你们可以看到这边有个L,这个这个L呢,它就不停的往这边走,而这边有个L,这个L呢,不停往这边走,OK,那最终走走走走走,最终最最终到什么情况下,他们就相当于交换完毕了,就是如果在整个这个递归过程中,如果发现L大于等于R了,那就不要再走了,因为你。
08:19
就彻底的把这一次本次这个交换怎么样做完了。就这意思啊,就这意思,那么你看呃,如果呃没有满足条件继续往下走,那就交换啊,这个这个条件满足就交换结束就退出了。就就就退出这个要对象啊,就退出退出我们这个本次啊,本次这个本次交换本次外语。本次好,那那当然你如果没有的话,你是不是上面已经找到,找到你还要交换了,这个就是交换,就是刚才我说的什么意思呢?比如说找到11和这个负一就交换。啊,交换就这意思啊,交换注意交换。
09:01
这个就是发生交换。啊,交换,那交换下面这两句话有点不好理解,这下面句话其实你要说,呃,没有也无所谓,但是有了可以提高效率,大家看这段这两句话的作用是什么呢?这句话和这句话的用处是什么呢?大家能看出来吗?这句话的意思就是说,如果我错完这个交换过后,我发现这个L等于pit,这个R等于pit,那说明什么呀?说明交换完B过后,刚好有一个在左边有一个跟跟这个PI相等,那相等你就不要再去比较了,就直接把这个R再往这边走一下。运它可以不用交换啊,就说这样子处理后,处理后如果发现,如果发现这个呃RVR。就是处理后,你你不是这边处理完了过后这个R不再走吗?如果发现这个L等于它。
10:00
A等于什么等于这个pit?那我们就可以不再进行这个比较,然后就干什么呢?就把这个R减去一个一。啊,这个是为了提高效率。提高效率,如果没有的话呢,这个也无所谓,就是呃,效率会多比一次而已,下面也是一样的道理。啊,整个这个整个这个Y2循环的作用,再说一遍啊,整个这个Y2循环的作用就是干这件事情,那这就是他的一个最核心的代码。这就是他最核心的代码做完以后,下面呢,这句话先不用看,这句话为也是为了提高效率的。提高效率。下面这句话,我相信同学们能能够容易看懂,下面这句话就是向左递归。因为你因为你把上面那个五,比如说你把这个这个九九整完了以后,这边这个边,那那那你第一次做完过后,它变成一个什么数组了呢?变成这样的啊负一。
11:01
负一一。然后是九,然后是这边应该是几呢,十和11,你这样做完了以后,你不敢保证,就当然我这刚好运气好啊,就是你不敢保证,你这这边左边的这边呃,仍然是个有序的,你不敢保证,因此你你还向左边递归进行这个处理,或者递进向左边递归进行这个分割啊,所以说那什么意思呢,这边代码就是相当于向左。向左。进行这个递归。进行这个递归处理,向左递归啊处理递归排序。当然这边就是向右,向右递归排序。递归排序。好,那这句话的作用是干什么呢?说呃这句话意思就是说,如果我们刚好呃处理完了过后是由于呃,由于是呃,刚好你是L等于R出来的。
12:07
就是说因为你推出这个Y循环语句是L大于,呃等等于这个R出来的,如果是L等于R,那其实刚好相等那个点自己跟自己比没有意义,就你刚好刚好找到一个点了,那一个数跟自己比没有义,所以说就在这个情况下呢,就错一位。就错一位,你错一位就是将将这个L呢,再往这边左边呃,向向右边走一下,R呢往右边呃往往那个左边跑一下,这个就是为了为了少一次这个比较,因为你两个相等,你没有一比嘛,啊这个就是提高效率的一个处理方案,好同学们这个代码就说完了,就是把前面的一个套路说完了,你看传处理完了过后,这个L,这个R会继续传进去。这个为什么体现出向左呢?Left r这边是l right。好,那这段代码输完了过后我们来测一下,看看它能不能跑的正确啊,我们来跑一跑quick。
13:08
Quick shot,我传一个零。我说了,我从最左边的下边从零开始跑,右边呢是点认识,注意要减掉一个一,然后把数组放进去。放进去过后,我们打印出这个排序后的。排序后的代码。排序后的,那我们执行一下。就是偶点make。String。我们跑一跑运行。跑起来。跑起来。好的,如果这样一跑起来过后,我们看代码是一个什么情况啊同学们。诶,大家看。跟我们想的是一样的。一样的,好,我们来把这个代码稍微修改一下,看看同学们能不能够理解。我这里刚好有一个测试案例。
14:04
我用这个速度来测试。我用这个测试速度来测试,我请同学们思考,待会我修改代码会怎么样啊。首先。我。把这个代码先跑跑一遍,看看结果是否正确。看肯定是正确的,没有任何问题,同学们看是这样的一个结构啊,好,现在我对它做一个稍微的修改,看看同学们能能不能看到它有哪些变化,比如说。我把这个向左递归去掉了。我如果去掉了同学们。呃,假如啊,我把这两个都去掉了。假如我把这两个都去掉了,请问请问。我。整个这个执行完了过后,这边这个数组会输出什么。是不是他相当于只做了一次?
15:01
分割呀。那这个时候还记不记得我们刚才是以找哪个中间值来进行这个分割的?是几?是零还是23呢?应该是零,因为你的下标零加上这边这个下标是几啊五,所以说你当时我们是零加五除以二,呃,但是它因为返回一个整数,所以说2.5就取到二了,所以它中间值应该是零。所以说如果这样子,我把左右两边去掉的话,它整个打印的应该是什么样的呢?情况呢,应该是这样子的零。零这个这边零,零以这边零为基时,你会看到,你会看到零左边全是小的,零右边全是大的,大于零的,但是呢,它并不是有序的,大家看。好,我们来执行一下,看这个结果是这样子,你看零确实如此,看零,然后比零小的扔到这边来了,比零大的扔到这边了,但是这个病。
16:02
不是一个有序的。这边也不是一个有序的,看到没有,好同学们,我再改一下代码,你们看看会出现一个什么情况,我呢,把这个向左递归打开。向左递轨打开,请问嗯,如果我向左递柜继续继续跑的话,是不是,呃,相当于他把这边还是进行了一个二分排序啊啊就是快速排序,那也就是说这边就变成了就是负的,呃567,那如果这样打开的话,这个结果应该是这样子的同学们。那就应该是。左边。呃,负呃,零的左边全部都是有序的,但右边仍然是纹丝不动,我们来证明这个。代码啊,就是这个代码其实也不难。你看我跑起来,你看的确跟我想的一样,你看右边,因为你没有向右边进行递归嘛,所以说右边就整了一次过后人家就不动了。
17:02
啊,同样道理,如果我现在把右边也打开好,大家看到右边仍然是变成有序的,所以其实这两句话呢,特别的重要,要是没有的话会出问题啊,我执行一下。再给同学们跑一把。你看这个代码,诶,这就是左右两边都有序了。都有学,其实在你放右右边递归的时候,它只是在这边的这个速度进行。进行这个快排,好,我们看看它的速度怎么样。它的速度怎么样啊,呃,它的速度怎么样,那么我们来一起来测一下这个代码的速度,如何打开我们这个前面讲的insert。快呃,插入排序,我把测试数据拿过来用一下。来,这是我们生成了一个八万八万大小的随机数组。我找到quick shot了,同学们。我先把这个注销啊,各位同学。
18:00
我们把这儿放一下。OK。那放进去过后呢?呃,前面排序时间咱们就已经啊拿到了。这边我们调用了快排。这边我们调用快速排序。快拍。OK。那排序过后我显然不能输出了,因为呃,这个量太大了,这个有8万个数据,你输出时间都比排序时间大很多,那排序过后的时间呢,我们也把它打出来看一下各位,那排序过后的时间是这么一点时间。各位同学,来,我们把它放这儿。好,同学们看啊呃,排序前的时间是这个,排序后的时间是这个,我们执行一下,呃,调用了quick shot肯定是有序的走一个。8万个数据多少时间完成了呢?好,同学们可以看到,对,零秒当然应该是毫秒级了,那我现在把这个数据整大一点啊,你看冒泡它可是用的多少时间呢?用了13秒,我们再把这个数据扩大到80万。
19:10
这个80万已经很大了,80万个数据,80万个数据我们再跑一下,各位同学请看执行的时间大概是多长。OK,零秒,OK,那说老师你再狠一点,你甚至有些同学,老师你排了没有是吧,肯定是排了的。那没有排,不知道这这个函,这函数确实掉了吗。那肯定是跑了的啊,这个你不用担心,它快速排序就这么快,那么我们整一个800万的数据,那800万已经很大了,这个呢,不可能是零零秒了啊,他应该大概会花两秒到三秒,那也很快了,来跑一个。我们看这个时候他花了多少时间呢?OK,好,我们可以看到他花了两秒搞定800万个数据,那8000万我们就不测了啊,8000万可能我设一下看。
20:00
8000万,那肯定是要点时间了,8000万呢啊。大概要多长时间呢?其实大家也知道它,因为它是不停分割,我们看这个变化会不会很大啊各位同学8000万数据。8000万主要是这个。好,我们看一下。8000万的数据。这个速度就明显就提不起来是吧,8000万。是不是不动了?哎,画了几秒钟啊。五秒,诶15秒,8000万数据花了15秒,待会呢,我们可以把这个速度跟那个规定再进行一个比较啊,就是看看哪个效率更高,那么8000万呢,他花了15秒,如果这个8000万交给冒泡牌,你基本上可以吃一顿饭了啊,吃完饭可能他还在排。这也也算可以8000万,好同学们,那关于这个快排呢,我们就先聊到这里,我们把这个笔记给他补一补,我们接着讲下一个啊,OK。
21:04
我们把快速排序给大家板述一下。好的,打开我们笔记,我们把快排给大家整理一下。OK。好,往下拉一拉。诶,这代码啊,好在这儿。那么我们来看下快速排序。OK,那快速排序,首先我对他做了一个基本介绍。对吧?我们对快速排序做了一个基本介绍,它的基本思想有一个示意图可以看得更清晰一点。这是快速排序的一个示意图。也放到这里了,他是怎么来排的呢?它的核心思想就是不停的去进行这个分割递归,进行这个左右分割。好,这是它的一个示意图,只是我这个图呢,有点呃有点不太好,就是我是以最后这个为这个基准分割的,大家把它调成呃,把它当作是以中间为分割一样的看啊好,下面呢就是代码实现。
22:11
啊,这个很简单,代码实现,代码实现呢,我给大家阐述到这里。好。把它放到我们的这个笔记中,这是快速排序的实现,截取一段。
我来说两句