00:00
下面呢,我们来讲第二一种排序算法。选择排序。那首先我们看一下选择排序的基本介绍,选择排序呢,它也属于内部排序。呃,是从预排序的数组中,按照指定的规则。选出某一个元素,然然后再依照规规定呢交换位置,达到排序的目的。那我们来看一个它的排序思想,它的排序思想呢,是这个样子的啊,同学们看。它的基本思想是这样子的。第一次先从。一个数组中,这个数组是从零到N减一,也就是从从从整个数组里面选取一个最小的这个数,然后呢,从跟跟这个二零交换,也就是说。他在找最小数的这个过程中并不发生交换。只是在。
01:01
只是在什么呢?只是在找到最小值的时候发生发生交换,不是说每次都交换,明白我的意思吧。哎,这点大家请注意一下。那么第二次呢?再从一到N减一中选取最小值,也就是说先把第一个最小值,第一个最小的先确定下来再去。选选第二一个最小的跟一进行交换,以此类推。以此类推,那么最后呢,他会得到一个按排序嘛,从小到大的一个有序序列,当然前提是咱们是要按从小到大排序,如果你是从大到小的话,那这个找最小就应该变成找最大就可以了,明白我的意思吧,那么这边还有一个图解,我们来看一下。这里面有一个选择排序的思路分析图,我们针对这个图呢再聊一聊,说目前有一个原始的数组是83217465。一共有八个数据,那么他第一次呢?这是它的初始状态,他第一次排序。
02:06
他从这个数组里面找到一个最小的,最小的那是一,一跟八交换就得到了这个数组。也就是说,第一次。第一次这个进行,第一次进行这个循环过后呢,会拿到一个最小的值放在这个位置了。然后呢,第二次就从后面的这七个数里面找最小的。然后这里面最小的应该是二,于是呢又又把第二一个数排在最小的排在这个地方,然后第三次的时候,从后面的六个数里面再找一个最小的进交换,这六个数里面最小的是三,于是呢,他又把这个三确定下来,然后在第四次又从。剩下的五个数里面找一个最小的,是几呢?是四,又拿到了第五一次是从后面的这个数里面,四个数里面找一个最小的,显然是五,又把五拿下来,然后第六一次从剩余的三个数里面找最小的,是几呢?是六,又把六确定下来,第七次从剩余的两个数里面找最小的。
03:16
但是七又确定下来,那第八次有没有必要呢?没必要了,为什么?因为你一共有八个数据,我已经确定了七个数,那最后这个数一定是在它。准确的位置,明白我的意思吧,好了,现在这个图呢,大家看清楚了,过后我们以另外一个比较简单的数组再说一遍,因为待会儿呢,我们在写代码的时候是按这一个数组来演示的,这样咱们可以去对比一下。好,现在呢,我们再来画一个图,叫做选择排序,选择排序的一个思路图解。选择排序的一个思路图解,好,同学们看我们,我们假定呢,这儿有一个初始数组。
04:05
就是原始数组啊,原始的。原始的数组呢,是这个样子的。那么我们第一次第一轮第一啊,注意听第一轮第一轮。第一轮排序我们会干什么呢?从这个四个数里面找一个最小的数交换,当然你你第一轮里面这个最小的数显然是一。这个没问题吧,那么这个一呢,就会跟。这个二零交换,也就是说第一轮做完了过后,其实这个数组就变成这个样子了。大家注意听哈,就变成101了,也就是说第一轮整个这个排序完了过后呢,他把这个最小的数据就放在了它应该的位置。那么至于这个第一轮,它是怎么进行这个循环来找到的,待会我们在代码里面再去说好,那第二轮第二一轮排序呢,大家看第二一轮排序它干什么呢?诶,它是从后面的这三个数里面再找一个最小的,再找最小的是34 34呢不动,所以说第二轮其实。
05:19
嗯,他没有真正的发生一个交换,为什么呢?因为34就是后面这三个数里面最小的。是不是好第三轮。第三轮排序,第三轮排序呢,大家看到啊,第三轮排呢,其实是从后面这两个书里面找一个最小的,显然101:119更小。所以说这个时候呢,它会发生一个交换,就把101和119进行交换,那也就是说第三轮完了过后,就把前面三个最小的数确定下来了,那第四轮还有没有了,没有了。因为我们一共四个数据,其实一共经过三轮排序就可以了,那么这里我要做一点说明。
06:03
说明啊,第一点就是我们从这里可以看得到呢,就是选择排序。选择排序一共有几大?有几轮几轮这个排序呢?一共有这个数组的,注意听啊,数大小减一次减一轮排序,那么每一轮排序里面其实是又是一个小循环。对不对,那第二点我们要说每一轮每一轮。每一轮排序呢,又是。啊,又是一个循环,又是啊又又是一个循环,是这意思吧,那么这个循环的规则是什么呢?它循环的规则大致是这样子的啊,后面我们代码里面还要说,代码还会说,那么现在我简单说一下,每一轮循环的规规则是这样子,它是先假定他这样子的啊先。
07:03
先假定,假定当前,当前这个数是最小的,最小的数。就假定当前数这个最小的数,然后呢,依次比较啊,然后和后面的每个数每个数进行比较。比你进行这个比较,如果发现,如果发现。如果发现什么呢?如果发现有一个比它更小的,如果发现有比它小的,比比它比这个当前数啊,当前数更小。更。更小的更小的数就干什么呢?就重新就重新重新确定确定最小数。最小数。并得到并得到这个下标。
08:03
然后当它整个这个呃变历到最后这个数过后呢,就找到了这一轮的最小数,当便利到数组的最后,数组的最后最后时干什么呢?就得到了本轮,得到本轮,注意听这句话啊,本轮最小数和下标。最小数和加标,那么第四点呢,再看一下,然后就交换。交换就可以了。大致就是这么一个逻辑,那么我这样讲呢,可能同学们听的有点蒙圈,也不知道老师在说什么,那么待会儿呢,我们代码中,从这个代码来看就更容易了,讲代码的时候呢,我们也是怎么样呢,这个用这个逐步推导的方法来讲,大家就容易理解好了。大体。这个排序算法的思路我们就说到这儿。大家。
09:00
大致应该有个了解对吧,虽然说我这讲完了过后,大家可能还是不太明白,因为排序算排序算法肯定他本身就比较绕,如果不明白呢,待会我在代码中再再继续讲解啊,再继续说。继续说。好,那关于排序算法的这么一个思路。这么一个思路,就先给同学们讲到这儿,一会儿呢,我们用代码再给他走一圈,加深印象。
我来说两句