00:00
你把排选择排序的介绍说一说,选择式排序呢,它属于内部排序,什么叫内部排序?就说所谓内部排序就是把你的数据全部加载到内存。然后进行排序,当然有内存排序,也有外外外部排序了,就是你的数据特别大,你是加载不了。对吧,我们可以用规定这样把它并起来。那么是从这个预排序的数列中按指定的规则选出某一元素,经过和其他元素的重整。在一原则,原则就是你的规定,这个在一规定吧,比较原则了啊,比如说原则听起来很生硬,规定。这个规定就是从小到大还是从大到小啊,这个其实它这个规定,那么交换位置后达到排序的目的,那么我们来看一个这个思想,这个思想。大家一看就明白啊,选择排序是个简单排序法,它基本思想是这样子的,它基本思想是怎么样做的呢?来看一下D。
01:04
第一次他第一次做件事情,第一次从这个R0到RN减一中,就是从整个这个数组里边,大家看啊,整整个数组里面选一个最小值。他说整个速度选一个最小值,然后与R2,零交换。能理解什么意思吧,就是整个数字我先扫一遍看了,一个是最小的,跟R0交换,那二零一旦交换过R0就变成最小的了吗?紧接着呢,他又从后续的这个R1到R0,再再选一个最小跟R1交换,依次类推。是不是思想很简单呀?那写代码我们就要写一下了,那这个代码其实其实这样子的,我们看一个示意图就更好更好理解了,大家看在初始情况下,这有一个数据就是83217465。OK,那么它进行第一次处理过后,在当第一次处理的时候,是对这个数处理,你看它把整个这个扫描扫描你发现一是最小的。
02:06
这个一一旦最小,它第一次完了过后,这个一就排在最前面了,这个一和八进行交换。好,第二次呢,又对第二次操作的是这个数组。对,这个数组,在这个数组里面1V1已经定下来了,然后呢,他又从后面这个数据,后面这一堆数据找个最小的,他发现这个这个二,他发现哪个是最小的,二是最小的。对吧,二就跟三交换。以此类推,那么我们看一下一共进行几次大的这个循环处理啊,是不是七次?能看出来是七次吧,那为什么是七次呢?因为你八个数据,如果能确定七个位置是不是最后那个位置,必然是在适当的位置了。理解好这个思路非常的简单。但是呢,有时候我们写很容易把它搞晕,所以说这个时候大家注意,待会儿老师写代码的时候呢,你我的思路这样子的。
03:03
我们在写这个冒泡或者是排序的时候啊,你们当你们想不起来的时候,最好的方法是就先把第一次完成就硬写。写完了看第二次,再硬写一次,找到规律,用一个for循环一套就可以了。就说我们经常会忘掉这个代代码写,但是我我我们只要有方法也不会忘记好,是不是大家都清晰了吧,那现在老师开始写代码了啊。这代码你一听就能听懂。朱老师真的容易听懂吗?很容易听懂啊,我们这次讲讲的方法呢,换一个比较自然的方法给大家理解。好,我们现在来选一个object。注意听讲好,现在呢,我们是一个先先整一个数组呗。哦,这个数组,我这应该是有一个测试数据的,我把这个数据拿过来。各位。
04:00
VR我们先先整一个小叶数组,然后再整那个大数组啊各位同学。好,这个数据大家可以看到是一个没有顺序的,我故意整的是大小大小这样呢。这个效果看的很明显,OK,那现在我们先先来,那就不啰嗦了,咱们直接写方法吧,就是DF写个方法叫select sort。各位,你在进行这个S的时候。如果你直接写,有时候容易短路,就虽然我写出来,但是大家老感觉这个好像有点空,我我给大家看一下这个演变的过程啊。我们看一下。看一下这个这个序排序的排序的一个演变过程。演变过程很简单,那我们先做第一次。第一轮。第一轮第一轮。
05:01
排序。第一轮排序,根据他刚才的思想,是不是先对整个这个扫描。然后把第一个位置做出来,那第一轮扫描他是不是上来过后,他怎么怎么来写这个代码呢。他的思想可以这么做,他第一轮的目的其实就是要把这个东西大家都知道,他其实要把这个转成哪个,大家刚才已经理解了,其实他会找第一个的最小位置。那第一个位置,这个最小位置是不是一啊,那也就是说他第一轮做完了过后,应该变成这个德行。是变成这个样子的,好,那么我们就硬写,那怎么写呢?我上来过后先写一个最小值。我假定最小值就是A。零这个没有,这个大家能理解吧,我假定啊,那么紧接着最小值的下标是不是也就找到了是解。
06:00
没问题,好,是不是这就意味着我假定这个一是最小,但实际上不一定。所以说我就开始便利。这个时候的便利应该从哪里开始便利呢?同学们,那就这样写的。走,是不是从0ON til?UT,然后它是不是要把这个二位的大小写出来,也就是这个二位。点认识。对不对,我们待会看规律就出来了,那么在这个整个这个便利的过程中,我们就会是不是要对它进行一个比较。如果。如果你认为的这个最小值它还大于,当然这个这个不应该从零了,因为自己不用不需要跟自己比,看一下就分析出来了,你自己跟自己比有没有意义吗?是不是这个道理,说这个你可以节省一次,那如果你认为了这个最小值,它还比当前这个值大。
07:00
说明什么问题?说明你认为的最小值不是最小值,是这意思吧,这个能理解吗?就说就说,说明说明这个mini不是真正的真正啊真的啊,真的最小值。最小值OK,那这个时候你应该怎么做,是不是把这个mini改成这个就可以了。我知道不着急,我会记住这个下标啊,因为你mini你还要继续比吗?所以说mini肯定要改。是不是这个道理啊,同学们,那你就把这个改成这个这个最小值啊,当然为了好看,我为了待会我容易写呢,我先把它改成节,我为什么改成解呢?因为待会我要套的时候,外层有个有个I,这样我好看,明白我意思吧,这个变量不影响,然后这个为什么报错了呀,是不是因为我这写的是。V了,好,这个地方就就是调整。或者重重置。重置这个mini,然后把mini index。
08:02
就是你这个最小值下标是不是也应该是解。这个同学们看懂没有?好,整个遍历完了以后,请同学们回答老师,是不是这个命令就是真正的最小值了?而且这个mini index也是真正最小值的下标了,这个能理解吗?啊,同时重置。啊,就是这个就重置。重置什么呢?Mini index,好,下面是不是就现在相当于说在整个这个扫描过程中,你的最小值已经找到,下面找到是不是现在就可以就可以交换了,但是你交换之前是不是要判断有没有必要交换。为什么?因为假设你这个你走了狗屎运了,你假定这个最小值,它就是最小值,有没有这种可能性呢?有的,所以说判断一下。判断是否需要交换。说老师为什么要判断一下呢?你不判断一下,你不是有时候白白搞一把吗?所以你这样子又可以牺牲掉了if。
09:06
什么样?如果你的mini index,它不等于你写的这个零。因为你说明你改过一次吗。这个时候才有交换的意义,那怎么的,这个实验准确不是交换啊,其实就复制大,大家想我应该怎么做。是不是这个这个时候大家想到这个mini和index整,我先问大家一个问题,整个数组这个上有有改变没有。当我做到这个整个数组有变化没有,没有任何变化,实际上这个时候我们这个mini和mini index还保存起来了,所以说你上来过就直接这么干。把这个值直接付给他就行。为什么?所以老师我我把这个付给幺零,把这个地方写成了101 101,那个一怎么办呢?一是不是已经被你保存起来了。所以你不用担心说速度还是连交换都不需要,直接赋值覆盖速度更快,连交换都不需要。
10:05
这边有些有些代码里面一般写的是交换速度会降低。他没分析出来。所以你看我这个代码里面就就直接不用交换判断判断应该这样子判断是否。是否需要重置?需要重置。啊,他这叫交换就叫交换吧,哎,但是这个交换的含义啊,呃,不一样,那就这样写了,大家看能不能看懂啊,首先我把这个。我把这个A,哎,我们看看是要改变的哪一个啊,Mini好,Mini这个最小位置。这样写的大家看懂啊,Mini index等于什么呀?Are什么?零。是不是就是你这个零给他了,然后我们还要做一个什么动作,就是为零。等于什么mini完事了。
11:01
好同学们,我们这样做完以后呢,我们看看这个第一步,这个第一轮完了过后,这个结果是什么啊,第一轮这个只要规律出来,代码就特别好写了,第一轮第一轮结束。啊,第一轮。结束,那结束过后呢,我们把这个数组给大家打印出来看一下,就是呃点make。好,各位同学好,我们执行一下。当我们执行完毕过后,我们可以看到这个结果跟我想的一样好,第一轮已经搞定了,那我们看规律了啊,第一轮搞定以后,我们来看第二轮。就这样子规律,就就说你们以后用这种方法呢,就可以解决很多简单问题,第二轮实际上是在这个基础上。在这个基础上找到,找到后面这个的。这里面的最小值是不是。
12:00
好,其实你这个地方呢,因为34刚好就最小值,所以说这个地方改变完了过后还是它。那老师那这个就不用跳过去就行了嘛,不,你不能这么说啊,你说跳过去,那你不比较,你可不知道344最小的对吧,说的没办法说你这帮人还得按刚才那样玩一把,看规律。现在我们把这个mini又制成几了,做成一,这个是不是改成一啊,这个是不是也改成一,然后这个地方的是是不是相当于。在原先这个基础上加了一个,就是从你的,这就是在你原先的,就是说在你这个指定的这个坐标上加一。是是这意思吧。这个大家要理解,然后下面这个代码不用变化。这个地方要改成几,是不是改成一啊,这个地方也改成一,这个地方也改成,大家看规律其实已经出来了,也说这个一只要做成一个循环变量代码就OK,第二轮我不看结果。第二轮其实连这个动作都没有做。
13:00
因为它必要完了过三四次仍然是第一个位置,所以说第二轮完了过后,你们发现代码呢,OK,你看。代码是不是还是他好,第三轮我们只需要最后一轮,因为我设计三个数据是有道理的,三轮大家应该还不觉得烦啊,所以再再做一下,大家觉得就意义不大了,我们改成第三轮,第三轮是不是在这个基础上各位同学。是不是又要开始找了?那这个时候是不是前两个数已经被你搞定了,是不是就在最后面的再去找最小值,其实同学们看一看出来,这个时候就是这两个数进交换。这是你肉眼观察到的啊,那就是。幺零这边是改成11119,看清楚没有,那同样这边是变成二。你看这个规律啊,二同样是不是这个也是这个二加一。啊,其实前面这个前面如果这个写的好的话啊,应该是呃。
14:00
诶,刚才那个。从这开始,这个其实相当于是零加一,这样理解,就在原先这个基础上加一。这样就把这个规律就看出来了,就是在原先你设定这个坐标上加一,这边是一加一,这边就应该是二加一了。对不对,好,然后这个地方换成二,这方也换成二。这个地方仍然换成二。好,我们这个什么呀,我们这个第三轮结束代码。再跑一下。看第三轮结束以后,我们发现这个已经是一个。有虚的了,好,那我们发现这1123这个其实代码非常像,没有必要写这么麻烦,于是我直接用一个循环套下。好,我们发现规律了,发现规律。我们发现这个规律。啊。规律好,那么这个时候我不要这些代码了,我整体将它注销。
15:04
整体将他注销,诶这个注销到哪儿啊。谁在这是吧主角这那么我怎么怎么来处理呢?我只需要把第一轮这段代码拿过来。大家看啊,我把整个这个代码从这开始拿到上面去。然后上面去我们来看。整个这段代码,我用一个for循环包起来。我一共要进行几次的这个这个循环呢?按T是不是就应该是我们这个数组点N减一规律出来了吧,然后我们只需要把这段代码包起来。理解,然后这个地方是不是就改成I就可以了,各位同学。改成I。下面这个地方是不是也要改成I呀,是不是也是改成I加一。是不是这个意思,那下面这个就改成解,改成I,这样理解起来是不是。
16:02
很简洁了。老师,这个还真是有点是吧,如果我硬讲的话,虽然我也能讲通。但是呢?对不对,大家觉得很难受,然后我这边。个Dollar Dollar去了Dollar I。加一是不是要加一,好各位同学一个for循环是吧,这就是。选择排序,那我们执行一下过后,我们发现代码呢。仍然跟我们一样。没有没有问题吧,代码写完,那因为我们在实际做的过程中,不会把它单独写到这,因此把整个这段代码整个卡走。放到哪里去呢?放到我们这个代码里面就完事了。然后同学们这边是不是要给我传一个数据,数组过来就可以了,R里面的类型是int,代码搞定。那这个时候你就不需要这样用了,你在做的时候就只需要这样干,就是select short把扔进去,那扔进去过后呢,这边我们也不输出了,没有意义啊,因为我们原先只是为了。
17:07
做测试嘛,看这个流程,然后这个地方我们把最后结果打出来看一下就可以了,各位好,排序后。排序后我们执行一下刚才老师写的这个代码make,看结果对不对。好,跑一下。好的好,各位同学看一下我们这个结果呢,仍然是正确的,代码就是这样一步一步演变过来的,也就说只要你在写代码时候,你只要记住一个根本的原则,就是那个是怎么玩的,代码就能写出来,但是如果让你们印记这个。还是有点麻烦,所以说我们有时候写代码,大家要记住一个一一个特点,就是说有可能是先写到里边再套一下。就好像我们在写递归的时候,有可能是先把里面写完了,再再写外面。好,那这样子的话呢,我们就来比较它的效率了。
18:01
Select这个效率我们来分析一下,它的确很很有意思,你看它它交换的时候,其实它在每你你们有没有发现这个select第一个他在每一次进行这个找出小值的时候,其实它的这个维度在降低,就是越来越小,越来越小。而且。而且大家看到它几乎没有这个交换值是负值,说这个速度呢,你只要一想,人家这个想法肯定是冒泡快很多,那到底能快多少?各位我们就来测一下它的效率啊,因为我没有讲数字分析,所以说我也不去说具体东西,我们就看速度,就拿一个硬东西来直接测。那刚才我们有一个八,我直接来把这个搞出来啊,来各位同学这段代码。但到到底你可以中断那个函数,我把这个注销了。同样我们登进去同学们看,现在呢,我这里这个二一共有啊8万个数据,8万个数据好排序。
19:04
这个是排序啊,就是调用。调用我们的选择排序,那么调用选择排序过后,这个我就不输出来了,因为8万的数据你你受不了啊,8万数据这个一打时间太太长了,那下面呢,我再把排序后的时间打出来。排序后的时间。是这里各位同学。就这里。好的,我在select里面,我打一顿代码。一个大家看确实调用了,而且这个方法我们测试是没问题的,一个是排序前的时间,一个是排序后的时间,大家觉得。能花多少时间呢?快多少呢?好,我们看一下啊,原先那个是13秒,我们看看选择排序会不会快一点。跑起来。有人说更慢是吧,那不可能。诶,你看我们一共用了几秒三秒。
20:00
而你原先是13秒,我三秒肯定快了很多吧,而且呃,随理论上说,你这个数据越大,它那个这个这个它那个。这个时间更节省对不对,所以明显感觉到时间确实是快了很多,那么我们再运行一下,看看稳不稳定啊,应该大致就是三秒。那还是很稳定的。啊,这个又慢了一点,可能这次呢,它产生这个产生这个。所以移速啊,可能大概三秒四秒的样子哈。是不是又又三秒,大致在三秒,那个是13秒,好同学们,那关于这个选择排序呢,老师就讲到这里,我们把这个选择排序给大家阐述一下。来走一个选择排序。好,我们把选择排序。给大家搂一圈儿。好,现在讲的是选择排序。好,这个地方我们是写到哪里了啊啊,就是排序的内容。
21:00
好,我们来把这个排序整理一下。那排序我讲的是什么呢?来搂一下。排序首先我说了一下我们要讲的排序有哪些。就我们要讲这么几种排序。对,排序呢,我先做了一个基本介绍对吧?诶,然后呢,我说我们要讲五种排序,这五种排序呢,呃,是要求同学们掌握的,尤其是前面这三种啊,最常用快速排序,并柜排序,至少你能看懂对吧?这是最低的要求。并理解你的思路。在这里,我们把这个冒泡排序做了一个回顾。哦,猫排序,因为毕竟是一个整体嘛,所以说我还是回顾了一下。做了一个回顾。好,把这面代码稍微的整理一下。好,然后这个冒泡排序,因为前面老师讲过了,我这里就没有多说。别多说,然后把他的一个呃冒泡排序的呃一个代码给大家跑了一下代码我就直接拿过来了啊同学们。
22:07
就是冒泡排序的代码。我放在这了,因为这是干拉型的嘛,同学们可以看一下。诶,我在这儿写到这儿冒泡。冒泡排序的代码。代OK包法排序代码呢,我标成一个箭头。啊,标出一个箭头。好,把代码给大家扔过来。这是我们冒泡排序的代码,冒泡排序完了过后,我们就讲了这个选选择排序,我先对选择排序做了一个基本介绍。OK,那首先我们看一下他的一个思路是什么样的,选择排序,选择排序他的思想一定要搞清楚。好,这是选择排序的思路,怎么做的呢?他其实是这样子的,第一次,第二次,第三次,以此类推。
23:00
啊,这样子的说,它是第一次从整个数字里面最小进行交换,第二次再找,依此类推,最后得到一个有序码。那么选择排序做完了过后,我们就给大家这还有一个思路图也给大家粘过来啊,这是选择排序的一个思路图拿过来。然后下面就是我们代码实现了,下面呢,我们写个代码实现啊,这就。这个代码实现。选择啊,就叫代码实现啊。选择排序的代码。代码实现。选择排序代码实现。那么我把这个代码呢,给大家放过来。Select没写错啊。OK。那截取。
我来说两句