00:00
同学们,我们上午呢,把这个插入排序法给大家讲了,那下面还有两个排序法呢,就也给大家说一下,一个是快速排序法,我们来看一下,首先还是老规矩,我们先把快速排序法的它的这个思想跟大家讲一讲哈。跟大家讲一讲,呃,首先我们来分析一下前面两种,前面三种排序法呢,它其实其实没有用,没有用使用递归就是它是就按照这个流程一步一步走的。那这样的话速度呢,肯定是提不起来,那么现在看一下快速。快排呢叫quick sort,它是对冒泡排序法的一种改进,它怎么改进的呢?他的基本思想是如此这般的。他通过一趟排序。将要排序的数据分割就分成两个部分,怎么分呢?其中一部分所有数据比另外一部分的所有数据都要小。
01:03
也就是说找到一个数,以这个数为基点,为为这个为这个这个基点,然后呢,把它分成两部分,然后再按这个词,此种方法对两部分数据实行快速排序,他这个示意图同学们看一下。我们以这张图为例来给大家讲一下,你比如说同学们看到我们在这里呢,有一个数组,这个数组显然是无序的。然后我以11。为这个基。以这个基准,当然更多的问题呢,一般更常见的是以中间这个值为这个为这个基准啊,反正意思都大同小异,然后呢。我假如我这个示意图是以11为准的,他把这个示意找到以后,把比11小的数扔到这边来。把比11大的数扔到这边来。对。
02:00
然后这边做完了以后呢,他同时这边进行递归。递归过后呢,他又把这边分成的这个数组,又以五为这个基准,当然更多的情况也是以中间这个数为基准进行分割,那道理都一样啊,它以五为基准的话,就把比五小的分到这边来,比五大的又分到这边来。同样这边也是一样的道理啊,比如他是以21为这个基准的,把比21的人这边啊,比21大的人这边继续,呃,当然到了这边他发现二和五只有一个了,那就那当然没没办法再割了,是吧,已经是独立的了,然后这个十和八不是那么再分,那这边就分成了二五八十,那这边变成了12。12 21 22 28和34,最后这样就。得到一个新的数组,这个数组呢,就是有序的,这就是所谓的快派,那快派同学们分析出来,你们发现这就有点类似于什么感觉呢?有点类似于以前我们去排数,我们怎么排,就是找一个人一个一个的比较比,比如已插入排序,就找一个人在不停的形成一个有序的一个数组,但是快排有点什么感觉呢?就是说我们说。
03:19
以中间为基准,把它分成两个部分,过后又找不同的人来排,就好好几个人一起来排。那你想这个速度肯定是。非常快的对吧,而且它这个越往下走呢,这个分割的这个速度就会越小,就速度就越快。那事实上,呃,就有点像多个人在进行这个排序,那结果是什么样呢?大家可以看到,如果是个8万的数据,它几乎是以毫秒级的,就是你测出来是零秒到了80万的数据呢,我测了一下,大概也就一秒到两秒之间就出来了。啊,如果800,呃,可能80万连一秒到两秒都没有,到了800万的数据,我测了一下大概是三秒。
04:01
同学们,800万的一个无序的数组,三秒排完,这还是很恐怖的啊。这已经很快了,依旧已经很快了。好,那么我们来看看他的代码是怎么实现的,好吧,我把这个截个视频。
我来说两句