00:00
那现在呢,我们把这个冒泡排序啊,不把这个插入排序说完以后呢,我们同样也来测试一下插入排序它的这一个执行时间。和前面的两种排序算法来来比较看谁更快一点,好吧。那前面呢,我们也模拟,我们也来创建一个有八万八万个随机数的这么一种数组,好同样把这个拿过来排序前打印,好,我们来捋一捋。好把这个格式化一下,大家看呢,我这里也产生一个8万。8万个随机数的这么一一个数组,好的排序前呢,我们把时间打印一下。时间打印就按这条语句来打。特别简单,好,那排序过后。排序过后我们再来打印一下,因为刚才我们已经证明排序呃是没有问题的,对吧,是按从小到大现在呢,我们。
01:05
这这这个insert sot不就是调用排序方法吗?是调用。调用插入排序。算法,那调用完了以后,我们看看他花的时间有多长,同样在这里把排序后的时间打印出来。这个呢,就是呃他的时间,那因为目前我们呃有8万个数据,如果说我们再输出这个每一轮的结果,那这个可能就没办法了,因为数据量太大了,所以说我在这呢,就把这两句话给。注销掉,不然的话待会嗯,那这个打印打印的这个时间就特别长哈,那就不能体现出它真正的排序花了多少时间了。好,那现在呢,我们来执行一把,把这个注销了啊来同学们,我们运行一下,看看8万的数据,它花多长时间呢。
02:01
走起来。好,同学们看这是幺九对吧,幺九好,大概是。啊,四秒钟的时间,我们再来执行一下,我们再执行一次啊OK。好,我们再指一下,我们发现这次是五秒,我们再跟刚才的选择排序做一个比较,选择排序是不是刚才也比较过,我们来指一下选择排序。好,选择排序是三秒还是刚跟刚才一样,我们再执行一下选择排序。再次下盘选择排序,你看这是两秒,我们再执行一下插入排序哈,插入排序我们再来再来给他比比对一下。走起来,零三。零三。好,大概是五秒的样子,大概是五秒的样子,好,那大伙呢,对这个排序这句话啊,这句话呢,我们刚才讲过,呃,如果说你在进行这个排序的时候。
03:08
需不需要把这个insert给到他呢?呃,可以加一个判断,我们看如果加完一个判断以后是不是,呃,对这个数时间会不会有些这个提升,我们来做一个优化。好,这里我们判断是否需要,是否需要什么呢?是否需要这个赋值。啊,是否是否需要这个重置,因为你就跟刚才我们讲的,假如我们。给这个找的这个insert value呢,它就是在它实际的位置,那就不需要再进行这个。呃,这个插入了对吧,那么这加一个判断就可以了,加句怎样的话呢?大家想想一想,加怎样一句话就可以搞定这个事。加这样一句话是不是就可以了?同学们,如果我们发现insert这个value。
04:04
它加一个一。它就等于什么呢。它加一个一,就等于当前这个I说明什么问题?如果这个条件满足。如果这个条件满足,说明他有没有必要再执行这句话,没有必要,因为相当于说你这个I,呃,你当前假定这个I值就是该放的位置,就是你这个insert算完了过后,它就等于I,所以说这个满足的话,它就不需要再加入,只有什么呢?不等于I的时候,咱们才去执行这句话,是不是把这句话放进去好,放进去过后呢?我们先来验证一下这个数据到底对不对,我们先把它改成八。好吧,改成八个数据,这样呢,我可以来对这个排序过后把这个速度打出来看一看。来,走一个。排序过后,我们看看它到底是不是一个有序的,至少因为我改改代码了嘛,那如果改改错了怎么办呢,是不是,所以说我还是做一个验证,那验证的时候呢,还是老规矩,我们用A。
05:07
点two。十岁,然后呢,把这个数组放进去。对吧,把这个数组放进去,我们来执行一下,因为现在是八个数据,没什么问题,好同学们看八个数据证明的确是啊,有序的看这49537779,对吧,肯定是从小到大的,我们再来执行一下。是不是仍然是一个从小到大的,你看726,这是727,好,现在呢,我们把这个数据恢复到8万。恢复到8万,我们看这个时候速度有没有一些呃,提升呢,走一个。好的,11。啊,示意。哦哦,不好意思啊,这个不能打,这这个太恐怖了,因为我们这要再打的话,就是8万个数据,那没办法弄了,好同学们我们再来重新执行。
06:04
好,这是五六啊,五六我们看。五六执行完了过后大概四秒我们再执行一下。再执行一下,这是零五秒。对吧,零五我们看一下。哎,五秒差不多,没有什么明显的提升,对吧,没有什么明显提升,好那么这个地方,呃,Insert shortt呢,这个排序它的一个测试,咱们就就说到这,还有一点我再强调一下,假如我们要想这个插入排序从大。到小我们应该改哪一个呢?如果我要写的是从大到小,其实就把这个改一下就行了,把这个小于改成大于。小于改成大于就可以了,好吧,把这个小于改成大于就可以,没有任何问题,同学们呢,可以去试一下,如果说我把它改成这个,你看把这个八又改成八号改成八,然后呢,我这还打出来,同学们看现在就应该是从大到小了。
07:06
看到没有?是不是从大到小啊,再执行一下。对不对,是不是从大到小,大的在前面,小的在后边。小的在后边好,我先还把这个改回去啊,因为我们最先讲的呢,都是这样子的,对吧。再次行下,这下子我们就是从小到大又回来了。好同学们,那关于这一个插入排序的一个速度的一个验证呢,我们就到这里,现在把刚才讲的内容,咱们做一个简单的板书啊,简单的板书这这块我们讲的是插入排序。好,理解一下操作排序。给同学们板书一把。给同学们板书一版来,走一个。那么参数插入排序呢?首先我们对插入排序做了一个最基本的介绍。
08:00
对吧,最基本的介绍。那么这个基本介绍说完了以后呢,我们把插入排序的它的一个排序的思想给同学们说了一下。这是他排序的一个思想。对吧,排序思想呢也比较明确,就是把N个待排序的元素看成一个有序表和一个无序表。是吧,然后开始的时候呢,表中只有一个元素,呃,开始的时候有序表。只有一一个元素,然后呢,无序表有N减一个元素,然后呢,每次就从这个无序表里面找一个数插入到这个有序表里面去,这个呢就是所谓的插入排序,那这块呢,我们有一个示意图。这边我们画画了一个插入排序的一个思路图,也给大家放到这里来。这这个示意图还是比较清晰的,把插入排序的思想描述出来了,对吧,比如说第一次我们把三放在这个有序表中,第二次把25放在这个有序表中,所以说这个有序表呢,你们会发现哈,这个有序表它是在逐渐的变大的。
09:16
而原先只有一个,后面变231,谁推?好,那呃,最后呢,我们把这一个应用案例也给同学们写出来了,是不是这儿根据刚才讲的插入排序的这么一个思路和一个算法呢,我们。对一个考试成绩进行了插入排序算法的处理。那最后这个代码在哪里呢?代码实现我也给同学们放在笔记中去。代码呢,我们也是按照讲解的过程,一步一步推导出来的,是吧,一步一步推导出来的啊对了,我们这应该还有一个地方可以优化一下,就是这个值啊同学们看这个insert value没有必要放在这里面去。
10:02
其实我们把这个定义呢,直接拿在这个这个外边是不是更好一点,初始化给他一个零。这个也给他一个零,那在这这个地方呢,我们上来过后,呃,这个insert的index就放到这了,那每次呢,他就会把它放进去就完了,是吧,这样会更好一点。啊,你看这个结果也是正确的啊,就是代码也没有问题是吧,仍然是呃,一个从小到大的没有问题,这样子呢会小,呃这样来说呢,比刚才要好一点,因为你如果把这个变量定义写在负循环里面呢,其实也有一点开销,对吧,我们可以试一下。把这个再回到这个8万个数据,看这样改了过后呢,对效率有没有一点提升哈,好,同样我在这呢,就不要输出了。运行一下。好,这是16。是。啊,四秒钟啊,差不多也差不了太多,对吧,差不了太多,呃,但是呢,按照这个正规的写法,还是应该把这一个定义,咱们还是写在。
11:08
呃,这个for循环的外边会比较好一些啊,会比较好一些,好,呃,那这个呢,咱们就。就说到这儿啊,然后把代码给大家拷贝到我们的笔记中去哪里呢?就在这儿。插入一个表格放进去。放进去好的,同学们,那关于插入排序的一个速度的。一个测试和小结,我们就给大家讲到这里。
我来说两句