00:01
同学们,下面我们来看一下我们讲解的这些排序算法的。它的一个对比在八大排序算法里面呢,还有一个堆排序我们没有给大家讲解,原因是堆排序呢,它跟我们二叉树相关,在没有学习二叉树之前,我们没有办法给大家讲解堆排序,那堆排序我们放到哪里去讲呢?等到我们把二叉树。讲完了。我们再给大家讲对排序,OK,现在我们看一下这几种排序法的它的时间复杂度的一个比对。首先我们来解释几个相关的术语,一个是稳定和不稳定的概念,其实刚才呢,我已经讲过了,所谓稳定和不稳定主要就指的是呃,如果有相同的数据。他们在排序以后呢,仍然保持相对的这个前后位置,不,不改变就称之为稳定,否则不稳定。这里还有一个概念,叫做内排序和外排序。
01:00
那么内排序和外排序呢?就是我们说in place out place对不对,这个所谓内排序就是内存在内,在内存完成外排序呢,就有可能放到磁盘。就有可能的啊,那么还有一个问题就是时间复杂度,时间复杂度我们在前面已经讲过了,就是一个算法执行所耗费的时间,空间复杂度呢是指的完整一个程序所需要的内存大小,注意还有个N,我们可以看到在这里面有N,这个N代表数据规模,说的再简单一点,就是你要有,你要针对多少个数据进行排,还有一个K,这个K在我们这里面只有哪一个出现呢?只有这里面出现了啊,有技术排序,统排序和技术排序。那么技术排序和统排序我没有去讲解,因为它的整个思路其实跟统排序是很相似的,很相似的,和我和我们技术排序很相似,所以说我们就没有去讲它了,呃,那么还有一点要说清楚,这个in place和out place指的是。
02:01
是不是是否占用额额外的内存空间,是否占用额外的内存空间,大家理解。那么我们来看一下这几个排序的时间复杂度,我们现在直接看哪里呢?看它的平均看这里。从平均时间复杂,呃,复杂度来讲呢,冒泡选择插入是一个级别。对不对,是一个级别,那么我们的这一个冒泡还有插入呢,是属于稳定性的。稳定,再来看希尔规定快速,他们的平均时间符杂度呢,都是一个线线那个线性对数阶。线性的对数解,那么我们再来看基数排序,基数排序是时间,这个时间符合数是N乘以K,这个K是代表统的个数。我们比如说有十个桶,那么它的实验复杂度就是什么呢?假如我们有十个100个数据。那么我们这个时间复杂度就类似于十,呃,100乘以十一千。
03:05
就这意思啊,所以说基数排序呢,它这个呃,它这个是平均是复杂度相对来说比这个冒泡可是要小很多了,因为冒泡是N的平方,这个N的平方假设冒泡排序有100个数据,那就是100乘以100,这就可是1万了。而且大家有没有发现,随着数据量的增大,这个冒泡排序选择排序,插入排序会。这整个这个值就会非常大是吧,所以说从我们刚才运行的时间来看呢,我们也看出来基数排序在数量大的情况下,它还是速度很快。还是速度很快,那么希尔规定快速呢?它是线性对数阶,如果这个N值很大。那么大到什么程度呢?假设这个它的对数就超过这个十的话呢,你会发现基数排序还比他们这两个还要快。但是如果这个N比较小,这个N比较小,那么我们这个基数排序呢,没有,呃,相对来说就是整个这个值就会比什么呢?就会比他们还大一点,就是说这个N的规模越大,我们这个,呃,比如说log。
04:14
这个线性它整个这个值超过了十,那么它的这个速度就会比我们基数排序还要多一些。但是因为这个K,我们这个K是个痛的个数是十嘛,它不它它就不会像说随着你的N的规模,我还我还继续变得很大,对不对。好,这是我们讲解的常用。排序算法的一个比对,那么可以看到这边是一个级别,那这课是一个级别,这边呢,技术排序又是一个级别,至于速度谁快谁慢,还取决于这个规模,就是你的规模大小也有影响。那么我们关于常用排序算法的总结和对比呢,就简单给大家介绍到这里,那同学们我们把它整理一下。
05:03
刚才我们讲的是什么呢?我们讲的是对。这几种排序算法的一个比较。排序算法的一个比较。OK。呃,具体来说其实就是这有一张图是吧?这张图呢,大家脑脑海里面要有有一个印象哈,多少要有个印象,大致你要明白是怎么回事对吧?别人问到你插入排序,选择排序,还有这个冒泡排序,它的平均时间复杂度和最最坏平最坏时间复杂度是什么?你至少要告诉他是平方键,至少这个要答得上来吗?然后呢,希尔规定快速,它的这一个最快呢,它的平均时间幅度是什么呢?是线性对数间要答的上来,但是大家大家要注意这个,这怎么去回答啊,呃,再看一个,呃,如果说嗯这个问道基数排序是。
06:01
时间复杂都是什么呢?大家看它,它是很稳定的,不管是平均最好还是最坏,都是很稳定。对不对,但是什么呢?是N乘以K的这么一个时间复杂度,而K呢,是一个常量十嘛,如果你没做任何处理,它就是十。好,这一点大家要有一个清晰的认识,那么这边有相关的术语呢?我也给同学们板书到我们的笔记中去就可以了,相关术语整理一下。OK,上面诶写错了啊,上面是一个图一张图,这个图呢,大家要有一个印象。OK,好,我背。小这里啊,这是我们的图形。啊,图就是一张。一张排序。排序。排序算法的。比对比较。比较土。我列到这里了。一张排序算法的比较图,这边是相关术语的一个整理,我给同学们整理到这里。
07:07
好同学们,那关于我们这一块的比对呢,大家呃,了解一下啊了解一下。
我来说两句