00:00
我刚才讲的一个方法,这个就好写,你不用这个方法,我写出来你都不一定看懂,或者说看起来比较郁闷。那么同学们,刚才我们讲的一个方法,让他在发扬光大一点啊,Insert shorts。插入排序思路,先把它拿过来,同样是这个代码啊,还给我一个数组吧,这边我仍然有个测试数组,还用它。还有它,我们还是从小到大,这是一个测试数组。这个测试数组呢,我们仍然对吧,R等于二把数据扔进去啊,当然这个地方呢,我要用小括号挂起来。来吧。OK,嗯,思想把这个排序的思想先写到这儿。我们把这个事情先排在这啊,就是。这样写就是插入排序,排序的一个思路,这个思路刚才呢,我们在幻灯片里边各位同学已经看到了。
01:04
我直接把它拿过来。OK,那这样子的同学们就开始来写啊,我们先写一个最简单的第一轮。先做第一轮来。我们说第。一轮。第一轮排序。啊,操作排序,第一轮操作排序,那第一轮操作排序,其实这个结果应该变成什么德行呢?大家看其实他应该这么做的啊各位同学。他实际上先把呃,他上来过后,他其实是把这个看成是一个呃101看成一个有序。有序表的是吧,然后给34找一个位置,这个能理解吧。那也就是说他第一次做完了以后,这个结果应该变成什么样子呢?是34。101,然后这边是119和119和一,这个大家看能不能理解。
02:00
好,这个我们就硬写了,我们先不去考虑那么多东西,我们从里面往外面写就变得简单,那你想一想这个思路,你你在做插入排序的时候,是不是不是首先得先把这个待插入的这个数先把保保存起来,因为你要比较啊。所以说你第一个动作先干什么?来,各位同学,我们先写一个insert。啊,Value这个能理解吧,这个insert value是不是就应该是R。一就就34嘛。你先不要考虑循环的问题。然后我再问大家一个问题,就是这个insert的这个索引,它应该是哪个位置呢?是不是他他在这个进行这个索引的是索引就应该是走走这个位置开始走啊。因为你这个ins的inser的这个插入位置,是不是就说你可以理解成这个inser的。
03:00
事呢,就是我们这个有序列表里面的最后这个元素的下标。为什么?因因为我我要从这开始比呀。好,那么这个时候其实就应该是一减一。一减一,我我说一下这个含义啊,这个变量表示表示有序。列表有序表的这个最后,有序表的最后。这个元素。的下标。没没问题吧,然后有了这两个东西,我们下面就可以进行这个循环的。这个控制了,那Y循环来了啊,大家看我这个条件怎么写。花条件。那么只要这个insert index大于等于零。也就是说,只要这个in射的。
04:01
只要只要就就说这个我们这个带带插入的下边,还在这个,还在这个有序列表里边,是不是就我就可以。继续比较。并且满足。并且满足什么呢?就是你这个待插入的数据。你这个数据就是你这个准备插入的数据,它大于大于谁,它如果大于我们这个位置的值就大于谁呢?大于这个。这个值啊,就大于这个我们这个RV。注意听insert。这什么意思呢?如果这个条件满足,说明我们这个位置找到了没有。没有找到是吧。是不是代表没有找到?这个你看嘛,零是大于零,同时你这个带插入数比人家这个前面这个数还大。是不是代表?
05:01
就说就说你就说假,打个比方,34 34大。呃,34大于这个大于这个吗?三十四三十四大不大于11110910101不大于不大于,说明这个位置找到了没有。没有找到是吧,是不是没有找到呀,说明这个位置还没有找到。再再理解一下。是不是没有找到这个位置啊,说明说说明,因为我要找到这个位置是应该小于它的吗。我大于他说明还没找到,所以说没还没有找到位置,还没有找到。这个位置。不着急啊,我们先把它写完,因为这个插入排序比那个选择排序要稍微的难理解一点,而且而且可以告告诉大家它的效率更快,原先我们是三秒,这个家伙只要一秒。就搞定了,那他肯定是有他的优越,就还没找到,没有找到是不是就要就按照这个逻辑,我们就应该把这个101往后面移一下。
06:03
这个怎么移动呢,注意看啊。Insert index加一。等于二。Insert。Index这个动作这句话是表示什么意思?同学们能看到吗?是不是代表把101往后面移一下,也就是说如果我执行了,执行了这个第18行这个代码,我们这个数组就变成这个样子了。这个前面这个值仍然是101。然后这边就变成101了。这个有点不好理解,那这个时候这个是1091。变这个了。说老师那34怎么办呢。是被你保存起来的。没问题吧,好,此时此刻你这个insert index是不是要减一了?因为你你原先是让他这个进这个原先你在这儿。
07:00
你原先在这个位置,在这个位置你比比较了,比较了一次,是不是还在往前面继续比啊。但是这个这个时候这个很遗憾,你这个在比的时候,它已经不再大于零了,那只要也也就相当于说,只要出了这个Y循环,就找到这个位置了。因为他出来只有两种可能。他出现,他出这个外循环只有两种可能,要么就是。它小于零了。要么就是它小于这个带插入这个值了,能理解吧。它只有这两种东西可能性才能出来吗?好,这样子只要一出来。如果出了。出了什么呢?呃,离开,或者叫叫叫叫叫。你就要退出了啊,如果他退出了这个Y循环,说明这个因这个插入的位置。插入的位置就找到了。他应该插到哪里呢?各位同学,他应该插入到哪里呢?是不是它应该插入到index加一这个位置啊。
08:06
你想一想我们就去,我们就以这个为例,各位同学我们就以这个为例,比如说我现在有34要往这边加入。34比这个101要小,此时此刻,同学们insert index是不是目前是指向它的?当你做了一个动作以后,做了这个操作以后,是不是这个in加一。这个就变成101了。同时这个你又减了一下,一说说明这个指标是不是就指到这个位置了,这个其实已经变成负一了。能理解吧。他如果。等于等于负一,负一不大于等于零,是不是就退出来,退出来过后。退出来过后,你不要忘了,负一是不能放数据的,那也就是说这个时候你负一加一是不是变成零零,这边加了34,是不是就相当于把34扔到这来了。
09:00
是不是这个结果就是344101了。看懂了吧?这个应该看懂了吧,王传成看懂了吗?开心啊,很好,那这个应该没问题了,那同学们我们看看第一次这个做完了以后,这个结果是什么呢。就是这个第一轮。第一轮的结果是。好,各位同学,那现在我们把这个数打出来给lawyer MK。好各位,我执行一下。那这个时候这个结果跟我们想的是不一样的呢。诶,不对啊,我我我做了个什么动作呀。没有进入被我循环。哪没有进入Y循环?好,我们看看这个地方啊,大于那这个逻辑,我我是不是写错了呀。哪儿写错了?
10:03
把第几行改一下。不对,这个应该它也是,呃,应该这样子啊,我看看啊,哪里写错了呀。这个这个方向写错了吗。Inex大于等于零是正确的吧,对,Insert。大于。它不大于这个是吧,哎,是不是应该写小于啊。我我们看一下啊,小于它。哎,我这个逻辑再再捋一捋啊,再捋一捋。哦,对,是是这样子的,Ins射的34,如果小于它。哎,如果我小于它是不是才能往前面走啊,啊,刚才这个这个逻辑说错了一点啊,不好意思,就是这说错了啊,如果我这样写的话,那将来插入的就应该是从大到小了。
11:00
是不是这个地方我刚才说的有问题,因为你想嘛,就是我现在是从小到大,我们现在别搞晕了,从小到大,那从小到大说明说如果我小于你,我还可以继续走,如果我大于你了,那那就没法走了,是吧?好,这个应该是这样写的,大家看一下运行。啊,这个门就是34,好,再跑一下啊。三十四幺零幺,好,我们再来做第二轮。第二轮啊,这是第一轮我们就做完了。再来做第二轮。好,这边我又把它改成R。第二轮又应该怎么写呢,同学们?第二轮。第二轮各位是不是我们把这个地方带插入的数据就改成了二。然后你要插入的下标二减一。对不对,然后这边有个不要再写它了啊,然后这边大于大于零不用变,这个也不用变,这个也不用变,是不是都不用变吧,其实就就改了这么两个字,再来跑一下。
12:14
好,再来跑一下,我们发现是不是也是正确的呀,好,我们再来看最后一轮,第三轮。第三轮代码OK,第三轮其实你发现改动的地方也很小,就是带插入是三索引改成三,你看改动都非常小,然后这边改成了第三轮。啊,刚才这个地方写错了,第三轮结果我们再跑一跑。各位,第三轮我们发现。对不对。你这个一是不是找位置,是不是找到最前面去了呀,正确的啊,完全正确,那下面呢,这段代码写完了过后,我们发现。它的每一轮代码几乎是相同的,那这个时候我们就来把它进行一个处理。
13:03
啊,从我们发现规律,发现规律。啊,规律。规律好,发现这个规律呢,我首先把这个代码先注销不要了。好,我不要了,然后呢,我们把它写成一个循环,我们看它是哪个在变化呢,其实就是这个是在变化,也就是说我只需要把这段代码拿过来。各位,我只要把这段代码拿过来,我用for循环来处理我带插入的数据是从哪里开始的呢?是从一。Until。哪个呢,就是我们。or.n减一。哎,是要减一吗。Until,诶,怎么写错了啊?哦,是不是要减减一还是不减一啊同学们。需不需要减一不减一,因为你这个on t本身就不包含它了,是吧,但是你不包含它,但是这个R点减一那个最后你还是要插入的吧,好这个不要不要把它搞晕了,然后把代码呢,刚才这段核心代码我这一复制。
14:11
好把复制,那同学们这个地方应该改成几。I。那这边应该改成几啊各位同学。是不是I1啊。对,然后这边这个第几轮是不是刚好这个,他这个A刚好是从一开始走的,就连这个都不用换了。好,各位同学运行一下。那么运行完了,我们看这个结果呢,我们想的是吧。一样的好,我们再多测几个数据。来做这几个复区一。45。90啊900,我们再跑一下。我们再跑一下,看这个结果吧,同学们。结果对吗?是正确的吧,从小到大,那刚才我那个地方呢,如果把这个换了,换成这个。各位,大家觉得是什么顺序?那就是从大到小。看代码是变成从大到小来。
15:02
没问题吧,就这么简单,就这么简单,OK,那我们这边就变成一个核心的地方,刚才老师这分析的有点问题啊,OK,那现在。显然我们应该把整个这个波循环呢,包到我们的一个什么呀代码里边去,没有必要写到这儿是吧,我们单独的写一份函数。Di in search song。同样道理,我们在这里接收一个数组。你给我一个数组,我来。把它处理一下就可以了,那然后这边我们在处理的时候只需要这样做,那这边这个打印我就不要了,同学们没有意义啊,没有意义,然后我在这里调用我们insert sortt一个方法把二填进去,然后呢,我说一下排序后。对,排序后它应该变成什么样子呢?点MK,好,我们输出同学们排序后这个结果。
16:04
大家看是不是跟我们想的。一样的。好,那现在我们是不是应该测一下它的效率了?对吧,把效率给测一下,看看效率到底怎么样,那同样我们把前面做这个选择排序的这一段代码拿过来用一下。这是映射的啊,我先把这个数据去掉。把这个数据去掉,走到这儿。啊,然后这个输出我也就不要了。不要了。我们直接看。这个。添加排序,插入排序后。插入排序后,它的时间是。大概是多久,我们从这个select里面把。排序后的时间也给大家输出来一下。在哪里呢?在这儿。我们再检查一下啊,首先我在这儿随机的生成了一个8万的一个数组。
17:03
啊,随艺术。然后我在这地方打印出了排序前的时间。排序前的时间,然后我调用。我调用这个插入培训。调用插入啊,调用插入排序,我们看时间大概是多长。8万没有变化运行。好,我们运行看下结果吧。一秒钟。来看一下。看问问你啊。一秒钟,诶,大家看是不是速度又快了一点。但是他还不是最快的。那待会如果我们这个8万数据让快速排序来来排徊,你发现他用的是零秒,它可能是毫秒级的。毫秒级,而且他在80万都是都是大概一秒都不到,那这个速度它为什么会提升呢?大家想一想。
18:05
它为什么会提升呢?它提升的根本原因,你看他从这个维度上来说没有什么变化,但是它提升的这个根本原因是第一个。他提升的这个根本原因,你看这个示意图。他每一次。这个数据是从后往前找,那么在往前找的过程中并没有交换,它并没有交换的动作,它只是把一个值赋给一个值,这一下就。变得很快了,第二个他每次在插入的时候,这个都是一个有序的。而且每,而且这个有序,有序这个数字呢,也比较容易找到,找到适当的位置啊,所以说整体来说,它这个因为没有交换,只是一个覆盖,这样的时间就变得。节省了很节省了很多时间。是这样的一个逻辑啊,好一秒钟就解决了。这个插入排序,那现在呢,我把这个插入排序给大家整理一下。
19:04
好,我把这个整理一下啊,操作排序我们是怎么讲的。协作代码。呃,操作排序的基本介绍。写到这儿了。插入排序的基本介绍。然后我们讲了一下插入排序的基本思想。他的思想是这样子的。啊,核心思想就是这样子,把N个代排的元素看成一个有序和一个无序列表。然后开始时有序列表含一个元素,无序列表含多个元素,然后依次取出做核心思想就是把它看成两个部分。然后呢,从那个无序列表找一个往里面插。好,这是它的一个核心思想,这边还有一个示意图,我也给大家拿过来。这是插入排序的一个示意图。给大家放到这里。放这里,放这里,诶这个地方有点问题啊,放到这里。
20:03
放到这里过后呢,然后这边我们就有代码了,对吧,这边就是代码实现,就没什么可说的了,就代码实现。就是我们插入排序的代码实现。插入排序的代码实现。给大家也放个例来。代码实现OK。前面这个是插入排序示意图,插入排序的代码实现也放这吧。好,代码实现就在这个位置。Insert。Shot。啊,放好了同学们,那关于插入排序呢,老师就讲到这里啊。
我来说两句