00:00
同学们,我们下面呢,把规定排序的速度给大家做一个测试,呃,我们来看一下这个规定排序的它的特点哈,同学们,我们刚才讲过他的这一个,呃,在进行这个merge的时候,这是它最核心的,对不对?最核心的你们有没有发现,当我们有八个数据的时候,它的合并就是八个数据,它一共会merge多少次呢?Merge我们的,呃七次,那我问大家,假设我是8万个数据。是不是他merge的次数?就应该是什么呢?应该是8万减一。这还可以啊,对不对,还可以,那你想如果我们是冒泡哈冒泡,那就很恐怖了啊,如果你是一个冒泡冒泡排序,那如果是8万。如果是8万。8万个数据,那你因为它的冒泡排序,它的时间复杂度是N的,是O的什么呀,N的平方。
01:04
那你这个就很恐怖了。那想想,如果冒泡就是8万,数据是8万乘8万。那你这个它这个比较次数就太多了,因此我们这一个就是规定排序呢,他在最好的一个情况下,最好一个情况下,它这个时间复杂度其实是比较小的是不是,那我们来既然如此的话呢,我们来给大家测试一下它的性能到底。是一个什么样的情况。那么关于。就是刚才我说到关于我们各种排序法的这个复杂度呢,我们后面还会说,你看这先简单看一下,同学们看我们这个规定排序,它最好情况下是n log n这是什么呀?大家知道这是什么情况吗?这个是线性对数键,是不是讲过它是呈线性对数键,那但是冒泡排序你看它是什么呀,平均复杂度都已经到了N的平方了。
02:01
而我们我们规定排序平均复杂度才是线性节,所以它还是非常的快的,规定排序还是非常的快的。那么我们来。走一个吧,我们来测一下,看看是不是速度跟我们想象的呃,一样,还是很快的一种写法,对不对?好,来同学们打开我们这个,我们仍然像刚才那样做一个测试,我们先给他。做8万个数据。8万个数据在这里呢,我们先来写到这。是吧?把它格式化一下。我们把它格式化一下。好,格式化了,那8万个,呃,现在是不是8万个数据啊,我们先把它做成8万。八个数据,那么八个数据这呃,这个地方也是没不需要变化的规定排序后这个数组呢。呃,时间我们还没打。
03:00
把它规定排序过后,排序后的时间我们再来打一下。对不对?那么首先我们还是老规矩,先用一个小的数量来测试一下我们规定排序是否正确啊,前面还少考了一点东西。规避排序前这个还没有把这个打,还没有把这个写过来,对不对,好这个产生数据来吧,所你们看这样就没问题了。我现在要把上面一个注销,我一共有八个随机的数,然后排序这边打印出来,验证一下八个数据肯定很快,这个没什么可说的是吧,首先看八个数据呢,我们花的时间很短,而且证明的确是一个有序,看这是156。就是207了,这是225310348417522。761没有问题,好,现在我们来测试一下,测试之前这些打印的信息我就把它拿掉了,因为你要这样的话,那这个打印就会花很多时间,这肯定就不是有效时间了,对吧?好来,我们现在把这个改成8万。
04:02
8万速度应该是秒杀。因为他这个时间复杂度只是一个线性对数间,是不是,所以说这样一执行呢,我们可以看到8万个数据应该是秒杀。诶诶,这这这来这个玩意儿啊,不好意思啊,这个就不行了,这个不行。这哦哦,不好意思,我把这个没有注销,没有注销,那这个肯定就没法看了啊走一个。好,你看一秒钟我们再再执行一下啊。再试一下。好一秒钟不到了,因为他因为有各种情况嘛,我们再执行一下8万个数据。是吧,一秒钟再来执行一下。再来仔细一下。对吧,一秒都不到,我们现在把数据量整大一点,80万。80万,我们看看能不能在一秒或者两秒左右把它排完。一秒搞定了,我们再来把它整成800万个数据,800万个数据呢,这个就可以跟刚才快排,还有这个希尔排序进行比较快排,好像是两秒到三秒是吧,这一个个十百千万,十万百万,好我们看看这一个。
05:11
呃,规定排序,它能不能在两到三秒左右把它搞定。好的,我们可以看到。呃,三秒啊三秒。还是可以的啊,还是可以,也就它的速度呢,呃,跟快拍几乎是一样的啊,零四秒。再来看084秒啊,这个稍微快了一秒,我们再来看。再来看一下。OK,来看这里。啊,三秒说明应该是在三秒到四秒之间,跟快拍速度几乎一样。所的还是非常快的,非常快的好,那关于这一个归并排序呢,我们先聊到这儿,下面我们把归并排序写的东西给大家简单的整理整理,那规律排序我们是讲了哪些内容呢?排一下版。首先我们给同学们说一下这个归并排序的概念,是不是归并排序,它的核心思想是分制。
06:08
哦,分开在。先是分再合,因此大家看该算法采用经典的分制策略。诶把这写到这儿啊,分制策略。那什么呢?核心就是先把问题分解成一些小的问题,在递归求解。这是它的核心及分而之之,那为了把这个分规定排序说清楚呢,我们这有一个规定排序的示意图,这个图呢,先做做了一个整体的介绍。这就是说就是这张图了。是不是就这张图?是很简单的,那上面这个蓝色部分叫分,分的过程其实说白了就是把我们一个大的数据分解成到分解到各个站,每个站的,每个站指向的数据呢只有一个,但是分的过程本身没有实质在做什么事情。
07:01
它仅仅是分开而已。那么治的过程中,治的过程才是真正干活的,那么怎么治,他是怎么把这个治过来的呢?好,我们这有一个小案例,这个案例这个图形呢,就把整个一个合并,就是字的这一个过程,把它描述清楚了,其实字的过程从我们这边来看呢,它应该分成了有这么三步,哪三步呢,大家看,第一步是先想办法把左右两边有序的列表拷贝啊,填充到这边来,第二步把剩余的那一部分再依次填充过来,最后再把temp。拷回拷贝回这个OA。就这样子的对不对?好,这两个图呢,同学们,我们也把它给各位朋友展示到这里,大家呢,有兴趣看一看,当我们有这样一个基础以后呢,我们就来写了一个数组来进行测试,对不对?这是我们规定排序的一个实例。
08:01
这是我们规定排序的一个实例,好的,那这个实例呢,我在这写的是这个案例,但实际上我在代码里面用的是这个数组,因为这个数组刚好跟我们图解。呃,保持一致,这样呢,大家好理解一点对吧,好最后代码呢,我就先到这啊代码演示。啊,代码我直接给朋友们拷贝到。笔记中去,这样便于大家的今后的一个复习,各位。就到这啊,那规律排序呢,老师就给大家讲解到这里。好不好?然后呢,为了加深好这个印象,我建议同学们在课后把这个规定排序理解,然后独立的把它写出来,这样你的印象就会非常的深刻,最好把那个图自己画一画。OK,那这一讲我们就先说到这里。
我来说两句