00:00
好,那么接着的话呢,咱们来看下边这个需求啊,这呢是算法当中涉及到数据的一个检索的,或者说呢,叫查找都行啊,那么对应的这个典型的这个查找方式的话呢,这呢我列了两个,第一个呢叫线性查找,第二呢叫二分法查找。啊,线性查找呢,其实也非常简单啊,比如说我们现在定义好这样的一个in特型的数组,哎,我只是以in特型为例啊,你可以呢,是一个string类型,以后呢,我们讲完面向对象之后呢,你还可以呢,是一个具体的对象构成的数组啊,就是对象数组了,想找某一个指定的对象啊都可以啊。好,那我们以in的数组为例,说呢,数组元素啊都放这儿了,所以现在呢,我想找一下五这个元素呢存不存在。那如果要存在的话,你告诉我五这个元素呢,存在于这个数组的索引的哪个位置?返回给我是吧,哎,如果呢,要不存在的话呢,你告诉我说就不存在了,那就可以。啊,未查询到结果啊,就行了啊。好,那么关于这个能查到这个事儿的话呢,其实在具体实际问题当中啊,这个表现形式。这个挺多的啊,一种的话就是你告诉我首次出现的缩音是吧,有的时候还有需求,就是你把所有的都告诉我。
01:06
啊这块呢,咱们就只找到首次出现了就行了,首次出现或者大家你再接着后边去便利把每一个都找到,其实也都类似的需求啊,都可以去做了。好,那么这样的话呢,咱们首先看一看这个叫线性查找的问题。哎,我们去新建一个Java程序,哎,这个线性的话呢,叫做linear啊。呃,关于他的一个search吧。哎,它的一个测试啊,这个名字的话呢,大家如果英语呢,确实稍微弱一点,一开始呢,不用特别纠结于这个词哈。啊,你渐进式的一点点去记啊,更关键点还是看这个代码层面啊,能不能写出来啊。好,那么这呢,我们首先呢,把这个呃,数组呢,已经定义好了,它现在希望我们要找的是这个元素五啊,所以这块我们来定一个啊,嗯,叫它哎target。啊,它给的就目标的这样的一个元素哈,这个值呢是五,呃,相当于呢,我们要找这个五是否存在于这个数组当中啊,那么最简单的或者我们最容易想到的一种思路呢,叫做哎,线性查找。
02:11
嗯,先行查找。那其实就是我们便利一下呗。所以说咱们这块哈,大家你想一想,刚才呢,咱们也做了好多这个题目了,其实你细想一下的话呢,基本上都没有逃出咱们一开始讲到的数组一开始使用当中的这咱们讲了六个基本点。都在这六个基本点里边呢,只是呢,具体问题的话呢,这样便利那样便利,比如你复制一下呀,反转一下,其实好多是不是都涉及到跟便利相关是吧。对,所以这块呢,还是这几个点,大家你得先得能拿下,现在呢,让做具体问题,你连数组的定义都定义不了,那那都白扯了。后边什么也做不了。啊,所以这呢,都是基本的点了啊。好,那么这个线性家长呢,其实就是一个便利啊,便利的时候呢,你看指定位置元素呢,谁跟他一样,只要一样了,我们就诶。停下来说找到了,然后都走完了以后,发现也没有找到,那就是没找着。
03:00
所以这块我们就for循环啊。E那个I呢等于零,I呢就小于A1.lengths啊I呢再加一下。好,接着的话呢,我们在里边呢,去做这个判断啊呢,这个我们要找的呢,是这个target,然后呢,如果它跟我们某一个元素相等了,诶这是不是就找到了。所以这时候我们就直接输出啊,说找到了啊指定哎,或者叫找到了,我们就这样吧,Target。哎,找到了这个target,然后再连接一下。逗号是吧,然后对应的位置为。或者叫索引为啊,加上这个I这就可以了。哎,这里边儿我们提到说一旦找到了,我就停下来,我就不找了。哎,那这时候我们就直接来一个啊。哎,这呢都还挺顺的啊,哎,那么问题是如果要没找到呢,你告诉我说没找到。几个小时?说未找到。行不?
04:00
这个就有点儿不太对了,你看一下。就成这样了。没找到没找,哎找着了是吧,这不行啊。这个未了化指的就是我们最终你要是没找到,就告诉我没找到。这个怎么刻画?插个旗是吧,嗯,插个旗可以。查钱怎么查?提前先定义好一个变量是吧。说布尔类型的啊,Is flag。哎,这个想法的话呢,其实挺好的哈,哎,这种思想呢,在我们很多编程当中都可以有所体现。这呢整了个小旗子是吧,说你一旦找到了我,是不是这块记录一下。啊,或者这块你写个出啊false啊,这个值默认值是多少,其实都还好啊。这个呢,我改成false。改成for以后呢,然后呢,这块一旦找到我们就break了,我们看一下除了for循环以后,你是不是当初进去过。进去过说明就找到了啊,进没进去就拿它判断了,说if,如果is flag。哎,我这儿呢,就直接写的他哈,因为我一开始这个值是出了,我现在判断你是不是出了。
05:04
你处。说明。没进去过是吧,那说明没找到,哎,那我这块呢,直接就输出也说未找到是不是就行。哎,不好意思啊,没有找到次元素,诶是不是就可以了。来。做一个软。诶,你看这时候这就找到了啊,那如果这个位置我们比如说改成一个15啊没有。转一下。但真的就是没找到。是吧,那就这样啊,行,我这样啊,咱们把这个target给他。哎,这个呢,重新复制为15啊,大家呢,去体会一下两种不同的情况啊。那么这两个这个问题的话呢,我们细着如果再去说一下的话呢,哈,我说呀,其实也可以考虑不去定义这个布尔类型的变量。那这呢,就涉及到我们针对这种循环,咱们再细着去剖析一下啊,你想我们一个循环结构的结束呢。或者说循环结构的结束呢,我们提到过有两种方式。一种呢,就是你这个循环条件不满足了。一种呢,就是里边有break是吧。
06:01
那这个题目的话呢,其实是说什么呀,如果你是靠break结束的。说明你是找到了。如果你要是靠这个循环条件结束的。说明就是没找到是吧。哎,你说如果是这个意思的话呢,嗯,其实这块也算是一个小的一个方式的啊,小的方式怎么办呢?我把这个结构啊,我CTRLC咱们先拿过来啊,去分析一下啊,然我写成一个方式二吧。其实差别不大啊。哎,方式一啊。把这个呢打开。嗯,这个呢,不要了啊,CTRLY一下啊好怎么着呢,就是说我出了一个for循环以后呢,我判断一下你是通过break结束的呢,你还是通过这个循环条件结束的呢?如果是循环条件结束的,那就意味着你就是没找到。那就相当于我们这时候去判断一下,说你这个I呢,你是否等等于,哎,最终这个I呢,我们还做过加加,其实最后呢,就是等于它吧。等于它的时候呢,这说明就是到头了嘛。
07:01
对,那当然这个I呢,是在这定义的是吧,出了这不就看不见了吗?那只需要做一个小操作啊,你把这个位置呢,给它拿出来是吧。这就行了,哎,只不过一般呢,我们习惯上把它写到里边拿到外边,这种更多的像一个well一样是吧。OK啊,那你也可以把这个你觉得不好看,你改成well,然后加是不是里边。也可以啊行,那如果呢,你是这样的一种场景,我就说没找到。CTRLCCTRLV保存是不是。也可以是吧,你看我们这种人做一个run啊,这是五找到了,然后呢,把这个打开,这就是没找到。看这就行啊好,这个呢,就是我们去稍微的体会了一下这个关于循环的这样一个特征啊OK,哎,用这种方式的话呢,也比较直接,但是你要想到我们具有这样一个变量的定义。行,那么关于线性查找呢,咱们就说完了,下边的话呢,我们来看下,这个叫二分法查找啊。这个大家大学也好,或者接触一些数学的一些计算也好呢,经翅有这种二分法的一个计算是吧。
08:06
有同学没听说过啊,这个接入过统计的话呢,可能学过这个牛顿二分法。一会儿咱们再说那个事儿啊,咱们先看这个什么叫二分法啊。哎,说现在呢,你看有一个数组,呃,说现在我也想找某个元素,说呢,除了这种线性查找之外的话呢,我们说还有其他的方式。哎,这个方式的话呢,比上面这个效率更高啊,这个呢叫做二分法长征。但是这个二分法长长,它有一个前提条件哈。哎,你看我们这个数组,我放在这儿的时候呢,它是一个有序的是吧。哎,这是一个最基本的条件了啊,基于这个有序,我们才能够使用二分法。啊,他的想法呢,哎,咱们看一看这个课件啊。哎,想法我们先这儿呢,举了一个例子,哎,这儿呢,你看就是一个有序的,不妨呢,就是生序的。说我现在想找某个元素,这个元素呢怎么办呢,我先跟这个数组中,中间这个元素呢比一下。
09:04
哎,发现呢,比中间的元素呢。大大,我是不是因为你有序嘛,比它大,我就只能说啊,你这个要找元素就一定在右边左边那就不要了。所以呢,相当于我们比一次之后呢,是不是就砍掉一半。对好,我就接着从右边找啊,然后在右边呢,这五个元素里边呢,我再找中间这个元素。发音呢,我要找的元素呢,比你这个元素小。那我就把右边的这块又砍了。又砍掉一半,那接着就还剩哎左边了,这块就剩他俩了,它俩的话呢,这个你再看一下这个它俩你要是一加,所以你再一除,其实诶可能就等于它了是吧,然后你再看跟它呢,是相等啊,还是比它大呀,比它小啊,这块其实就已经出来了。所以这块你发现的这个速度,我们每比一次,直接呢,它的元素呢,就砍掉一半。这个效率呢,就大跨步的把这个原有的速度元素就降低了,所以它的性能显然是更高一些的。
10:00
啊,那如果大家呢,你要是之前接触过数据结构的话啊,第一种我们叫做线性查找,或者叫顺序查找,它的复杂度呢。是不是你便利了整个所有元素了是吧?哎,它是on的。哎,那么他呢?对,这个就是以二为底,N的对数是吧,啊烙文。这个呢,就以二为DN的对数了啊。哎,这个怎么来看呢?就是你嗯嗯怎么来说,你看每次它相当于减一半减一半,你要这块逆着来看,每次相当于加一半加一倍是吧,每次加一倍是不是就二点指数次幂。你到这来看的话,就是它的反函数。二的N次方的反函数不就是LOG2N吗?哎,所以呢,它的效率呢,性能就是烙杆。啊,1VN的对数啊,那这个性能呢就要好很多。OK啊,哎,这个呢,如果用我们这个整个实现的逻辑来看,这就是我们代码上的一个实现,这个咱们等着再说哈,我再举个生活中的例子啊,你比如说现在。一个除夕夜是吧,这呢是整个这个小村庄啊,这个大家呢,灯火通明啊,都在看这个。
11:04
春晚的是吧。啊,这个中央一的也好,还有网络充满也好,是吧,OK啊,哎,那现在呢,这个是供电厂啊,这个供电厂的话呢,这不是把这个电呢,都输送到这个村子里了。突然现在停电了。哎,那这时候我们就排查出哪个位置呢,这个烧了是吧?啊,可能这个用电量比较大了啊,那这时候呢,我们想快速的排查出哪块有问题。啊,那么推荐的话呢,是不是也是二分的一个排查。哎,你说我这就有好多这个,咱们叫这个电线杆一样是吧。啊,你要有好多的话呢,这个可能上百个啊,这个你要一个一个这样排查,天都亮了啊。哎,所以这块我们直接呢,就定位到中间啊,我先看呢,从电场开始,哎,到你中间这个位置,看这段有没有电,如果这段要是有电。那就说明这块有问题。哎,那就这块有问题了,好,这块有问题的话呢,我们还是找到中间,然后看看是是从一开始到这块啊,就是说白了,就这块儿有没有电啊,这块要有电,OK,那就这块有问题。
12:01
每次排查一次呢,整个这个就相当于是减少一半的距离,那很快的话呢,我们就能够找到哪块出问题了。哎,比你一个一个的这样去排查,这个要靠谱的多。啊,这个呢,其实也是使用了类似于这种二分查找的这样一种思想啊。好,那么刚才呢,是我们说的这个,呃,这个形象点去理解哈,说我们怎么看待这个代码的一个实现了,那具体这个步骤怎么去做呢。哎,你看这样子的哈,那呢,首先呢,我们定义一下这个数组的这个索引啊,害的呢是零就是首索引,N呢,就是我们这个尾索引。哎,手缩引萎缩引啊,怎么办呢?我们找到它的一半,就是中间的这个索引。啊,这呢是我们这个循环的条件了,啊,这个循环条件呢,就是这个had呢,小于等于N的。啊,就是你这两个呢,不能够交换了。交换了就得终止了,OK。行,注意这个等号呢,不能丢。哎,等号不能丢,需要判断它俩,万一要相等的时候呢,这个元素是没有判断过的啊,记着也得比一下好,那么就取你中间这个索引,然后中间这个索引呢,我们看一看啊说诶正好要找到这个Y,恰好就是你这个索引值了。
13:09
那就找到了。那就结束了。呃,那要不的话呢,就是发现这个Y呢,大于你要找,呃,就是你现在给的中间这个。那我是不是就得从右边找啊。在右边找的话呢,你就接着就相当于让你这个had呢,是不是修改左边界,让它等于me加个一是吧。对的啊,然后呢,你要是发现这个Y小于这个中间这个值,说明我们在中间这个值的左边呢,那就让你这个N的呢,就是往前移,移到你这个mid的呢,减一的这个索引位置。然后接着的话呢,再回过去看一下满不满足这个关系式,如果满足接着再去找,如果这时候不满足了,那就说明已经结束了,说明没找到。看看能不能捋清楚这个逻辑。OK啊行,那下边的话呢,咱们找这个直径元素的时候呢,咱们就按照这样的一个思路呢来了,首先啊,把这个速度呢,已经定义好了。
14:04
哎,咱们写到这儿是吧。哎,又建新建一个渣程序,这个呢,叫bary的一个search。哎,它的一个test啊。哎,这样。好,这个速度呢,已经有了,然后呢,这个目标的啊,Target咱们要找的。啊,还是五。哎,我把五呢就放这了。好,诶按照这个思路来啊,刚才提到这个事儿啊,诶首先的话呢,我们得把这个索引啊,默认的这个值呢,给它定义出来,害呢是零,这呢就是默认的首索引。嗯,手缩引好,然后呢,再定一个N啊,这个呢,我们是ar.les呢减个一,哎,这个视角。哎,默认的这个萎缩引。好了,然后呢,这个循环条件呢,就是让这个head呢,它俩不能够交换了位置了啊,所以呢,Had得小于等于这个N。
15:05
在这种场景下呢,我们接着呢,首先啊,计算出来它俩中间的这个值。Had,加上这个end。除一个二啊,有的人除不尽怎么办呢?那就把那个点几截断就行了。啊,这个我们叫middle也好,叫middle也好啊,就中间值的意思,中间的这个索引啊,然后下边我们重点是要判断一下啊,你要找的这个target呢。哎,看看如果要是等于了,哎,我们这个AR这个密这个这个middle是吧。A2啊。Middle。这个位置大家看好啊,千万别写错,你你就写成个middle,那麻烦了啊。这个咱们密度呢,指的是中间的这个索引是吧?哎,你是要找这个索引位置上这个值的啊,哎,这个一定要注意。哎,这么着,那这个呢,就意味着我们找到了啊。所以这块我们就其实就结束了说找到了,哎,咱们这个target。
16:00
啊。然后逗号哎对应的位置为,哎,加上咱们这个谁呀。Middle就行是吧,哎,那一旦你找到了,是不是就结束就行。OK啊,好,然后else if。呃,如果呢,你发现呢,你这个所谓的target,你要找的话,大于了我们这个值。那说明我得去右边找是吧,那你需要呢,把这个指针是不是就直接调过去,左边这个调过去是吧,让它就等于M呢。加个一。加一就行了。好,然后呢,加完一之后呢,你接着再判断它,如果满足这个关系式,再去找这两个现有的这两个所引的这个中间的位置就行了,好再来个else啊哎,那就相当于是这个target呢,就是小于这个值的这个场景了。哎,我就注释一下啊这样。好,那么小A这个场景的话呢,就说明你这个target呢,应该是在它的左边了啊,所以呢,这是我们就让这个end是吧。那它呢,就复制为这个米减个一。
17:02
得往前调一次。啊,就像刚才我们这个图里边就是,呃,相当于呢,比如我们这个找在右边呢,就是这个target呢,是大于我们这个值的,所以说我们这个让这个head呢,就接着等于这个位置了,所以要是小于的话呢,我们让这个N呢,就等于这个位置了。这个位置是吧,不是等于这个值啊。好,这呢,就是我们说的这样一个思路,然后呢,诶判断完以后,我们接着再回过去。走这个结构啊,依次呢,再往下顺就行了,好,那如果你要找到的话呢,那没问题啊,确实是找到了就结束了,那如果要是没找到,你告诉我说没找到。咋办?告诉我没找到。哎,又得想这个事儿了,没找到呢,是不是说这种关系是不满足了。哎,不是靠这个结束的循环是吧,而是靠这个结束循环,那就相当于我们这个N呢,它会小于这个head了。哎,这就属于没找到场景,或者的话呢,还是跟咱们上道题一样啊,我是不是也定一个。
18:03
Flag是吧,哎,布尔类型的啊叫is flag这个呢,我也写成true啊,用它呢来去判断。哎,是否找到了这个指定元素是吧。如果这块我写的时候是否找到了的话呢,那这个咱们先写成个false吧。哎,那就是默认先没找到是吧,哎,这个呢,你一定要找到了,在这个位置呢,我们是不是给它赋个值。啊,Is flag这个我改成是个出吧,这就相当于找到了呗。好,那么这块呢,出去以后我就看一下你这个flag这个值了。哎,这个flag这值呢,如果你要处说明你找到了啊,我们现在想判断没找到。非是吧,就说明你还是原来的这个force啊,在这种场景下的场景下的话呢,就是没找到啊,不好意思啊。哎,未找到,哎这个元素。哎,这就。可以了啊。来,我们右键run一下。哎,这个呢是咱们找到了啊,所以呢是二啊,那正好是这个位置了,哎,那这个咱们也可以啊target。
19:03
那这个呢,改成这个,比如说十,诶啊15有哈,十十七吧。嗯,来右键run一下。那这种感觉没有找到。哎,就可以了啊行,这个呢,就是我们说的这个叫二分查找,哎,这样的一个思想啊,好,那么回到我们这块啊,咱们看看这是呢,是具体这个操作了,然后回到这个算法层面啊,这块我们稍微说两句哈,第一个呢,叫扩容与缩容,刚才已经讲过了啊,下边呢,我们讲的是这个查找,查找呢有啊顺序查找和二分查找两种方式,来我们看看各自的优缺点啊。哎,首先说这个顺序查找这个优点是啥呢。嗯,就是这个算法也比较简单是吧。哎,算法简单啊,就是我们直接呢,一看就能明白哈。OK啊,这个呢,其实是挺明显的一个点了,那相对应呢,它的这个缺点思路就明显一点就是。算法只能说叫稍微的。是吧,或者说你相较于顺序查找来难一点哈,但以后大家来看这也都是。
20:06
很简单的是吧,哎,断法算法呢,相较于啊。对,相较于这个顺序查找来讲,简单难一点。难还得难一点是吧。好,然后接着呢。你说他缺点是啥?效率对这个相较于我们的二分常数来讲呢,它的效率低是吧。啊,效率这个低,这个效率低呢,其实就体现它的这个,我们说执行的这个复杂度啊。这个我们是O。对的。这个大写的O哈。啊,这就是大写的o on的。呃,这个执行呢,我们后边讲这个排序的时候呢,我们会说啊,这个呢是时间复杂度。嗯,复杂都是它而对应的,我们这个二分查找它明显的优点呢,是不是就跟它正好。
21:00
呃,相反了,这是缺点,这是优点是吧,这就执行的这个效率高。这个咱们在这写一下啊执行。哎,执行效率。高啊,然后呢,它的这个执行的复杂度,哎,刚才我们也稍微提了一下啊。对,是log啊,以二为底,N的这个对数我写成这个吧,看来会更清晰一点啊,那这个对应的我也写成这个大写的N吧。好,真正就是它了啊行,然后呢这块呢,我们说二分查找,除了说这个算法相应它哪一点之外呢,其实还有一个点啊。咱们刚才提到一个大前提。对。这个前提呢,就是数组必须有序。在有序的前提下,我们才能够去比。如果没序。那就没有意义了。啊,你说我们这块去找的时候呢,二分查找啊说呢,先跟中间这个比,发现的比它这个值小啊,去左边找,结果左边还有比它大的,右边还有也有比它小的,你要找元素,结果还在右边呢。
22:00
这不麻烦了吗?那就成不了了是吧,诶所以呢,它一定得是有序,至于说呢,你是升序啊还是降序啊,那个无所谓了。对啊,升序的话,就按我们说的,你比这个小蓝中去左边高。哎,你这个教训呢,就反过来就行了是吧。OK啊好,这个呢,就我们说的这个二分查找的这个事儿了,哎,刚才我提了一个啊,说这个数学系的或者统计系相关的会有一个牛顿二分法。啊,这个是是是啥呢,这个就是闲聊两句哈。这个呢,你比如说我们这是坐标系了哈,以前呢,咱们上这个中学的时候呢,都解方程是吧。解方程里边呢,可能含有这个变量,这个变量呢,我们最后解出,解出它的一个值是多少,这个是极其精准的。极其准确的就是就是这个数,那一开始的时候呢,这就是有理数,后来呢,有这种带根号的是吧。这个你可能说这个数呢,具体是多少啊,你可能有多少多少多少可能还无限循环的。啊,这是极其精准的,那么在实际科学运算当中,或者我们实际生产环境当中,有的时候呢,这种方程啊,它不一定能够就是解决出来,解出来一个极其精准的一个数数了。
23:02
就是很难是吧,第二个思路呢,就是我们也不需要你得到一个极其精准的数,你只需要告诉我呢,它的精度达到了,比如说0.000001就可以了。就能够满足我们的需求是吧,那这时候呢,其实我们就在统计上呢,有一种方法叫牛顿二分法啊,你比如说这个呢,如果我们看成是一个方程的话,哎,这个方程里边呢,你比如说原来都等于零,现在我们就让它变成Y,这不就相当于是一个。相当于一个。一个一个函数一样是吧,这个函数的话呢,我们在这个坐标系当中,其实你就可以呢,比如刻画出来它的一个曲线。啊,那你现在呢,这个是Y,你不就是想让判断Y等于零的时候呢,这个X值不就相当于是我们这条线当中的这个位置吗。对对,你不就想找他嘛,是吧。啊,这有点难啊,这个咱就先聊聊啊,然后呢,你怎么去找到这个值呢,我就先取一个X1,让这个X1呢。对,就相当于是这个S1呢,我一计算完以后呢,这个Y呢是个负的,那比如这S1假设就在这随便挑一个啊,然后你再随便挑一个另外的一个S2,让这个S2的这值呢,恰好呢,算出来这个Y呢是个正数。
24:10
所以说是正极也无所谓哈,这就S2了,所以呢,就是一个还是负的是吧。啊,一个呢,是不就正的了。那我说呀,我要找的这个呢,应该就在中间了。那这时候怎么办呢?我就取X1和X2中间的一个值。假设中间值是在这儿。诶,这不就相当于二分法嘛,是吧?诶中间值在这儿呢,你发现呢,这个算出来这个中间这个值诶有可能是正的,有可能负的啊如果它呢,发现跟这个X1呢,它俩之间就相当于是FX1,它去乘以这个,呃,你某个值它是小于零的,谁跟谁小于零,我就接着去要谁是吧?当然这个中间值是正的,那我就跟他俩匹配了,如果你这个要值是负的呢,我就跟这个去配对了啊。对,然后这俩配完之后呢,我再取中间这个,中间这个你发现呢,这个是负的,那我就接着跟他配对,他俩呢,我再取中间的,哎,发现就跟他俩配对,你看这个区间就越来越小,越来越小。小到你满足你精度的那个情况下呢,那这里边儿的每一个值都可以。
25:03
作为他的一个约等于的一个结果。对就可以了,对,这是一种通用的一种解法是吧。哎,这就是牛顿二分法啊。这里边儿呢,也用到了这种二分法。那思路呢,是一样的啊。好,那么关于这个查找啊,我们就讲完了,这个呢,在我们实际开发当中,查找或者要搜索是挺重要的一类操作了,诶那我们接下来讲个排序,排序呢,很多时候呢,目的就是为了方便我们去做这个查找,比如像刚才讲的二分法查找是吧?诶这个查找的效率很高,但是它的有序,那怎么办呢?如果没有序,你可以呢,先给他排个序。啊,通过这个角度出发呢,我们讲排序呢,也就有意义了啊,那么在这个数据结构当中,通常我们讲一些常见的基于某种数据结构的操作的时候,像数组哎,我们通常都会提他的排序算法。好,那这样话呢,我们先来看一看咱们对应的这个课件。提到了叫数组元素的一个排序啊呃,那么一提到排序呢,这块呢,先有一个官方的一个定义啊,这个定义大家看看能不能看得懂。
26:06
啊,它因为是个数学的定义,所以就会抽象一些啊。说呢,呃,含有N个记录的一个序列,哎,二一到2N这不N个元素嘛。哎,它相应的关键字的序列呢,是这个。这个可能就有点儿不懂了。咱先顺啊,所以呢,将这些记录呢,重新排序成一个新的,这不就把它重新组合了吗,一个新的顺序了,然后呢,使得新的这个顺序当中哈,对应的这个关键字呢,满足这样一个关系式。哎,那这呢,就是一种排序操作。有点抽象,我给你举例子啊,比如说这里边儿的每一个二呢,假设哈,就是咱们每一个人。哎,咱们班里边每一个同学是吧,哎,就都放在这了啊,大家呢,我说现在呢是混乱的,我就随便写的哈,数组呢虽然有趣,但是呢,这里边的每一个元素呢,其实呢,我就哎。是没有顺序的啊,所以呢,我现在希望呢,按照大家的这个年龄做一个排序,那么这个K呢,就是年龄的意思。
27:03
属于大家每一个人中的一个,咱算一个属性吧。是吧,按照年龄排序是吧,哎,最终呢,使得呢,这个年龄呢是递增的,然后大家呢,这不重新呢,就重新又调整调整位置嘛。哎,就这样子的,那你也可以呢,说这个K呢,表示的是大家的这个,比如身高。然后按照这个身高呢,是这样一个顺序来的,他重新又整合了一下。哎,就这个意思,好,那这呢是一般的一个定义,放到咱们现在呢,比如说我就是int型的数组。那这个二呢,就是代表一个一个的数了,那这时候这个关键字呢,其实这时候这个K呢,就相当于是我们这二了是吧。啊,因为这呢它本身就是个数,所以这呢就还是这个数,把这个数呢,按照一个升序呢来进行排列的。哎,这个注意一下,哎,这边也提到说排序的目的呢,就是为了啊快速的快速的查找。好,那么下边呢,就我们要谈谈具体的排序的算法了,排序算法的话呢,其实有很多种啊,那么不同的算法的话呢,我们怎么去衡量谁好谁不好呢。其实这块呢,就提到了,哎,排序这个衡量算法的一个优劣的标准啊。
28:04
哎,这个标准大家可能也有的听说过的啊,学过这个大学数据结构的呢,多少应该可能听说过的,哎,那这个标准的话呢,一般呢哈,我们说呢。这个探讨一个算法,它的这个优劣呢,标准一般就俩。我说的是一个算法啊,不管是排序算法了,那任何一个算法一般呢,这个标准呢,就是俩,一个呢叫时间复杂度,一个呢叫空间复杂度,那对于咱们的排序算法来讲呢,我们又加了一个指标。叫做稳定性。啊对,这个呢,是限于咱们排序算法来讲的啊。好,呃,那么这块呢,其实呃,我们就来看这个具体的概念了,讲了一个概念之前哈,诶大家可能有一个,呃,潜意识当中一个一个一个常识性的东西,说这怎么叫时间复杂,空间复杂度了。说我们看一个算法好坏,那就看多长时间不就完了吗?哎。我再说一遍啊,所呢你看啊,我们这块呢,还需有好多种算法是吧,哪个好哪个不好,我就看你这个,你说这种算法,那我们跑一下,你看你花了多长时间,这个多长时间,这个多长时间,我一看时间谁快那谁就好。
29:06
行不行?啊,不行。这多直接呀。对。诶,这个呢,首先说呢,这个想法是很直接的是吧,这个想法行不行呢,其实诶没啥大问题哈,呃,但是呢,你想想我们即使是同一个数组。啊,同一个这个算法,你两次跑的话呢。你发现时间也不一样是吧。这是一个点啊,再一个点的话呢,就是它跟你的硬件是不是也有关系。你说这个算法啊,这个数组,然后你在这个机器上跑,这个机器呢特别差,花的时间就长,然后你换了个算法,那个算法明显不如这个算法,但是那个性,那个CPU啊等等,这个性能也特别好,它算的可能就快一些是吧,所以你纯看那个时间这个事儿呢,不是特别稳定。那这时候怎么办呢?我们想找一种标准是吧,这个标准什么呢?诶以我们数组这块为例啊,我们发现呢,这个快跟慢呢,跟这个数组的长度啊。
30:02
有很大的关系。你速度要短那肯定快,你速度要长的话,那就慢,所以这块呢,我们不妨呢,哎,假设呢,这个速度的长度就是N了,我们看一看啊,不同的算法跟这个N的这个。是一种什么样的关系式?你像咱们刚才讲的这个,呃,线性的这个查找是吧。你发现了你这个是N,我们就从前往后变了一遍就行,那就是变了N次。啊,我们假设每一次的这个时间呢,咱就看成是一个基本的一个。单位时间吧,那你就是N乘以这个单位时间就可以了。如果你这个诶二分查账,你发现呢,人家呢,不用N次,人家这个烙恩就行了。是吧,那你这个N呢,假设呢,我们说是是八这就八次,然后我这要是八的话呢,我这得出来是不是就三了。对,那我三去乘个基本单位,那我就快。所以这块呢,咱们就不去计算那个所谓的精准的时间了,我们只考虑呢,跟你这个诶数组的长度的一个关系式是多少就可以了。啊,那么这个关系式里边呢,我们又说了一下啊,说呢,其实也不用整的那么细啊,你说你这个是N,我这个是2N,我你变了一轮就行,我编了两轮是吧?哎,咱们认为呢,你俩呢也差别不大,没有这种数量级上的差别。
31:15
哎,所以呢,我们就把,哎,比如你这便了一次就要N了,我这便利了,呃,我回去一次,呃过去一次我又回来一次,我跟那针对这个数字便利了两轮,其实2N哈,诶我们就认为你们呢,都是on的。啊,都是O的,就是都是跟N这个一次幂相关的。那至于说你是一个二分之N,那都是on。这个怎么看呢,其实这就数学里边呢,就是这样子了是吧,就是你上面呢,是你要得到的那个式子,下边是N,如果呢。哎,在这个N呢,趋向于正无穷的时候啊,有点丑了啊,哎,你最后得到的是个常数。那就说明跟这个N呢,就是同阶的是吧。这个呢,大家学极限的时候应该接触过这个概念,通接的就是一个次幂的那种方式是吧?哎,那我们就都叫O了,所以你上面是的,你说我是2N。
32:08
那还是你说是这个这个二分之N。也是是吧,啊,你说我这个三加五。也是啊,哎,我是这个二的N次方加个一。啊还还也是啊啊,这就不是了啊,这个你跟N的话呢,要是取一个极限,这不就成正无穷了吗?不是常数了是吧?哎,是不是跟N方才是常数。所以呢,这个你的复杂度就是N方的。啊,就这样。哎,那你这个私密呢,呃,这个越高其实就越。不好是吧,因为随着N的增加呢,你这个时间呢,是不是就陡增了是吧,所以这块我们就有一个这个复杂度的个关系式哈,所以这呢就叫常量级别的,常量级别就意味着比如我们这是哎,咱们这个刚才还是那个公公式里边哈,我这呢是一个三,你下边这个就就写个一,这个也没有N了,趋向极限,这不就是个常量三吗。
33:00
啊,就是你不管这个N呢是几,最后发现的就是那几次啊,跟没有关系啊,那这就属于这个常量级别的就是它。然后那个LOG2为底N的对数啊,就像我们刚才说那个二分查找,就是它的这样一个复杂度哈,然后on的N乘LOG2为底N的对数的N方的N的立方的啊二的N次方,这其实已经就就就很差了是吧。哎,比它呢,还就是相当于增长快的,我下边有个这个图哈。那这个你看这是on的哈,这个线性的。这个线性,我这个指标呢,也是这个。依次增大啊,这个纵轴跟这个横轴,你看它这个标度不一样啊。这是on的,然后这个呢,是N乘log n的啊,这是N方的,是二为底N的对数的,还有N的阶乘。比他长得还快。然后N的。N次方是更快是吧。对的啊,这个就更快了。行,这个呢,就是满足这样一个关系式,那大家呢,如果你发现,哎说某一个算法,它告诉你它的复杂度是它另外一个呢,告诉你是它哪个好。
34:04
前面这个好。哎,它会随着N的增加呢,它长得没那么快,所以他花的时间呢,就没有那么多,所以它就好。可以了啊啊,这个呢,就是我们说的这个叫时间复杂度。刚才我把这个呢,稍微的解释了一下,然后这个空间复杂度呢,就是说除了时间之外呢,我们还得看你这个算法啊,你想解决完这个问题,你还需要额外这个多少辅助的内存空间。啊,那这呢,我们也可以用跟N相关的这样的一个关系式呢,去表达,还是这个式子。OK啊,这呢是我们通常啊去判断一个算法说呢,谁好谁不好呢,两个指标。在这两个指标里边呢,我说呢,某一个指标啊,我们看的会更重一些,是谁呀。对,是这个时间复杂度。因为很多时候呢,我们都是拿空间来换时间的。因为现在的这个硬盘也好,内存也好,它也相对来说便宜嘛,是吧,所以这个时候呢,我们就是想让这个用户体验更好,那我们就加内存就可以了。
35:01
啊,加这个磁磁盘存储空间就可以了,所以呢,拿空间来换时间是我们现在的一些主要的思想啊,你说要是这个这个这个空间要特别贵了,那就是拿时间去换空间了啊,现在一般都不这样做。那在我们这个排序算法这块呢,还有一个稳定性哈,这个稳定性呢,就是这样的意思也很容易理解,说这呢是我们本身这个数组啊,这不需要排序吗?排序完以后的话呢,你发现原来你看这个五跟五它俩是相等的啊,排下序以后呢,这个原来这个五呢还在后边,这个五在前面的是稳定的。它俩位置没变,哎,如果你排完序以后发现呢,它俩相等,就然说呢,谁先谁后呢,好像都算是升序的了哈,但你发现你这种排序方式呢,导致原来的前面这个五呢,跑到你这个五的后边了哈,我们就称为叫叫不稳定的。哎,这个比较好理解,行。那么我们下边呢,就谈这些算法,看看他们各自的这种时间呀,空间复杂度啊,还有稳定性的一个问题,那到底都有哪些排序算法呢?这块关于排序呢,有一个分类啊,这个分类呢,大方向来讲呢,分成叫内部排序和外部排序啊,内部排序说白了就是在内存中排序。
36:03
那外部排序呢?啊卖不排序呢,其实就是这个意思啊,比如我们这个内存呢,有两个G,现在你要排序的这个数组挺大的啊,这个100兆。那这个内存呢是能够的,所以我们就在内存中排,那现在呢,我们这个数据呢,特别大哈,十个G的内存,十个G的数据。需要排序了,就2G的空间你肯定盛不下,所以我们只能是先取一部分呢,先排,排完之后呢,把这个数据呢,先放到这个磁盘中,然后再取一部分呢,再进去去排。哎,这呢,就需要借助于外部的这个磁盘了,我们就称为呢叫外部排序。很好理解啊好,那呃这个外部排序呢,是需要外部磁盘呢来参与的,但是呢,具体的算法还是得在内存中呢去操作,所以我们主要关注的就是内存的排序算法有哪些,这呢一列看这多少种。十种。哎,经典的话呢,我们讲排序算法呢,有十种,哎,然后呢,每一种的平均的复杂度,时间复杂,最坏的时候呢,最好的时候呢,是吧?哎,空间复杂度稳定性都列到这儿了,哎那么接下来呢,说一下你也就看一眼就行。
37:08
哎,不用去深究,我们关注的是哪些呢,哎,我用红框呢,这个框呢也框出来了啊,红框呢,这个当然就是更重要了。啊,这个对应的一个叫冒泡排序,一个叫快速排序,为什么扩除它俩呢。哎,说一下啊,冒泡排序。因为它很简单。就是多少咱们也得会手写一个吧,是吧?哎,所以呢,我们就写个冒泡,哎在实际的笔试当中呢,有时候确实也考你啊,说你写一个排序,他有的时候没说,那你就写个冒泡行,他如果要说了,说你写个冒泡,那你就写个冒泡。啊,那你这块就因为它简单哈,所以咱们一会儿呢,也写一个它,然后这个快速排序,为什么也很重要呢。对,名字都写的很明确快嘛,是吧,诶所以说快速排序呢,是我们实际开发当中选择的这种排序方式,它比较快,虽然呢,你看到它的这个时间复杂度是它跟跟这个呀,跟这个呀,你看复杂度平均上来讲是不是都一样。
38:04
但是咱们那会儿说了哈,你都是on的话呢,咱是不是也分一个,你是2N还是3N还是7N是吧。哎,那你其实都是on了,哎,就是他们虽然都是N乘log n,但是呢,哎,快速排序比他们俩呢,还是要更快的。所以说呢,这个快速排序呢,是我们真正开发当中用的一种排序方式,那进而的话呢,咱们稍微的也得去熟悉一下。诶,所以呢,这两个是我们最关注的这个堆排序呢,在很少的场景下呢,有时候也会呃,笔试面试会问一下啊说的呃,你知道堆排序吗。它是怎么实现的呢?是吧,还稍微可能问你一下啊,那一般呢,这个就很少了,其他的人呢,就接触的就会更少一点。那所以下边呢,咱们讲解的话呢,咱们就诶带着大家呢,就写一个这个冒号,然后快牌呢,一会儿我们说一下它怎么实现啊。好回过来,哎,这呢,我们就先开始这个冒泡排序了,说呢使用冒泡排序实现我们这样一个数组的一个排序,让它呢实现一个升序。
39:02
啊,升序好,那这个冒泡咋咋整呢,这不知道啊,那下边呢,咱们这块有冒泡的一个具体的排序的一个思想。哎,为什么叫冒泡呢?哎,我们这块呢,诶排序这个思想走完以后呢,你就知道了,哎这呢,我是放了一个静图哈,那你要是大家想看一个动图的话呢,可以在这看,哎,你按住这个CTRL键啊点一下。第二下这个浏览器哈。哎,我把这就关掉了。啊,这是一个数。给我们来一个创建啊。年再再重来一个吧。这个稍微的长一点的好,你看啊这呢,比如就我们这个数组啊,这个数组的话呢,目前呢,是一个乱序的,我们希望呢,让它实现一个升序啊,这个升序的话呢,先说一下大体的一个整体思路啊,就是冒号排序的特点呢,就是相邻的两个元素呢去比。好,你看我们来一个开始啊,首先第一个跟第二个去比啊,如果呢,你发现呢,这两个比的时候呢,我们稍微的慢一点啊。比的时候呢,如果你发现呢,这个前面这个数要大,就他俩就交换。
40:04
相邻的两笔。哎,只要呢,前面这大我们就交换诶。好,那么到这儿的时候呢,我们最大的这个值是不是就出来了。注意我现在是不是走了这一轮了呀,那这一轮你说我比了多少次啊。有有的说N,有的说N减一,咱可不不说那么细了,是不是就on的。对吧,诶跟人相关,注意这是一大轮了哈,诶这是O的了,诶那么通过这一轮的话呢,我们就找到了一个最大值,那么接着我们要走第二轮了,第二轮是不是只需要在这一部分里边去找就行。所以这一轮再找的话呢,其实比上一轮就少一个是吧,少比一个了啊好,那么接着我们再开始。还是相邻的两个呢去比。这个咱们把速度呢就提一下。这个大家别光看热闹。你得要想。我大概要怎么去写了。相邻的两个,相邻的两个比啊,一旦发现前一个大,我们这块呢,就交换。
41:05
第二轮出来了。第三轮又是从头开始。再加个速。是吧,那你说我们这块要比多少轮啊。门轮。And farmer。多少轮多少轮,不是说一共比了多少次,是,哎,我这刚才完事了,已经啊。可以了啊。对,你比如说我要是有呃五个元素的话呢,你看第一轮最大的出来了,第二轮次最大出来了,其实你到最后俩的时候呢。对,你把那个第四个那个找到以后,就最后一个,自然而然它就最小的了,其实呢,是找了四轮是吧。哎,对的啊好,那么刚才呢,我们看到这样的一个过程了,其实这块呢,它有其他这种排序方式啊,诶有兴趣呢,你下来你自己呢去看看都行。
42:04
好,那么这个完了以后呢,我们回到代码层面。看看刚才我们这样的一个思想怎么去落地啊。这块我们写一个啊,叫bubble。哎,它的一个salt一个测试啊,那为什么叫冒泡呢?你看它每次呢,是不是就相当于冒一个最大的值出来,就跟那个水泡一样啊,越往上它不越大嘛,每次冒一个最大的泡。哎,就冒泡派去啊,形象一点啊好,那么首先呢,我们这个数度呢,已经放在这儿了,哎,比如说啊,咱们先去做一个便利。哎,编利一下啊哎,For循环for I一下ar.las然后打印一下A。哎,这个来一个杠T啊,这个位置呢就不要了,哎先呢便利一下,然后呢,我们哎实呃实现的这个冒泡排序。这个A实现数组元素从小到大排列。
43:00
拍完以后的话呢,我再去便利一下,希望呢,你就是从小到大了。在这儿我们来一个换行。行,那目前的话呢,我们要是去执行那一样啊。啊,没问题,好,那关键就是我们在这个位置去写这个排序。排序啊排序的话呢,刚才我们看到比如说第一轮。啊,我们就是比较相邻的两个元素,然后呢,找到一个最大的了,然后第二轮第三轮你发现每一轮都是比相邻的两个是吧,而且每一轮的话呢,都会有多个元素做比较,所以这块呢,呃,你看我们第一轮比较了多少个,第二轮又怎么着,其实他一看啊,能想到就应该是个嵌套的了,是吧。前套了啊,那要前套的话呢,这个两个思路,第一个呢,你就是先把这个轮数先整出来,第二的话就是先整,先考虑其中的一轮的。都行。都行啊,这个如果我们就先考虑其中的一轮吧,比如说咱们先考虑第一轮。执行的这个里边的这种场景哈,哎,那就是相邻的两个去比,一直一直比到最后,哎,所以这时候我们就for I一下啊,我就I是零这个ar.lengths先写成点LAS了。
44:08
然后呢,咱们去判断啊,如果你发现这个AR2I是吧,它呢,要是大于了AR2。I加一是吧。我就交换。交换咱们讲过了。交换这个AR2是吧,和。I加一。行,那就you一个time。哎。AR。对这个I加个一是吧,然后接着。哎,加个一。等于在这呢就交换了,好,那么这块你小心一点啊,我们这样的写法行不行。对,记着这块要减个一,因为你这块有个A加一了是吧,让它能够取到最后一个就行了,哎,所以这块记着有个减一了啊行,那这样的话呢,就是我们这一大。
45:05
而且呢,一直走到最后了。哎,我们就把这个呢,就交换了一下。没问题是吧。你说我要现在执行一下会是什么效果呀。管最大的出来了是吧。哎,你看这个啊,然后呢,这块我们就执行了这一轮哈,哎,76呢,其实已经出来了。哎,那这一轮不行,我们要好多轮,到底多少轮呢,是不是我们把它呢,得套到一个新的循环里边是吧。啊方循环。啊,这个呢,我们in特一个三角接了,啊这个刚才那会儿其实已经说了有多少轮呢。诶,N减一轮了啊,所以呢,就是ar.lesss减个一。怎么着?就这样就行吧。咱不是说多少轮吗?啊,这个呢,刚才呢,大家说的N减一轮就行,这个它最大的值不就是N减。嗯,从零开始的。呃,它不就是LA减一轮是吧,好,然后呢,你把这个呢,是不是扔进去。
46:05
人宇宙呢?稍微的再优化一下。哎,注意我说的叫优化啊,EG呢,就这样写其实也行啊。你说那是吗?测试一下。看看。真情是吧,感觉很神奇似的啊,感觉写代码像是在拼运气啊。啊。诶,我说这时候其实行啊,这个行呢,呃,这个确实也行啊,为什么我说要优化一下呢?呃,什么意思啊,你看哈,我们刚才在这个排序的时候。啊,这个这个我点成别的了啊。你看我们这个在排的时候呢,第一轮的时候,他把这个最大的呢,其实已经找到了。我说第二轮的时候呢,就没有必要再跟44去比了。你本身就比人家小,你比一下,那不是自己。找不舒服嘛,是吧。哎,你所以说你第二轮再比的时候呢,其实就没有必要让他再跟最后一个去操作了,就是往前一个了,所以这块我们说呢,叫做优化嘛,我这个没优化呢,就意味着你还跟最后一个比了,只不过比完之后你俩也没交换嘛,是吧,所以呢,你第二轮比的时候是不是就少了一个。
47:09
第三个又少一个又少一个是吧,所以其实减个减个。接就行了,第一轮的时候呢,这不接是零嘛,第二轮是少一个是吧。那接加加了,所以你少一个,诶就以此类推就行,所以这呢算是一个小的一个优化啊,然后再去做一个run。哎,没问题啊。哎,这个呢,就是咱们写的一个猫排序,只不过习惯上呢,我们说外边就要写,哎这个写接,呃,这个你把它俩换一换也行啊OK。好,这呢就是冒泡排序,然后呢,我在这个课件当中啊,其实还写了一个冒泡排序,稍微的一个叫呃优化哈,这个就是基于刚才咱们写的这个呢,又稍微的优化了一下,这个我就先暂时不说了。啊,可能一说有的同学可能会有点迷糊下来呢,作为一个思考题,大家可以思考一下,说诶怎么还可以这样再去优化一下呢。下来看啊好,那么冒号排序咱们就讲到这儿,要求咱们所有的同学啊,要能够写一个冒号排序,就是这几行代码。
48:04
啊,这个呢,在笔试当中有可能会出现,所以呢,要能够去实现这个的核心就是两个位置,一个是它,一个是它。好,那么接下来的话呢,我们来看一看这个叫快速排序啊,这个快速排序的话呢,我们首先来看一看它实现的一个思想啊,对于它呢,进行一个介绍啊呃,首先呢,提到说这个快速排序呢,是由图灵奖的获得者啊,是这个人发明的啊,这个快速排序这样一个算法呢,被列为20世纪十大算法之一。诶,同学想说,诶十大算法不就十个排序算法之一,不很正常吗?注意哈,不是排序算法之一哈,是对所有的这种算法都合在一起,它是十大算法之一,可见它这个重量级还是很高的是吧?呃,一个呢是快,第二呢,就因为排序操作呢是很频繁的,所以呢,在呃排序这些操作里边呢,它又是最快的,那显然呢,他的地位就是很高的了啊。诶,它的复杂度我们已经说过了,这个呢,大家记住它是N乘以log个N啊,因为呢,在有一些笔试当中,或者有时候面试的时候会跟你聊到啊,说这个快排的复杂度是多少,有的时候还问你说,诶它是怎么算的呀。
49:10
他可能会这样问你一下啊。OK,然后呢,为什么我们会用快排,包括呢,咱们也看到了,它跟其他的一些排序算法,这个平均复杂度呢,说都一样,诶那会儿我也讲过了哈,虽然说这个复杂度是一样的,只能说是同阶的,但那你这个系系数可能还不一样的,是吧?哎,那么整体来比的话呢,快排也是N乘以log根,这个这些复杂度当中呢,它还是最快的。OK,所以呢,我们在实际开发当中啊,用的都是快速排序啊,啊,那么它具体这种排序思想是什么呢?这个我就不看这了,咱们直接看下边这样的一个情况。下边呢,先整体上来看一看,首先啊,我们这个数组呢,是一个乱序的。我呢,随便挑这个数中的一个元素,然后呢,把哎挑完这个元素以后,剩下的元素呢,分成比它小的和比它大的两组。
50:00
那既然我随便挑,那不妨呢,我就挑第一个了。所以呢,我就先选了个49,哎,假设我把49就往这一扔是吧,然后呢,接下来把剩下的元素分成比它小的和比它大的。这就相当于一分为二。然后呢,接下来我们再考虑比它小的,这里边儿呢,我们不妨再取第一个元素,再把剩下的元素呢,分成比它小的和比它大的。其实这前三个就已经完事了。然后后边这块呢,不妨我取出来第一个元素,然后再把后边这元素呢,分成比它小的和比它大的。以此类推。就排成了,你看这个速度挺快的。就完事了是吧。这个呢,就是大方向来讲啊,大家知道它是怎么来做的。那么通过这个大方向呢,其实这个复杂度呢,就差不多了哈。咱们来讲你看啊,每次我们再去,咱就先说具体的这一轮当中哈,这一轮当中呢,其实每一次我们都得找到,诶,后边这元素比它小的,比它大的,实际上就意味着后边每个元素是不是都得跟他去比一下。这个也一样啊,都得跟大家比一下,所以这块呢,这就这一轮来讲,我说呀,其实是on的。
51:04
对吧。啊,因为你说诶可能是N减二,因为你这两个不用去便利了,但是呢,这个我们减减的那个常量就忽略掉了哈,所以呢,每一轮来讲其实是on的没问题是吧?然后呢,我们接着来看啊,它这个呃,数量就是数量,就是原来呢是有这一组,现在我们变成两组了,两组变成四组,速度变成八组,相当于每次呢,是不是相当于是指数级的增长是吧。那指数级增长,那就意味着你每次这个拆分以后呢,这个数量呢,不就相当于减一半吗。那这个轮数的话呢,到最后你就减成就一个的时候,不就不用减了吗。不断的裂变,裂变,裂变到最后就一个就不用裂了,裂了多少遍呢?啊,你要按那个多少个的话呢,不是二的N次方个,那多少变呢,其实就是它的一个反函数。哎,就是烙根。哎,Log位底N的对数。跟咱们刚才上面讲那个二分查找其实是类似的啊。诶,他就每次相当于砍一半,砍一半砍一半这样,所以这就是以2VDN的对数,所以呢,它的这个整体的复杂度就是N乘以LOG2N。
52:04
这就是他的一个复杂度。啊,就是简单的,我这样给大家呢,就是做了一个,呃,形象点理解的一个证明啊好,那么这个说完之后呢,我们下边你看一下具体该怎么落地去写这个代码呢,刚才我们说了,说这个49,我把它分成比它小的,比它大的,这个说的挺容易,你怎么就把49给它扔到这儿了呢。诶,下边我们看看具体这个操作。好,我这又换了一组数据,注意啊,这块咱们也只是把这个过程说一下,具体的这个快排的这个实现的这个代码哈,诶我就不讲了,因为呢,这里边儿会涉及到方法这个调用,而且还是个递归方法,咱们还没有讲方法,所以现在写呢,其实写不了。哎,等我们讲完这个递归方法的时候,讲面向对象啊,哎,到时候呢,大家再去写这个代码呢,就非常容易了,现在呢,咱们先把这个思想呢说清楚,OK,什么样思想首先的话呢,我把这个数组呢先放到这儿。然后呢,这个数组呢,刚才说了,我们就取它的第一个角标零的这个元素了。
53:00
那那么接下来啊,我这儿有两个指针啊,一个指针呢是从前往后指,一个指呢是从后往前指。啊,那么这个漏的话呢,先让它就是找不到一的这个元素了,这个就不用管了啊,然后这个呢,就是让它是最后一个索引的这个元素,从样往后指的这个呢,我们就找,诶每一个位置走的过程当中呢,我就找看是不是都比它这个九小。比如说这个呢,比九小三十呢,比九不小,我就停到这儿。也就是说呢,我从氧后找的时候呢,找到第一个比它大的元素。我就停下来。下来了是吧。啊,听下来了,好,那么接下来的话呢,这个呢是从后往前走,从往前走的话呢,我们默认的后边这个呢,都是比你这个九大的哈,所以呢,我从往前走的过程当中找到第一个比你小的这个了。停下来。哎,那么这两个元素呢,交换一下。诶,所以你看负49就在这儿了,然后负诶负三这个30呢,就跑这儿来了,然后呢,再接着往后走,接着这个往前往后一走,然后它是23比这个九又大了,它就停下来,然后这个呢是氦是负30,它也比这个九呢要小,它也停下来,然后他俩再交换一下。
54:06
他俩交换完以后啊,这不是负30跑这儿了,23跑这儿了,然后呢,你这个氦呢,接着往前走,漏呢接着往后走,他俩呢发现呢就不满足这个式子了。说白就是你俩已经。交叉了是吧,一旦交叉就停下来。哎,就停下来了,诶,那就说明我们前边这块都是比较小的,后边这块呢,这不都比较大了嘛,是吧,诶OK,好,那么在接下来的要做的事儿呢,就是我把这个负30哈。你你别一二十三啊,一定负30,把这个负30呢,跟最初的这个九呢,它俩交换一下。啊,交换一下,然后呢,负30就跑到这儿来了,九呢就跑这儿来了,那么这样的话呢,我们这个九前面这个呢都比它小,后边呢都比它大。诶,这不就实现了我们刚才说的这里边儿的第一轮的这个事儿了嘛,诶刚才这一轮这个事儿咱们也说了,这不是其实跟N是一个同阶的啊,所以它的这个复杂度呢,是on的,这是第一轮哈。
55:01
第一轮完了以后的话呢,诶,现在呢,我们就接着进行第二轮操作,现在这个数组呢,我拆成两个小的数组了,然后这个九,后边这个我打成灰色的,就是这块我们就不考虑了啊,咱们就光考虑前面了,光考虑前面的话呢,跟我们上面第一轮这个其实是一样的啊,不妨呢,我还是取出第一个来,然后后边呢,看看,看看是不是比你小啊,这个不小不小就直接停下来,负49呢,看看是不是比你大,大的话就先往前走,结果也不大,那就也停下来,他俩一交换。交换了,交换完以后的话呢,接着拿这个负49跟那个负三折,他俩得换一下,哎,换了。换成这样了,哎,其实这块呢,我们一换完之后,这仨其实已经就排好序了。诶,然后呢,这个呢,是比如我们第二轮里边的前面这一部分了啊,后边这一部分的话呢,诶跟我们刚才这个思路一样,九呢是我们上一轮的时候呢,找到这个中间的这个值了哈,呃,我们右边这块呢,你就拿23去比。然后呢,这个漏呢,就是从这个30这块往后走,这个呢往前走你看呢,是不是哎都比它小,就接往上走,一旦找到一个大的就停下来,这个呢都找到大的,一旦找到小就停下来,然后该交换交换。
56:04
哎,就是整个这样的一个思路。那么在整个这个思路当中呢,你会发现一个特点啊,什么特点呢,就是说诶我们呢,比如说以整个啊,先说上边这个啊。以整个这个数组为例,我们相当于先找到这个基准值。然后呢,后边这个呢,呃分成比它小的和比它大的,这是一个操作了,然后呢,你接着呢,把它呃分成这个两个小的这个数组之后呢,我们仍然是找到一个基准值,然后看它后边这个比它小的比它大的这个呢,也同样道理啊,这个我画错了,不应该画九了啊,再画它,诶它呢作为这个基准值,然后在后边呢,看成比它小,找到比它小的比它大的,你会发现呢,整个这个套路呢是一样的是吧。诶,那我们就可以呢,把这个呢,诶找到一个基准值,然后呢,后边的元素呢,分成比它小的,比它大的,封装到一个方法当中。哎,咱们讲明向对象的时候会说这个方法啊,碰撞这方法里边,然后呢,这个区别点呢,就是你的这个基准值不一样,还有呢,这个索引不一样。
57:00
啊,那么在我们第一轮当中,你发现呢,后续要调第二轮,第二轮里边这样,然后呢,像这个第二轮这个比较长的,它里边还要再去调这样一个功能,所以呢,就会出现一个,哎,快排咱们就写好了啊。写好以后啊,这个就出现方法里边掉方法了,你看这个呢,是什么样的情况啊,咱们就先看一下这个代码,大体上我就说一下啊,这呢是本身这个数组排序之前便利了一下,呃排序,然后呢,之后再变了一下,中间呢,我们就要快速排序,把我们这个数组呢扔进去,这就是咱们后边要讲的方法。面向对象咱们就说了啊好,那么这个方法的话呢,就是我这块写的,把这个数字翻过来,从这个头部开始,一直到他最后的这个区间。这不就是你完整的这个数组的这个区间嘛,所以呢,区间范围对它呢,进行一个排序,然后这个排序的话就放到这儿,然后呢去调啊,你相关的一个操作,那么调的过程当中啊,你看我这里边会发现呢,就是自己呢,会去再调他自己。啊,因为你看啊,比如说刚开始的时候,我们这边从头到尾,然后呢,你会涉及到你不是把它就拆成了前边一部分跟后边一部分了。
58:04
哎,所以呢,就是里边呢,就自己在调自己,哎方法自己调自己,这其实就是后边要讲的一个叫递归方法。啊,就是比一般的方法呢,可能还要稍微的难一点啊,就是整个这个流程会感觉有点绕啊,但是大方向思想呢,大家记清楚,我们在第一轮里边调,第二轮的时候不是还是这个套路吗?哎,这就是一个递归调用。啊就可以了,好,那么关于这个快排呢,咱们目前大家需要掌握的第一个它的复杂度。啊,第二的话呢,就是他的一个排序的一个想法是什么样子的就可以了,那么在实际呢,笔试面试当中呢,他可能啊,就是一般呢,他会问你,比如说快排是什么样子的啊,一般呢会说一下这个复杂度的问题啊另外一个的话呢,就是呃,让你写这个代码的情况呢,其实也相对来说就少一些了,通常呢,他至少会让你说一下啊,这个快排是怎么回事,怎么实现的啊,你呢,就像这个图一样,你稍微的给他列一个数组,稍微的描述一下这个过程,能说清楚其实也就可以了。啊,那么后边我们讲完递归方法以后呢,大家你可以再回来把这个代码去写一写,这个逻辑呢,其实也是比较清晰的啊OK。
59:07
好,这个呢,就咱们说这个快牌了,那除了快排冒泡之外呢,其他的这些排序算法呢,诶我就不讲了,因为这个时间关系啊,咱们不可能说所有的都整一遍了啊,诶大家呢,如果有兴趣的话,你可以打开咱们对应的这个课件,诶课件呢,数组排序算法打开以后,然后呢,一方面啊,这儿呢,我也放了一些所谓的一些动画了哈,呃,比如说你这块呢,只呃这个选择排序。就跑这边了啊。哎,全限排序,那它的一种思想什么样子的,他这其实就是先固定一个跟后边的每一个去比,不像冒号呢,是相邻的两个去比了,哎是怎么操作的,这就是一个动画上的一个演示了,OK,这呢也有相应的一些动画啊,然后呢,再回过来,诶对应的这个代码层面呢,我这儿呢就放了两个,诶大家呢,有兴趣你下来想看看呢,你就看啊,这两个里边呢,一个是考虑稳定性了,一个是没有考虑稳定性。诶大家呢,现在呢,你还看不懂这个考虑稳定性,因为呢,我是封装到一个对象里了啊对象呢,就是后边讲面向对象才会,所以呢,你先不用看它,先看这个,诶这个打开以后啊,相对应的,比如说这个呢,就是冒泡排序,这个呢就快排,这是选择排序,这是选择排序一个优化,这是系数排序,这是堆排序,这是插入排序等等。
60:14
统排序啊,哎,这呢我都放着呢,有兴趣呢,你就打开自己看一看就可以了。啊,其实正常来讲,大家就先不用去研究了啊呃,因为呢,从这个实际开发当中,我们用的是快盘,快盘呢有现成的直接可以调。啊,你要从这个呃,笔试面试的角度来讲呢,冒泡排序呢,会让写大家呢要求掌握,然后呢,这个快排的话呢,这个呢,但是我们写不了,而且笔试面试的时候呢,让你写的场景呢,也是其中一种情况,哪怕你说呢,你说我这个写呢。呃,写不了,我跟你说说他的实践思路,这个也都OK,你要说清楚的也没问题的。其实。OK啊行,那么关于整个排序呢,咱们就说到这儿了,好,那么接着的话,咱们看一看这个笔记哈,把这个呢,我们稍微的给大家补充一下,诶这呢就提到这个排序的这个算法了啊,那么排序算法呢,我们就说衡量谁好谁坏,对应的这个标准呢,我们提到了有三个标准是吧。
61:04
对,第一个呢叫时间复杂度。对,第二呢叫诶空间复杂度。诶对,诶,然后呢,第三个呢,叫做稳定性。哎,稳定性啊,然后这三个指标里边,我们最关注的呢,是这个时间复杂度是吧,诶这个是最重要的一个指标啊。好,那么这呢是我们说的这个事情了,然后对应的有一个时间复杂度,或者叫空间复杂度呢,对应的一个公式,就跟我们这个N相关的这个事儿呢,这个呢,大家做一个熟悉就行。啊,这个做一个熟悉就可以了啊,CTRLC稍微的粘一下啊。啊,这个我就粘到这儿了,这里边儿呢,是表的是这个二的N次方的一个意思啊。这是N的这个三次方粘过来,它会有这样的一个小问题啊,行,这是这个,然后下边呢,关于这个排序,这个分类呢,我们大方向呢,分成了叫做哎,叫内部排序和外部排序啊。哎,也非常简单,内部排序呢,就存在内存当中,哎,外部排序呢,就是哎外部的。
62:03
呃,叫硬盘或者叫外部的存储设备是吧。然后呢,再加上我们的这个内存。内部排序就是存在这个内存层面啊。来排序的。好非常简单,然后呢,针对这个内部排序的话呢,我们说具体的算法呢,提到了有十种是吧。诶,然后呢,咱们这个具体的啊建课件了。然后我们需要关注的呢,诶刚才我们提到了说有两个啊,第一个冒泡排序。对,另外一个呢,叫快速排序。诶,这个关注的原因啊,第一个冒泡排序,因为它那是最简单的。所以呢,大家最起码哈,你得能会手写一个。啊,需要大家啊会手写。啊,这是他的问题,然后呢,它的一个时间复杂度是多少呢。啊,这是多少。哎,刚才那会儿还真没提他是N方啊。还是N方,它可达不到快速排序这样的一个复杂度。
63:02
嗯,你想想咱们刚才呢,呃,八个元素,咱们说是不是有七轮。这个七轮也好,八轮也好,是不是都咱可以看成是on的呀。然后你每一轮的话呢,基本上咱们是不是都便利到末尾了。可能说每一轮有时候少一个少俩的少仨的是吧,但是基本上也是跟on是相关的,这不一乘不就是N方吗。诶,所以这是它的复杂度啊好,那么快速排序呢,它不是最简单的,它是最。最快的对。啊,那就意味着我们开发当中默认使用的都是快速排序。哎,默认选择的这种排序方式。所以呢,这个呢就比较重要了啊,所以大家呢,需要呢,掌握的点啊,掌握呢叫快排的一个,呃,实现思路啊。诶思路啊就可以了,然后另外一点呢,就是它的一个时间复杂度,这个呢需要大家知道啊。N乘以。嗯,对,长呢,我就省略了啊老根。呃,这个就是以二为底N的对数了啊,诶这个能看懂就行了,好,那这呢就是关于我们这个排序算法呢,诶掌握到这个程度呢就可以了,哎,你要说下边我还想看看,你要再看的话呢,建议你要看就看那个堆排序了。
64:11
啊,因为堆排序的话呢,复杂度呢,跟这个快排是一样的啊,有的时候啊,极个别的场景下的,可能在笔试面试当中,他可能会问你哈,说堆排序,你知道他是怎么样一种思想吗。注意堆排序呢是。没有见过说让你去写对派去的啊,顶多就问问你说,诶,你能说说他的一个实践思路吗?那这个大家可以通过代码呢,你再去看看就行,这个我就不说了啊。
我来说两句