00:00
好同学们,那下面呢,我们就用代码把这一个选择排序给同学们实现一下,先看这个要求哈,说现在呢,有一群牛颜值分别是呃,这那我这个颜值就变成这个了啊。我用这个速度来说。那就不用上面这个,上面这个呢,呃,我看了数据不是很好啊,那么现在呢,要求我们从高到低进行排序,那刚才我讲的是从低到高,那干脆我这也是从从低到高吧,这样大家容易跟我刚才讲的呢,进行一个比较好,这是我们的一个要求,看明白了。好,待会我们整完了以后呢,我们也测试一下8万个数据,看看它和这个快跟那个冒泡排序谁更快一些。好,同学们,现在呢,我们打开这一个eclipse,我们来写一段代码。来,走一个写到这里来,那现在呢,我们叫做select song。
01:00
把主方法勾上。总方法勾上,现在呢,我们就直接开始写一个方法,写一个叫做选择排序,那么选择排序这个算法呢,我们上来给我这样写,先写一个static void OK,你给我写一个方法叫s select sort,那你给我传一个什么呢?传一个数组过来。这个没有问题吧,拿到这个数组,拿到这个数组呢,我们仍然用什么呢?我们使用逐步啊,逐步推导。推导的这个方式来讲解,来讲解这个选择排序,这样呢,大家容易理解,好吧,这个大家容易理解好,我们先来看第一步,同学们还记不记得我们刚才说的原始数组是这样子的,第一轮排序过后呢,我们把最小的找到好,我们先完成第一轮。待待会让同学们注意看他是怎么推导出来的啊,注意听讲。
02:03
这个其实是一个很重要的能力,就说我们有时候这个算法很复杂,你有一种方法和能力可以干什么呢?可以把它。理解的更清晰一些,我们先不去考虑一次性怎么能出来,我们先就做第一轮,把最小的放在这里,放在我们数组的第一位,这个是不是问题就简化了,所以说我们在做算法的时候呢,有个重要的思想,算法以后怎么思想的是先简单,先简单然后再复杂。啊,然后再再把它做的这个复杂一点。做复杂。所以说你要有这样一个能力,不然的话,嗯,遇到这个算法,你上来过后就去想,想一个最难的,往往你想不到。然后你先简单一点,诶,然后再把它综合起来,就跟刚才我们讲这个冒泡一个思路,这样你理解起来,还有包括你记忆起来都比较轻松,所以说先简单再复杂,说白了说的再直接一点,就是什么能力呢,就是。
03:06
就是可以把一个复杂的复杂的算法拆分成拆分啊拆分。拆分成简单的问题,然后再逐渐解决,然后再逐步解决,能理解我的意思吧,这是一个很重要的能力啊,就是说你能够把一个复杂算法拆分成简单的问题,然后再逐步解决,这最后综合。明白好,现在呢,我们就说第一件事情,那上来我就这个数组,到时间你传的就是这个数组,比如说我待会。在外面传进来这个宿主呢,诶长的样子就是这个样子的。就是哪个数据呢,就是这四个数据。这样我好比对好来了之后,我们先看第一件事情啊,他要找到这四个书里面最小的,我怎么做呢?你看我的思路,我先确定啊,我先确定这一个最小的索引假定。
04:07
Index等于零。这个没有问题吧,然后呢,Mini这个mini这个词呢,我们就叫index。也也就是说,我假定假定什么呢?假定最最,假定当前这一个最小数的索引就是零。就是这个数,但是实际上呢,呃,它不一定等于这个数是吧,但是我假定式,因此呢,我就这样写的零。看到没有,第一轮我们先把这个搞定,比如说我认为。啊。Index索引等于零,然后呢,它的值是mini mini也是它好,那这样。这样呢,就是说。我假定他是,但实际上他是不是呢,不知道。不知道好不知道,我就开始进行循环了,来我就循环了啊int解,等于什么呢?等于让这个我假丁的最小值跟后面的数进行比较,那也就是说我应该从哪开始比较呢?应该是从零加一开始比较。
05:16
大家明白我意思吧,比到哪个位置呢?比到认识后面,然后结加加。对不对。那也就是说我让这个最小数跟后面的下边为一的数比较,那这个时候我们来判断,如果说我假定的这个最小值它大于了谁呢?大于了这个结。说明什么?如果这个条件成立,说明什么?说明你说明我们假定的这个最小值并不是并不是最小的。那如果不是最小的是不是,我就把它重置一下。重置,那也就是说这个mini就应该等于多少呢?诶它就等于二,然后mini index应该等于说呢,等就等于大家知道我在做什么事情吗?就说。
06:09
就是重置最小值相当于说重置。重置什么呢?Mini这个字,这个也是重置什么呢?Mini index,我不知道大家理解我在做什么事情没有,就说我假定第一个第一个数下标为零的就是当前第一轮的最小数,但是它不一定是。于是我就从。D下边唯一的开始进行一个遍历,在变历过程中,如果我发现我这个假定的最小数还大于别人,说明你这个假定并不是对的,就重置一下就行了。那么我问同学们一个问题,当。当我这个for循环结束以后。当我这个for循环结束以后,是不是这个最小值和这一次的这一轮的第一轮啊,这个是第一轮。这是我们的第一轮。
07:01
第一轮。就说我们这第一轮是不是最小值和最小值的索引就找到了。是不是好,那如果是这样的话,我们是不是就应该进行一个交换呢?是不是就应该进行一个交换,那也就是说这个时候我们怎么办呢?就是相当于刚才说的是交换一下。这个时候就将什么呢?将这个最小值,最小值放在哪里呢?放在这个R0这个位置。是是这样子的吧,然后把什么呢?把这个R0的这个值放在哪里呢?放在呃,就是让这个让这个交换吧,咱们就简单说最小值放在里交换及交换。及交换是这意思吧,那现在这个代码应该怎么写呢?是不是?Or大家看啊,Or mini index。等于什么呢?等于我们的二位零。
08:04
什么意思?就是你经过你的一番查找,是不是你发现最小值的索引在这啊。那是不是应该把这个零,把零就是101放在这个位置去。然后把这个一放在这个位置来。那怎么做呢?是不是就是这样一句话啊,零等于mini。大家看这这这段代码能理解吗?这句话是什么意思?这句话是不是经过你上面一个扫扫描过后,我先问大家mini index是不是从这来看,是不是就等于三了。最小值也是一,那这样子的话,我就让这个202把这个2020不是101吗,放到这个位置来,然后把最小值,最小值实际上不是一记录下来吗?放在这个位零的这个位置。是不是又发生交换了,那我们输出看一下吧,同学们看好第一轮后,第一轮后注意啊,这些算法我原先讲过,其实我可以讲的很简单,我上来之后根本不做这些推导,我把代码一写就完了,但是很多同学其实是很难理解的。
09:17
明白吧,所以为什么老师要这样子一步一步推导过来,就是希望大家能够真正的理解。很多书上也好,网上也好,动不动就说彻底理解,其实你根本没有彻底理解,就只能越听越晕,所以说一定要把这个推导过程给大家讲明白,你们才能真正的理解好,至少我是这样认为的,那么呢,大家看点我们to把这一个oray放进去,同学们看,这个时候其实你拿到的。就应该是他了。因为你原原始的数组是这个,现在就应该变成了幺三。呃,11910,好,我们来测一下吧,我们来测一下啊,Select把这个放进去。
10:04
把这个饵放去,我们玩一把。同学们看。第一轮过后,是不是把这个一就放在最前面了,你原先是这个,我把我们把这个最先前也打出来。排序前。排序前这个数组它长的样子是a.tor然后把这个放进去。大家看他排序前是不是这样子的,后面经过我第一轮过后呢,怎么样,这个就发生变化了。那我们可以还有一种方法能够让大家理解,怎么办呢?你下一个下一个断点来学习,当我们不理解的时候,你们可以通过算法,通过下段的来玩,你看我再给他玩一把。Debug一下,这样看得更清晰了。这样看的更清晰了。好,同学们看,现在呢,我们断点执行到这里。现在mini现在看先看数组,现在数组是不是10101344和1191啊没有变化,好,现在接着往下走一步。
11:07
走一步,好,来,同学们看,此时此刻我设定的mini index是零,最小值是101,为什么呢?因为你假定第一个数就是最小的嘛,那么。你然后让让什么呢?让我们假定这个数跟后面这个一先比较,也就是说让1101跟谁比较呢?就是让我们这个假定这个101跟344比较。那么我们来看往下走,现在mini是多少?Mini是101而J,而节,这个节是一,其实34,因此mini大于它,它会进到这个IF1里面来。进到这里面来过后,大家有没有发现,当我这样执行完毕过后,Mini就已经发生变化了,看mini就mini index变成一,Mini值变成一,34,因为我刚才假定的101并不是最小的,所以它发生了一个重置。
12:02
那接着再继续往下走,下一次再走的时候,是不是我们这个最小值就34,再跟1119比,那这个时候这一次比较,显然这个if语句是不成立的,于是他直接跳过。是不是又到这来了,跳过这是不是现在呢,就要跟第三个一进行比较,那一进行比较的话,是不是这个MINI34又大于这个一,它又进到if里面来了。是不是又进来,然后把第三一个数就是A节现在是三了,交给mini,大家看这个时候mini等于几了?1MINI index是不是也也发生变换,Mini index就应该等于几呢?等于三。看是不是等于三了,这个这个时候他再进,他还想跟后面数进行比较,但是呢,其实已经比到最后了,是吧,比到最后你就不需要再比较了,于是整个就。退出来了。退出来过后,再把这个二零,这个二零现在不是已经是真正最小值了吗。
13:00
二零是多少呢?呃哦,不是不是啊,是把这个二零这个位置放在我们下标找到这个三,就相当于把101放在二三这个位置,然后呢,再把mini mini现在是一再付给这个零,就相当于发生了一个交换。是不是所以第一轮打出来过后呢,这个结果大家看现在就变成了什么呢?数据变成了1101,就这样过来的,好了,同学们关于这个分析我就讲到这儿啊,再说一遍,讲算法一定会有难度,如果你觉得难的地方呢,你只能多去理解好,第一轮讲完,那第二轮就比较简单了,第二轮你看老师就不啰嗦了啊,第二轮其实就在第一轮的基础上,咱稍微的修改一下代码就出来了,你看。如果是第二轮的话。啊,我把这个地方按了一个insert啊第二轮。如果是第二轮的话,我们这个mini index呢,就应该变成一了,因为你第120这个最小的已经确定下来了吗?这个改成它,改成它以后这个地方也要来做,然后下面这个地方是不是一加一,然后这个不需要改变,这边是一。
14:12
这边是一,所以说第二轮以后呢,同学们可以看到啊,第二轮以后这个得到的数组呢,就应该是这样子的。是不是这样子一个东西啊。大家看其实这个是没有发生变化,因为你第二轮的时候,这个34,其实它的的确确就是这一轮里面的最小值,大家看并行。大家看到没有,没有发生交换,这又出现一个新的问题了,大家看你在第二轮的时候,这个最假定的最小值还就刚好就是这三个数里面的最小值,因此你这个交换,你这两句话其实没有意义,发现没有。因为你在第二轮的时候,你假定的这个R1,它的的确确就是这一轮里面最小值,但是你却执行的这两句话,大家觉得有意义吗?没有意义,因此我们在做这个地方可以做一个优化,怎么优化呢?可以这样写。
15:08
可以这样写,我我们同样啊,这样可以先把这个写到这来,因为这两句话肯定是一样的,我就这样写,在交换的时候呢,我们要做一个判断。做一个什么样的判断,就是如果mini index。在上面啊,如果mini它不等于零,我们才去交换。对不对,是这个逻辑吧,那下面这个应该怎么写呢?诶下面也是一样的,就是如果mini index。它不等于几呢?不等于一,我们才去交换,因此你看第二轮我们其实是没有进到这里面来,因为你命index没有发生交换,Meaning inex就是等于一,所以它就不进来了,好,第三轮咱们就来了第三轮。第三轮呢,我把这个仍然进行一个处理。格式化一下,好,第三轮,第三轮是不是我们应该假定这个变成二了,这个变成二能理解我的意思吧,这个呢,变成二加一,下面不用改变这一方是不是应该改成二,大家看规律已经开始出来了。
16:12
规律已经开始出来了,然后这是第三轮,第三轮的话呢,这个数据就应该这两个发生交换,于是这个变成了101,这个变成119。我们再执行一下,同学们看第三轮。第三轮是不是在第二轮的基础上让119和101发生交换结束?结束好,既然在刚才分析的过程中,我们发现已经有这个规律了,是不是我们完全可以用一条语句搞定好在在在推导,推导的过程中,过程中。中我们过程中啊,我们已经我们发现了,发现了这个规律。规律,因此,因此,因此可以可以使用一个循环来解决。
17:06
是吧,嵌套一个循环就行了,来,同学们开始玩了啊。其实我就要这一个东西啊,其实我就要一轮的。对不对,把这个地方也拉过来,我把这个拿上来,注意听啊,我我先把下面这个注销。大家看我怎么把这三三个破循环嵌套起来。来走一个,那现在同学们看。这是一轮,这一轮其实我们就可以把它做一个循环,你看我开始写了啊。For循环开写。Int先写ii等于几呢?等于零,I小于多少呢?二。点Les减几减一,因为我整个轮一共是它的Les减一次,是不是I加加包起来包到哪里,包到这个位置。
18:00
是不是包到这个位置过后呢,我们整个把它格式化一下,格式化以后这个零应该改成解改成I。大家看到没有改成I,这个改成几改成I,那下面这个零是不是也改成I?是这样子的吧,那下面这个地方改成几也改成I,下面这个改成几是不是也改成I啊,没没有问题吧,因为你刚才已经推倒了,那这个第几轮过后,这个我们应该加上一个I加一,这样就看得很清晰了。For循环一次,代码写完了。也就是说原先写的这三个for循环,我们可以用。再外面再套一个循环,因此大家可以看到我们的这个选择排序,它的时间复杂度是多少呢?仍然也是一个这样的东西。是不是也是N的平方啊,N的平方。为什么是N的平方呢?因为它是一个嵌套负循环。
19:01
好,我们运行一下,看代码有没有问题,好,现在这个输出我们也可以再看一下啊,走运行同学们看是不是也是正确的。好,那既然如此,这个输出这里我就不要了,我就不要了,我直接上面写。好,我在这写一句话,System走,那么这边我们写一个排序后,排序后那么我们也把这个打出来看看对不对。看对不对啊,来玩儿一把。执行过后我们发现呢,排序前是这个,排序后是这个。我们把这个数据多来几个,看看能不能经得起考验,好,我就多写几个啊,然后呢,123,我们看这样排序过后是不是也是从小到大。没问题吧,没问题,那么我问同学们,假如我要把它改成从大到小,应该改哪里?应该改哪个地方?面试官如果这样问你的话,如果要把它写成从大到小,应该改哪里,是不是只需要把这个符号改成这个就可以了?
20:04
因为当mini啊,Mini小于这个舞台交换,那这样子一写是不是相当于整个就是从大到小排了,来试一下。是不是好,那我那我还改回去好不好,我还改回去。好,同学们,那这个就是我们选择排序的。呃,这是我们选择排序的整个一个推导和编写的一个过程,看看大家能不能听懂,还是那句话,同学们,还是那句话,就说我们去研究一个算法的时候呢,它本身是有难度的。你看现在选择排序还算是简单,后面咱们讲到快速排序,归并排序,还有这个希尔排序,它的难度就更大了,还有堆排序,因此你一定要有一个什么样的能力呢?或者说你要怎么去学这个东西呢?一定要把一个复杂的算法拆成简单的问题,再逐步解决,这样听起来会比较轻松,如果我上来直接写这这个for循环,两个for循环,我相信啊。
21:08
呃,至少有一部分同学是听不懂的。更别说理解了。是吧?好,那关于选择排序的代码的实现部分,我们先给同学们讲解到这里。
我来说两句