00:00
下面呢,我们对这一个冒泡排序进行一个适当的优化,什么意思呢,就是说。如果我们发现在某趟排序中没有发生过一次交换。则可以提前结束冒泡排序。就是说呃,相当于说这个时候已经是一个有序的了,比如说针对我们刚才讲的第一个案例是不上,实际上他在这个地方已经有序了,对吧,那么这个怎么来优化呢?看代码我们可以这样来玩。我们可以这样来玩,比如说我在这里呢,定义一个变量。啊,我们做一个标识符布。对不对,那我写个flag。默认给他一个force。默认给了一个,这是个标识符。标识标识啊,标识变量。标识变量,那么它标识什么呢?就是表示,表示是否是否进行过交换。
01:03
能理解,默认为false,那么我们怎么做呢?如果它在这个for循环中,这个for循环是不是相当于我们一趟排序?相当于什么呀,现在老师高亮的部分是不是相当于。第一次进来是第一趟排序,第二次是第二趟,第三次是第三次,第四次是第四次的排序是吧?那如果说我们发现他进来过,那么我就把这个flag。这是在我们做小的算法里面一个常用的技技巧,同学们注意一下,我就认为是错。OK,那么如果一旦我们发现是处,那么整这个在一次大的循环里边做完了以后,我们先干什么呢?我们来做一个判断。我们来做一个判断,怎么判断呢?如果我们发现flag,它等于false,说明什么问题?
02:00
说明什么问题说明什么呀?一次都没有交换过,说在一趟排序中。一次交换,一次交换都没有发生过。对不对,那所以说这个地方呢,其实我们可以写成这样子,一个格式,如果一次都没有发生,是不是就可以break了。是这个意思吧,就是一次都没有发生,因为你进来原先是force嘛,进来你没有进到柜子里面去,那就是force,但是有一个细节大家有没有注意到,如果说。他进来有一次就是在一次一趟排序中它交换过,那是不是下一次你还得把这个flag重新置为一个force才有效啊,对不对,所以说这地方还有一个动作不要忘了啊,这有个很重要的动作,要把这个flag。Flag干什么呢?等于这个force重置,我写下这个原因啊,这里重置这个flag,让让进行进行下一下次的。
03:06
下次。来进行下次判断。大家能理解为什么老师这样写的吗?因为你想嘛,假设,假如说这个人,这个他进行过一次交换,就是他他一共有四趟交换,其实第一次他交换过了,交换变成处了是吧。变变成出了过后,那你第二,那你进行第二次第二轮的时候,你是不是先把它制成force,然后再来判断第二次第二场的排序里面到底有没有发生过,所以说你这一定要把它重置一下啊,不重置这个就无效了。明白好这个呢,我们再来执行一下,你看这个效果就不一样了,你看啊走一个你看。第一趟,第二趟,第三趟,第四趟。是吧,进行了市场完成,但是如果我把这个数据改改一下,比如说我们还改成20。改成20,如果改成20的话,你们有没有发现他第三趟第四趟是不会进行的。
04:05
第三趟和第四趟不会进行,为什么?根据我们刚才分析的,如果是20的话,是不是它在它其实有两次不需要再执行,你看我在运行。你看实际上哦,你看走了第一趟,第二趟第三趟走了一下,第四趟就没有走了。为什么第四趟那个时候他已经不会在,也也就是说在进行完第三趟排序过后呢,他发现一次都没交换就退出,为什么第二趟有呢?因为大大家记记住你第二趟来的时候,是不是第二趟,第第二趟里面的第一次实际上是三和负一,是不是这个还是交换过一次的,因为你第一趟完了,最后这一次这个是这个数组,就是现在老师标量的这个数组,是第二趟排序里面的第一次比较,所以所以所以说这个地方实际上是交换过的。
05:02
对不对,那交换过后,第二趟交换过,所以说他仍然要进行第三趟,只是第三趟呢,它没有发生过任何交换,第三趟完了过后就退出来了。你你如果不相信,你可以这样玩一把,说老师我不相信,你可以上来过后就整一个就是有序的,你看啊我我做一个特别极端的案例。六。假设我这个叔叔上来就是个有序的,请问他。第一次。都没有发生交换,所以说他只一趟排序就完事了。因为他发现第一趟一趟排序里面一次交换都没有,所以第二趟排序都没有,你看我给他跑一下。是不是他上来给我第一趟排序就就完事了,明明白吧,那如果说你你把这个数据颠倒过后,它又不一样了。明白这意思,好,同学们,那我这个就说说到这里了啊,相信同学们应该也能理解这个含义,那大家看,当我把这个做完了以后呢,我们这样子玩一把。
06:04
因为你这呢是分分散写的,这样很不好,所以说我们把这一段冒泡排序呢,封装成一个函数,封装成一个方法,好吧,我们把它封装成一个方法,来将前面的前面的这个冒泡冒泡排序算法封装成一个方法,这样更方便,好public我就开始写啊,Public static void。当然直接写着bbb。B b Le bubble对吧?B b Le bubble shop。那么我需要你给我传一个数组过来就可以了,是这意思吧,同学们,那么你给我传一个数组,我就帮你进行排序,那整个代码是不是这样就可以了。是不是我把这段代码直接剪切到这里?
07:02
是吧,然后呢,我把这一段代码进行一个格式化。就完事了,那么我们要去用的时候,要去排序的时候,是不是这样做就可以了,同学们大家看我在这调一下。好,我这测试测试这个冒泡冒,诶写啊冒泡排序。那么怎么测试呢?刚才我们写的这个方法拿过来把这个传进去,传进去过后我这里面可能就不再输出了,这样输出也没什么意义,这几句话呢,我就把它注销了。没有问题吧,那你把这个数组传进去,数组是引用类型,因此呢,在这我们可以输出排序后的。这个数组这样写啊,排序后。排序后呢,我们把它打出来。简单吧,就是阿瑞。a.TWO10G,然后呢,我把这个输出。
08:03
那么在排序前呢,我们也输出一下进行一个比较好吧,这是排序前。一个是排序后,一个是排序前,那么我们运行一把,我们可以看到排序前是原始数组,排序后有序的。有序的好,那么刚才我们讲过这个冒泡排序啊,它的时间复杂度呢,是这样一个时间复杂数N的平方。就是平方阶。是一个是一个平平方的平方阶段,那我们想来做一个这样测试,现在这个数据量太小了,因为后面呢,我们还要写很多的这个排序算法,我们可以来测试一下,假如我们现在这个数组一共有多少个呢?假如这个数组现在有啊8万个数据,我们看看冒泡排序会花花费我们多长时间。
09:02
OK,好,这样子啊,我们来测试一下冒泡排序的测试测试一下冒泡。冒泡排序的速度,那么我这里用的是事前,我是事前我们实际上是可以算出它的辅,它的这个它的这个空空,呃时间辅杂数是这样指的是O。O。然后呢,N的平方。N的平方,现在我们再来做一个事后复杂度,我们实际的运行一下,现在呢,我们给给给8万个数据。8万个这个数据,就是8万个的这个数据。测试一下,那现在呢,我们先在模拟先来创建一个,创建一个啊,8万个的随机8万个。
10:00
的随机。这样写啊,随机的随机的一个数组,那现在我开始来创建,首先呢,我先把上面这个先注销。好,上面我们就先注销了,好吧,我们因为我要做测试了,那首先呢,我们先创建一个这样的数组叫in。In等于六一个INT8万。个十百千万,我们看看拍8万个数据,他要花多少多少时间,那现在呢,产生一个随机数。好,我们现在这样写啊,For循环。For循环int I等于零,I小于8万。这个很快啊,I加加,I加加完了过后呢,我们这样写I,等于我们这样写用me。点产生一个random。再乘以一个。
11:00
这样的一个数据。那么整个这个结果呢,我们把它转成一个int。转成一个整数。OK,转成一个整数,后面这个也把它包起来。大家有没有发现我这样写,这样写呢,它会产生一个怎样的随数呢?会生成生成一个这个范围的随机数,零到这么大的。这么大的一个。数对吧。就是因为我这个random是产生的是零到一之间的一个小数嘛,再乘以后面这个值,这个值为什么写这么大呢?因为我希望它能够闪开。这样呢,就有效的看到它是一个随机数了,好,这个数做完了以后,我们先看看这个数组,它是不是一一个随机的啊,我们输出一把。我们输出一把这个数组。
12:00
那现在速度太大了,太多,我这个不好测试,我先我先把它改小一点。改小一点,大家看一下运行。好,同学们看,嗯,目前的确是有效的,看这是个随机的排完的功能,仍然是一个有序的,对不对,现在我们把这个整大一点8万。那么我写上这个8万以后,现在呢,我们就不能再测了,因为这个打印出来时间太长了,所以说我就直接输出时间。我们写一段代码来测试排序前的时间。那么怎么写呢?好,六一个六,六一个date。好六个date。现在date。假设这是第一个时间。我们把。把这个时间引进去。好,这边呢,我们引入这个包,诶这个包看看date。啊,这不是不是这这里面的这个date啊,刚才应该是引错了重新来。
13:00
他应该。那我们我们看一下这个地方。应该怎么引号?Date date里面呢,我们把六一个data啊,这个写错了data。第好,不是他。重新来一下。再来。对,是这个utr里面的date,那拿到这个东西东西以后过后呢,我们因为待会要输出这个描述嘛,所以说我用一个simple,大家还记得吧,有一个simple。什么呢?Sample date for my。我进行格式化,格式化的时候把它的年。越。日输出。十分秒也输出来,这样呢,待会我们好进行这个比较,对不对,好,这是一个格式化的一个东西。格式化的东西,然后呢,有了这个格式化以后,我们就可以拿到。
14:03
一个肉串。对不对,拿这个运算,比如说十斤,我把这个字符串拿出来,等于什么呢?等于我们的这个格式化。就是simple date for me.format一下把谁放进去,把DATE1放进去。把对一放进去以后呢,我们就可以把当前这个时间输出来了,就说排序前,排序前的时间是。是多少呢?我们将其输出。对吧,那就是刚才我们说的这个时间。Date。好,那么排序后我们也把这个时间输一下,我把这个复制一下,排序后这个数组我也不打了,因为告诉你8万个数据,你打出来非常的耗费时间,所以说这个呢,我也把它注销。没问题吧,好,那把这个复制过来过后呢,这个是DATA2。这个我们就不要了,这句话我就直接删掉,然后呢,格式化的时候是对对二格式,格式完了之后把这个。
15:07
排序后的时间也把它输出来,排序后的时间我们看一下8万个数据,现在8万个数据在排序前输出了时间,然后呢,排序过后我们又输出时间,我们看时间大概是多长,运行一把。好,同学们看到。同学们看。现在呢,排序前做了这个工作了,我们等待一下。好,我们等待一下。时间为什么这么慢呢?好,你看这个时间很慢,你看到没有,就说我8万个数据,我8万个数据大家可以看看这里我一共产生了个十百千万八万个数据,我耗费的时间大概是。11啊,十几秒呢,十六十六秒的时间。
16:00
还是很慢,我们再执行一下,看看是不是仍然是16秒。这个第二次实验,第一次实验可能不一定完全相同哈,可能会有一些小小的差别,我们再看。就说待会儿呢,我们用这种方法可以可以比较直观的看到到底花了多少时间,虽然我们用时间复杂度可以看到时间,但是不直观。对吧,不能告诉你是多秒,现在这个比较直观,你看22。45这个花了多少时间呢?这个花了23秒时间。对不对,刚才是19秒,现在是23,大致就在这个范围,就是呃,20秒左右,20秒左右,待会儿我们呃,在写另外的排序算法的时候呢,我们可以进行一个比对啊,可以进行一个比对。好,我们看看这个到底有没有效啊,再把它改成一个小一点的。你看小的时间就很快了,看到没有八八个数据一下就出来了,对吧,到了8万就变得比较慢了。
17:04
比较慢。所以说可以看到冒泡排序法呢,它的速度其实并不是很快,你8万个数据将近花了20秒左右。对吧,这个其实还是比较慢的,就是在我这一个。在我这个时间里面呢,还是比较慢的,比较慢的好的,那当然跟机器有关系了,跟机器有关系好,那关于同学们,那关于我们这个冒泡排序的一个优化,还有整理呢,就讲到这儿,我们把笔记给大家板述一下。那刚才我们讲的这个冒泡讲了哪些内容呢?我们来捋一捋这个思路。利率这个事物,首先呢,我们对冒泡排序做了一个基本的介绍。对吧,好,我们做了基本介绍,把它的一些特点,它的一个流程给他做了一个介绍,首先说的是基本介绍。冒泡排序它是怎么样来做的呢?
18:00
它是这样一个流程。对不对,它是这样一个流程,我这儿就不一个说了啊,就是。呃,它是呃,发现逆序依次进行,这个比较相邻的是发现逆序就交换。发生允许就交换,那么在这里呢,我们有一个优化的过程。有个优化的动作就是什么呀,优化。优化。如果我们排序过程中,如果发现有一趟比较下来没有进行交换,说明已经有序了,如果有序的话呢,我们可以优化。对吧,好,这是它的第一点,第二点呢,我们这演示了一个冒泡排序的一个图解,也把它拿过来。这个图解的案例呢,没有我这儿。更直观,所以说我就不考不拿这一个。不拿这一个幻灯片里面的,我直接把这个拿过来。对不对,用我的Excel表里面画的这个冒泡呢,更直观一点。
19:04
拿过来过后呢,我把这个步骤的一个整理也给大家小结的冒泡排序的规则也给同学们拿到这里来。好,我就放到这里了啊,小结了,小结一下,小结上面的一个图解过程。OK。孝接他的一个过程,那这个。图解过程说完了以后,是不是我们就用代码给大家演示了一个冒泡的实际的一个应用,对不对,而且呢,我们在讲的过程中,实际上是一步一步给大家推导出来的,让大家更容易理解。好的,这是我们举的一个例子,那具体的代码呢,就在这里啊,代码实现,代码实现呢,我直接给各位同学把代码放到我们的笔记中就可以了。好的,我们在这里运行一把。
20:01
放这儿啊,放这儿。好了,嗯,那关于冒泡排序的。这个优化还有冒泡排序的整理呢,我们就先讲到这儿,同学们听完这个呢,我建议大家按照刚才老师推导的一个这个过程,把这个代,把这个冒泡排序的一个完整版本自己写一遍,然后再听我们的下一个。排序算法这样呢,你在听的时候就不会乱了,因为我们这个排序法一共有八个。你稍不注意就会混在一起。就是自己会。会混混乱,因此你先把这个冒泡排序呢,自己写上一到两遍,然后再听下一个。排序算法会比较到位,好,那这块我们先说到这。
我来说两句