00:00
好,同学们,下面呢,我们来一段代码给大家实现一把,还是对一群小牛,它有考试成绩是幺零幺三十四幺幺九和一,从小到大进行排序,好吧,那现在我们直接升代码。打开我们的eclipse对吧,然后呢,我们在这里来新建一个类。新建一个类呢,我们这叫做insert so。Insert。So,然后呢,我在这个地方呢,我们先来直接写一个方法,叫做插入排序,插入排序static void。对不对,好,我写VO,然后写个insert so。那这个时候呢,我们仍然是接收一个数组。对好,同样我们使用什么方法呢?我们使用这个逐步我们使用。逐步啊,就是逐步推倒。推导的方法来讲,方式来讲解,便于理解,便于理解。
01:08
便于理解。好,那现在我们先来看第一轮,我们来看第一轮,现在呢,我们假定哈,呃,假定这个就是四个数据了。这样,因为四个数据简单好讲嘛,所以说我就用四个数据,不用刚才的六个数据了,同样我这先定义一个数组。它就等于这四个数没有问题吧,没有问题,那么我们来看第一第一轮大家看一共四个数据,一共有几轮,三轮是吧,第一轮。呃,那么同学们看第一轮我们应该怎么去做呢?第一轮针针对这个数组来说啊,注意,如果是针对这个数,针对这个数组来说,我们第一轮它就应该由这个得到怎样一个数组呢?就是给34找一个位置,是这意思吧,那他做完以后应该得到这样一个数组。
02:03
是101,然后是119,然后一是这样子的吧,也就是说给34。给34,把这个34插入到第一个。插入到这个有序。有序列表里面,而第一个有序列表,其实第一个就是101,那我现在开始写这个代码了啊,开始写代码了,首先呢,我先定义,我先定义这个待插入的。注意听这块啊,带插入。差带。插入的这个数。代超数,那这个代超这个数到底是哪一个呢?如果针对第一轮来讲,我们就具体化明白啊,比如说insert value。它就应该等于R几呢一。能理解的,因为你第一个带插入的不是34吗?对不对,那这个数这个34是不是要跟前面的。
03:05
前面的这这个有序列表进行比较是吧,所以说我们再定义一个带插入数的这个索引。Insert,那这个应该等于几呢?就应该等于零。就改名,因为你你原先你这个34,它首先要跟这个101。比较101是不是就是相当于这个一的前面这数,准确的讲应该是这样子的,是一减一。为为什么是一减一呢?因为你现在带插入的数,它的下标为一,那么你就应该跟它前面的就是34的前面,最前面这个数,最前面数它的下边应该是在它基础上减一,能理解我的意思吧。OK,也就是,也就是什么,即即这个R1R1。的临近的就前面前面这个。
04:03
这这个数的下标。能理解我的意思吧,好,那这样子做完了以后,是不是你这个地方有一个循环的操作,去给这个insert value找到一个位置,下面就干什么呢?给谁呢,给这个inser的value找到插入的一个位置。插入的位置。因为你将来要把这个insert放到哪个位置,你你得通过一个循环来做,所以说我用Y循环了,大家看我的这个逻辑啊,如果我们这个insert的这个index大于等于零。这句话保证我在为34找这个数的,呃,在让这个34跟前面这个有序列表进行比较的时候,这个insert index呢,不至于越界,这句话主要是用来保证不越界。我写到这难。
05:02
说明一下啊,说明这句话保证保证在给哪一个呢?在给insert value。找什么呢?找找这个插入位置时,位置时这个不越界。不越界,也就是说它不能跑到这个负一去了,对不对,同时还要保证什么呢?这句话大家要理解一下啊,大家看这这段代码能不能理解,就是说inser的这个Y6。如果这个insert value小于R,大家看我的这句话能不能理解insert index?大家看。如果在inser index大于等于零的情况下,同时还满足ins射的value小于这个r inser的index,说明什么问题?说明什么问题,是不是说明你现在这个34,如果小于,你看这个34,如果小于101,说明我这个34还没有找到位置。
06:08
为什么呢?因为你这个1011后面移动。那这句话满足的话就说明什么呢?哎,这句话就保证了,就说你现在还没有找到说明带插入的数。带。啊,带这样写的啊,带插入的这个数还没有,还没有找到这个适当的位置,或者叫插入位置。那么如果没有找到这个插入位置,就意味着我们当前这个101应该怎么样往后移动。就是你当前这个101要后后后移,及现在要干什么呢?就需要就需要将什么呢,将我们这个呃,Insert index这个值往后移动,大家理解我在说什么吗?就是要让这个当前这个值后移。
07:04
后羿。为什么要后移呢?因为你这个30是不能够插在这个位置,得往前面,但是你这个要要后后面移动,把这个位置让出来给我。所以说这句话呢,应该怎么写呢?得这样写了啊。Insert index加一等于index。这个这句话,同学们这句话就代表将应该后移。也就是说,如果一旦这个发生的话,你可以理解成好像这种感觉就什么呢?就是你你可以理解成是这样一种动作。就是原先这个值,它移动了一下,就变成101101119和一了。那有些同学说老师那不对呀,那34不就丢了吗。大家有没有认真看34是不是已经被我保存在insert value这个地方去了?
08:03
是我上来先把这个insert value先保存到就是这个34先保到这个变量里面去了,能理解吧。OK,那这个时候完了过后是不是,然后让这个insert index干什么减减。为什么要减减呢?因为我我得让这个,让这个344跟101前面这个数再进行比较。但是有同学老师,那如果越界怎么办?我这有条件约定的。如果insert index,它。小于零了。啊,小于零,那这个就退出,说明我们这个数就应该加到当前这个数组的,就是那个有序列表的第一个位置是不是好,那理解到这个地方,我就写句话,当退出。当退出while循环时。Y循环式说明什么呢?说明插入的这个位置找到。这个位置应该是在哪里呢?这个位置就应该是这个位置insert。
09:05
Inex加一这个位置。为什么要加一个一呢?因为你跟前面比较的时候,是跟前面这个比,那你比完了过后,我这个数如果不再满足条件,是不是就应该在你后面,我举一个最极端的例子啊,大家看我举个例子,你们一下就明白了。答,假如。假如我这个34不是34,而是。334。我上来过后,先把这个334放在这个地方,然后inser的index是不是就是就是1.1等于零,那么334是不是上来过后第一个条件就不满足,因为我的三三百三十四并不小于你,不小于你我就直接退出,退出过后是不是我这个334就相当于要直接加在哪个位置呢?加在这个insert的加一这个位置。因为你上来1INDEX等于零嘛。所以说这个位置就应该是insert加一,能理解我的意思吧,没关系啊,理解不了,待会我第bug一下啊,没关系,理解不了,理解不了不了。
10:09
呃,理解理解不了的话呢,我们一会我们一会这个我们一会就debug debug你一下就明白了,好吧,因为这个我画一个图,你你不去走一圈还是不能理解,那这个时候应该怎么走呢?好,我们就加一个。这样写index。加一等于谁呢?等于insert value就搞定了。就搞定,但是实际上你这儿可以加个判断。你这加一个判断,就是如果说我们我们这个上来过后,这个index他上来就就是就是最大的,那你其实不需要不需要再做这个动作,但是你加判断呢,本身也需要一个时间,所以说这个不是一个大的问题。就你加判断不加判断都无所谓,好吧,好同学们,我们来我们来看看第一第一轮过后这个数组变成什么样子啊,第一轮后。
11:08
第一轮。第一轮插入后,第一轮插入后呢,同学们可以看到,这时我们可以看到这个数组就应该是。谁呢?应该是这个了,待会我们来给大家打出来看一看啊走。那接着呢,我们把这个数组打出来or。RA这个地方要这样写啊,用这个A工具类里面有个to string,然后呢,我把这个数字打出来,大家看一下。好,同学们,我们执行一把。执行的时候呢,我直接调用这个insert sort,把这个OA放进去,我们执行一下,同学们看效果,是不是第一轮就把这个34。放在这个位置了,那么我们debug一下,让大家理解的更到位,好,我这加个这个东西,我们debug。这次大家根据刚才老师的讲解再来理解一下好吧。
12:02
好,现在呢,我们进入到这个代码里面去。好,进到这里面了啊,首先看insert value往下走,Insert value是不是就是34啊。434是吧,Insert index是不是就是零,因为我是一减一嘛。是不是inser的,呃,INDEX0,好,现在我开始比较,那么ins射的index大大不大于零,零零呢,是在这个范围吧,然后我们看inser的value。它小于这个值吗?Ins射的value现在是34,看这34,这个34它小于or inser的index什么不小于,因为你这个inser的value,它现在这个值是谁啊,是101。说明这个位置还没找到,是这意思吧,因为你看你打出来这个现在O瑞零的话是101因,因此它它满足这个条件吗?这个insert。
13:00
Value,它是它就呃是啊,刚才我们说的是这样子的insert value34,它的确小于,它小于说明这个位置没有找到,没有找到的话呢,我就让这个101往后移,往下走,是不是进去了,进去过后往下走。往下走,我们看这个数组现在变成什么样子了,看是不是这个数组变成了幺零,1101119和一,也就是说刚才这一个原先那个OV0往后面移了一下,但是原先这个OV1是不是已经被我用insert value保存起来了,所以你不用担心。然后紧接着我们再去比较这个因式,减减减减完了过后,大家看这个变零变负一了,负一不满足这个条件,不满足这个条件呢,同学们看,往下就退出来,退出来过后我要把这个因式2344加到哪里呢?加到第一个位置,因为这是负一,负一加一就变成零,所以说这样一走,我们再看数组。数组现在是这样子的啊,101101111和一,当我把34行一走,我们发现34就进去了。
14:07
看进去没有三四十就来了,以此类推,好整个流程就是这样子的,整个流程就这样子的,好那这个我们就呃讲到这,那后面这几轮其实我不用说,大家知道怎么写了吧。各位,大家看后面这个代码就变得比较简单了,这是第一轮,我们来看第二轮。第二轮这个思路就跟刚才非常的像啊,非常像第二轮那一样,我们上来呢,先把这个带插入的数确定下来,这时第二轮咱们要找,要给谁找位置呢?给第三个数。比如说下边为二的,那同样应该是他要找的位置就应该是二减一了。也就是说给找这个O2的前一个数作为嗯,它的下标作为一个比较,同样这个Y循环是不是一样写一遍。
15:01
是不是这这个地方不需要变化大于零,这个成立,这边也不需要变化,也就是说while循环其实是跟原先是一样的。然后这个整完了以后,这段话是不是仍然是。这样做一遍。是不是这样子,也是,也就是说这个时候呢,我们只是把insert value进行了一个变化,这些并不需要变化。并不需要变化,是不是好,那现在我们把第二轮也给大家打出来看一下。第二轮操作过后,我们输出来运行值。第二完了过你你没有发现这个119,因为119啊,嗯,大家看到这个119,你在给119找位置的时候,呃,其实他上来过后一下就找到位置了,是这样子的吧,因为你119本身就是大于10101的第一个条件,他在第二轮的时候,这个外循环进都不进去,直接就找到位置了。好,我们再看第三轮。
16:01
我们再看第三轮,第三轮这个代码呢,其实跟前面也是非常的相似的,来把这个呢也给同学们写到这第三轮是不是相当于给第第四个数找位置,那这个名字是三减一,因为位三的前一个下边是二,就三减一。那为什么我要写成三减一,待会我要看规律,这个一写下面是不是都不要变化,然后直接写第三轮来走一个代码。看第三轮做完了以后,是不是这个一就跑到最前面去了,还有第四轮吗?没有第四轮了,因为我们一共四个数。那你只要确定三个数,那当然你因为你第一个数就已经是有序列数列了,那你其实就是跟后面三个数找位置嘛。说一共三轮就搞定啊,三轮就搞定,那现在呢,我们有了这个推导过程过后,我现在用一个使用什么呢?使用这个for循环。
17:01
For循环来把这个代码整理一下,把这个代码简化,代码简化。代码。哎。代码,代码简化。对吧,那现在呢,其实我们只需要一轮,把这一轮拿过来用用就可以了,来吧,那这样子我们把这段代码拿过来。我们就这一轮哈,就在这上面改一改,那为了不跟下面的冲突呢,我先把下面的代码先注销。好的,然后我把刚才这段代码拿来用一用。大家有发现,我们怎么来处理一下,就把这个事情就搞定了呀,是不是来一段负循环。I。等于什么呢?是不是从一开始的呀,因为我们。给第一个数找的时候,给第一个数找的时候其实就是二位一,因为第零个就是呃二位零的二零其实就是呃,本身就是一个有序的呃列表了嘛,是不是说说诶怎么为什么还在这个debug的模式啊。
18:10
把这个第八个先先关一下。好,同学们,我们回到这,那么I小于几呢?我一共要经过经过几轮呢?R点认识。奥认识哀佳佳。哎,讲讲同学们,我我我问大家一个问题,我我问大家一个问题,我这个地地方需不需要减一。同学们先想一想,我这个地方需不需要剪一?请思考需不需要检疫?我这不需要减一,因为你这已经是一零了,你再减一的话,那最后这个数呃,他就不参与不参与找位置了,这个千万不要减一啊,同学们好,这个代码呢,我往这边后面挪一下。好,这个时候把这个一改成几,改成I。把这个一改成I,不要改错了。
19:01
下面代码是不是不需要变化?也就是说这个代码就已经完成了,然后这个地方呢,为了看到这个效果,我这应该怎么写呢?直接写I,因为你I就是从一开始的,所以说刚好跟这个轮数也是匹配上的,来同学们我们执行一把。我们看这个代码呢,就OK了是吧,第一轮第二轮,现在我们可以把这个数据做的稍微复杂一点。来,我们再加一个负一,再加一个89,那一共有几轮呢?你现在一共有六个数,应该就是五轮。对吧,一轮二轮三轮,这你看这个地方最后这个数的确就是一个有。有序的按负11344849101和119。是吧,好,那这个代码呢,就是我们插入排序的,呃一个呃111个讲解,大家看看理解了没有,其实并不难。这个代码呢,并不难,是不是跟我们刚才讲的选择排序区别是在哪里呢?区别是他上来过后,先把第一个数当做一个有序,然后依次为后面的无序列表的每一个数给他找位置并插入就完事了。
20:17
好,那关于这一个操作排序的一个讲解,它的一个基本的讲解就先说到这里。
我来说两句