00:00
同学们,我们来测一下这个堆排序的性能,刚才我已经把这个写完了啊,写完了,而且呢,我不但我第bug这个无所谓了,因为我刚才已经把它讲的很清晰了,我不在第bug了,堆排序的速度非常的快,我测了一下,在我的机器上800万个数据呢,基本上43秒,也就是说它的这个线性复杂度,哦,它的这个时间复杂是这样子的,是N。Log等,也就它是个线性对数阶,线性对数间,来,我们玩一把。同样道理。现在呢,我把这个数组调成一个800万的,大家测一下。那我们原先在进行数据测试的时候。是不是前面都有这样的代码,我用一用好。把这个代码拿过来。没问题吧,同学们,我先把这个拿掉。这个拿掉。好,这格式化一下。格式换项,我现在一共有多少个数据呢?个十百千万,十万百万八八百万个数据,那在排序之前打印了时间,在排序之后呢,我们也把这个时间打印下。
01:11
看一下他的花费时间大致是多少。排序过后时间是这么多。是不是看他是否,呃,速度还是OK的,这是排序后的时间,然后呢,现在我们就不能打这个数组了,再打这个数组就太大了,好吧,再打这个数据太大了,我把它注销,注销过后,呃,为了验证一下数据。这个对不对,我们先把它改成八个能够测试的数据,在这呢,打印一下这个数组。打一下这个数组,好,我写一下,排序后等于加上二。A。2.twostring,好,把二放进去。好,同学们,我们运行一把吧。我们用一下看看效果怎么样。首先可以看到的确仍然是一个有序的是吧。从小到大好。
02:02
中小大现在呢,我们把这个数据量提上去。直接提升到800万个十百千万。我看8万怎么样啊个十百千哦万八万八万八万,好,我们运行一下8万个数据,基本上是秒杀对吧,秒杀再执行一下。8万个数据是很快的,那么我们提升到80万。看速度怎么样。80万个数据呢,也是秒杀800万个数据。800万个数据,这个呢,可能不会秒杀了,要点时间了。这32。32秒。四秒钟好像五秒钟了啊,那我再来运行一下看看是怎么回事啊,可能我这机器现在跑的程序太多了。好。五秒钟啊,五秒钟可能机器机器性能的影响啊,但整体来说还是非常快,对不对,还是非常快不对啊,我应该测的以前都是三秒到四秒看一下。
03:06
好,这次你看比较接近四秒了,嗯,好,那同学们关于这个堆排序呢,我们就给大家讲讲解到这里,代码呢,我就留到这了啊,就是关于分布怎么写的,我也给大家写到这了。那核心的代码其实就是这段。好,我把刚才讲的堆排序的内容呢,给各位朋友板述一下,给各位朋友板述一下,我们怎么讲的呢,来捋一捋思路。来捋捋输入,首先呢,这个这个章节就已经进入到数结构的实际应用,是这样子的吧。我先拟一个树结构的实际应用。那么我们实际应用的第一个应用呢,就是讲的堆排序。是不是讲的堆排序啊堆排序。诶,好。粘过来堆排序,那堆排序我先给同学们做了堆排序的基本介绍,就是什么是堆排序?
04:02
做了一个介绍,这里面呢有这么几点。是不是一共有四点。对不对,对,排序在这我已经说了,它的时间复杂度是这样子的。好,那这里面我们在讲之前先说了什么叫大顶堆这个概念,因为你不明白大顶堆,我们就没办法玩,大顶堆的特点呢,我也给大家写了。看到没有。大顶椎的特点就是。这样一个特点,其实这个特点呢,我们在呃,在在讲那个顺序存储。二叉数的时候其实提过,就是I和I,它的左右子节点的关系,我们提过,只是这里呢,在引入了大小的关系是不是好,这是。我们大顶堆的一个举例,大顶堆说完了以后呢,我们又给同学们举了一个小顶堆的案例,就什么叫小顶堆。小顶堆呢,就说如果我们是排序是从大到小的话呢,我们可以用小顶堆来实现,那这块呢。
05:05
具体来说。小顶堆的特点就是这样子的。这就是一个小顶堆,是不是同学们?小顶队完了过后,我们这做了一个小结,说什么呢?说如果你是要升序排列,我们用的是大顶堆,如果你是要降序排列,我们用的是小顶队,这个呢,同学们可以根据刚才我们分析得出这个结论。当我们把这个大地堆、小地堆说完了以后,我们就给大家说了一下堆排序的思想。我们说一下堆排序,大体他是怎么做的,是不是他的思想呢?有这么几步。但是大部分同学听完这个这个文字描述的描述的事情,不知道老师在说什么,因为对派序确实不是很好理解。所以说呢,我这里马上就给同学们画了一个图解。来继续解释了对于排序的一个过程和它的步骤。
06:01
是样子吧,同学们,我这里用一个图解来描述的,而且呢,举了一个实际的例子,这个堆排序的思想是在这,我们把这个呢也给同学们板书到笔记中,我插入一个小格小表格啊。把这个放进去,然后呢,把图也带过来。这样子大家以后再去看堆排序的思想的时候呢,可以看得比较清晰。好的,这个堆排序说完了,呃,这个排序完了过后,我们就直接上代码了,把代码给大家实现了一把,而且一边写呢一边在推导,不是说直接把代码给他敲过来就完了,还在推导。因为对于我们来讲,对于我们来讲啊,同学们,我们要去找一个代码来并不难。并不难,为什么不难呢?因为网上的这种代码太多了,但是你要把它理解了,这个是有难度的,对吧?好,代码实现,我把代码呢给各位朋友直接放在我们的笔中。再说一遍啊,希望同学们把这个堆排序自己能够敲敲下来。
07:04
而且其实也不难,因为我这已经讲的比较清晰,尤其是只要你把这个just help。明白了,其他都比较easy对不对,其他比较为什么这个讲呀加呀,我已经说的比较清晰了,好同学们,那关于堆排序的内容呢,就给各位同学讲解到这里,大家好好消化一下。
我来说两句