00:00
下面我们来测试一下传说中的快速排序,它的速度到底有多快,那还是老规矩把刚才这段代码啊,就是前面这个测试的。呃,代码呢,拿过来大家看,我们还是呢,给他8万个数据,明白8万个数据,好,我先把上面这个呢注销一下。好,我们写一下测试快排。快排的一个执行速度对不对,我们看看速度到底有多快呢?好,我把这个呢给大家格式化一下。我把上面这个已经注销了,现在有8万个数据,那8万个数据在执行之前。对,在AA到这啊,在执行之前呢,我们把它时间打印出来。是吧,同学们把他的时间打印出来。OK,这个没有问题,那么在执行之后,在执行之后呢,我们也把它的时间打印出来。在这里对不对,同学们啊,这这排完了,排完过后我们把它打印出来,显然这个时候我们不能够再去,呃这样打了打,如果我们我们可以先试一下我们这个代码到底正正不正确,因为前面这个数据呢,我们是这样分析,但是到到底是不是正确呢?我们再验一下,我产生八个随机数,OK,我们来执行一下,看看到底。
01:20
这个快排是不是稳定的好,我们可以看到呢,这个结果没有任何问题是吧,2930的五,六的五,七的六,二的六,五的六,九的七的说明的确是。哦,这个正确的,现在我把它。提到8万。个失败千万八万来各位朋友,我们运行,那运行这个时候我们就不能打了,因为8万的数据你打太费时间了,来运行一下。好,我们看时间的速度,时间啪一秒钟啊,我们再看一下。再看一下。没,没到一秒了,再来执行。OK。每到一秒,那现在呢,我们可以这样子,在这个数据里面,我们再加上一个零。
02:04
现在就是80万个数据了,是不是我们看80万个数据,他要多长时间呢执行制。贵朋友看。是不是很快啊,你看刚才这个12排序,12排序我们8万个数据是大概一秒,那我们80万个数据,你看这个12排序是多长呢?我们看一下啊。现在执行的是希尔排序,希尔排序要一秒钟,也还可以,也还可以啊,也可以我再加一个。现在800万个数据了,啊个十百千万十万百万八,嗯,800万,800万个数据,我们看希尔排序它需要多长时间,我们看两者谁的速度更快。好,同学们可以看到。现在是404秒钟线排序需要四秒钟搞定800万个数据,那快速排序我们也来一把,快速排序目前是呃,80万,我再加个零。再加个零,我们数一数啊。
03:00
呃个十百千万,十万百万,我们看快排800万个数据要多长时间,是不是能够拉开和希尔排序的一个啊一个距离走起来。OK,我们可以看到。快速排序800万个数据,四秒钟我们再执行一下。走一个。两秒钟还是快一些。800万个数据啊,还是很快的,你看我再执行一下。我再执行一下。看看是否稳定哈。两秒还是比较稳定,希尔排序呢,应该是,呃,没有这个快排,在综合情况下来说,没有快排快。啊,快板呢,用用了递归这个,递归这个效率呢,确实是就是说他在执行的这个,呃,空间换时间上还是非常明显的,虽然我递归的次数多了,但是我的速度确实有所提升,对吧,两秒钟。
04:00
好,那现在呢,关于这个快排快排我们就搞定到这里,我们把刚才讲解的内容呢,给大家阐述一下,刚才我们讲的是什么来捋捋。那刚才呢,我们讲的一个快速排序。走。快速排序呢,我们首先对快速排序的算法做了一个呃介绍是吧,我们说快速排序它是干什么的?首先大家要明白,快排呢,它是对冒泡排序的一个改进。这里面它用到递归了。对不对,大家知道递归肯定是要开B站的,那开B站呢,就需要空间,这是必然的,对吧,这是必然的,所以说他这个呃,用到递归了,用到递归,用到递归过后呢,我们可以看到这边有一个示意图,关于快排的一个示意图,我们也拿过来。这是快排的一个示意图,这是。这么一个图形。但是这个图呢,他跟我讲的案例呃,有一些出入,因为这个图它是以最后这个数作为基准来进行这个分解问题的,那么我这里还画了另外一个图,就是这个图呢,是跟我们代码匹配的一个思路分析图,因为这里呢,我用的就是后边我们这个数组。
05:20
而且大家也看到,我第一次分割找的这个数量是零。找到中间这个数,以它为中轴数进行左右。这个分解,然后呢,对左进行递归和对右进行递归,最后我们拿到一个有序的数组是吧,我们这个图呢,跟讲解的内容更匹配,所以说我也拿过来。被拉过来好,有了这两张图以后呢,我们这就对代码做了一个呃,演示对吧,我们这完成了这么一个东西。那我把这个我把这个快排的应用代码呢,给大家拿到这里来,就是我们的应用代码,这边是要求,要求过后呢,我这还做了一个验证,大家有没有发现我刚才呢,其实在讲解过程中已经把这个过程讲解清楚了,看如果我们取消左右递归,其实你会发现呢。
06:13
只是把0比0小的数放在零的左边,把零大的数放在右边,但是两头都不是有序的。如果我去掉取消右递归,你会发现呢,只有左递归,呃,左边它是有序的,右边没有序,如果我们取消左递归,你会发现呢,右边是有序的,但是左边是无序的。只有把这几左右DV都加进去,我们发现最终才是有序的,所以最后代码呢,我也写到这里啊。代码实现。代码实现,我直接把这个代码给大家拷贝到我们的笔记中,而且我们对它速度做了一个验证,是吧,我们发现八八百万个数据呢,其实也就是两秒左右,在我的电脑上两秒左右,那如果说在你的电脑上呢,可能更快,因为我的机器性能不一定比你好,是不是好这个呢,我们就给大家讲解到这里,讲解到这里,好,这是我们讲的快速排序的。
07:12
一个。一个问一个这个速度的测试和小结。
我来说两句