375_尚硅谷_Go核心编程_数据结构和算法-排序的速度比较.avi原创

好说一下啊，我们现在呢，拿一点时间来比对一下我们前面讲的三种排序方法的一个。啊，一个这个这个效率问题，或者说时间问题，我们看一下来。现在呢，我们打开打开这个地方啊，打开我们笔记，我们先回到。这个地方我们再增加一个就是三种排序，因为冒泡那个呢，我们以前讲过，我就不去比对了，我就直接比对这三种就是。诶，这个是站的实线啊，站的实线。是排序应该在这里。就是。好在这啊，我们自己讲就是三种三种排序，排序方法的速度。啊，速度的一个分析，就说以后同学们这个参加工作以后呢，你想去看哪个排序方法更快，你可以用老师这种思想去玩一把，好打开我们的这个方法，我们先来看第一个选择排序法。

那么选择排序法我们是在哪里写的呢？是在这个地方写的，同学们是select啊select寻寻觅觅一下啊，这来我们来，我们整8万个数据，不整多了啊，8万个数据，我们看他花的时间是多少。那么8万个数据呢，你要先把它整成一个无序的才可以，所以说我们先来整8万个数据。走一个R，我先定义一个数据测置数组啊R，然后呢8万。个十百千万八万就可以了啊，80万呢，等的太久了啊in，然后呢，我给他随机的产生8万个数据，这个很简单，For循环I等于零。I小于8万。个十百千万好爱家家。然后呢，我给这个瑞开始分配数据。

给到一个值，这个值呢应该是一个随机的，我们用red.int。N。好，然后呢，然后同学们给它一个范围大一点的，把它散开，这个散的越开，咱们最越容易来判断它的速度，所以说我给他来一个这样的。闪开一点，但是因为用red呢，需要引入一个包包，大家都知道是慢包，我们以前学过。就是我们数学包里面有个round对不对，好这个就没问题，然后呢，我们把这个先测试好好。呃，然后这个就不要再打了，因为你8万个数据这样打呀，你会。你你会死到死的，死死人的啊，不要再打了，因为我们现在测试的时间呢，是它的这个排序时间，所以说这里面呢，我们也不要打了。这里面打了也要也也也会死在这里面的，千万不要再打了。好，这个也不打了，就打印的时间我们不做测试，然后呢，我在这里在它排序之前把它的时间算出来，大。

Start，那么我们就等于一个time点闹。对，那取得当前的一个时间戳没问题，尤尼可斯。对不对，Unx，然后然后呢，End结束的时候，它这个做完了以后呢，我们再打印出一个时间那。那诶点啊。time.no然后点time unique好，最后呢，我们这个这下面也不能再打啊，再打这个地方也会也会出问题，我就直接说耗费时间是多少。好排序时间。就是选择排序法，选择排序耗时等于多少秒呢？输出来。这边有个F。好，这边是个秒数对吧，这个呢，我们以前讲过秒啊，然后把这个减一下，就是用end end减去一个start。

好，写完了，写完过后呢，我们来做一个小小的测试啊，我们看看这个测试大概是大的单词写错了吗。好的。这个地方逗号写错了。啊，还是写错了。好，我们现在看一下8万的数据，他画了个诶，Time time没有写，Time时间包包没有写，你就去还有一个时间抛time没问题。好，各位同学，现在呢，我们来验证一下啊，他8万个数据花了多少时间，这个地方是有问题的啊，因为你那边是8万了，所以说这边呢，也要把它调成8万。啊啊，这个排序的正确性我们上午已经做过了，不要在不要不要怀疑啊，肯定是肯定是排序是正确的，那么现在我来开始运行CD，点点CD到select。注意go run main.go。好运起来。这个实验为什么会这么慢，因为它生成这个数会比较多一点啊，时间会比较多，排序时间看一下。

八个数据。好，等待。好，同学们可以看到排序耗费了12秒，我们再执行，再执行一次，取它一个平均值。看是不是稳定的，就是十几秒啊，是不是十几秒。好，同学们可以看到选择排序。8万个数据，第一次是12秒，第二次十秒差不多。啊，就是说你看这个它只要散开了过后，你会发现它是时间还是比较稳定的，那么现在呢，我们来判断一下插入排序来插入排序呢，老师就不啰嗦了，把这边需要的东西拿过来为我所用，我粘贴拷贝一下就行了，操作培序来走一个。对，然后呢，从这边再粘贴一点过来，哎，实验。好，我把这段这段代码拿来为我所用啊，同学们就是这个好，这个这个呢，我要用一下。把这个用一下就可以了。

来写到我们的main函数里面去，我们来看看它的速度是不是真的要快，说跟老师分析的是不是一样，是不是快一半大概五秒六秒就能出来一样的问题啊来好，这个呢，我把它拿到这儿，先把它注销一下。同学们注意听。好，我把它放到这里来，然后呢，原始数组也不能打印了，对这地方也不能打印了，我直接输出耗时时间。的print n f，我们就说一句话啊，就说插入排序，插入排序耗时。百分之D秒。同样，我们也是用这个end。减去start。好啊，同样这边呢。接收的地方，咱们也把它改成这个8万。好，代码写完了。OK。好，往这边下看一下，有有问题，End end没有写，End没有写，那在这地方呢，结束完了过后我们再拿到一个end。

好，注意还有一个地方，我记得应该还有一个地方啊，同学们，我们在这儿好像是输出了，这个绝对不能输出，这样输出的话。相当于把输出的时间也算到排序里面去了，这是不合理的，那人家不划算。好，我们来看看，插入排序CD点，点好CD到我们的insert go run面点够好。8万的数据啊，看时间。看时间。好，同学们可以看到它的耗时为四秒，而且跟我跟我想象的还稍微还要快一点，再跑一次。再跑一次，8万个数据。好。可能这是五秒左右，或者是多少秒啊，你看反正就在大概就在这个这个这个这个范围波动，那么为什么他会这样子，大家想一想，别人问你，因为你插入的时候它是这样子的，他他总是从后面往一个有序数字里面插。

所以说从平均来看呢，他以后在比较的时候，它其实就是在，就是在你这个速度的一半，就它不是全部时候，你你选择排序法是怎么做的，它总是全部看完才找到最大或者最小的，他每次全部要变完，但是插出排序，因为它每次都像这个有序数线差差，所以说。它总会根据它那个平均值，它总是它的长度的一半，所以它扫描的就应该是将来是你整个长度的一半，所以他呢，时间上它可能要节省一半，就是这个原因，好，那么我们再来看看最为厉害的。快速排序法。而且我要问大家为什么快速排序法快。你要给我解释清楚，注意啊，快速排序法并没有，并没有，这个并没有多线程，它仍然是，它其实也是把左边排完再去排右边的，他并没有像我们说用多线程的，但是它为什么会快呢？你得想明白这个道理。

你看啊，我们还是八方的数据，我们再来玩一把。OK，那不说不不说，我们直接把这段代码呢拷贝过来放在我们的。放在我们的insert这个quick sort里边去啊，OK，朋友们。好的，那现在呢，我们在这儿粘贴一个包包，然后从这边粘贴一份。好，他的这一个排序的这么一个东西，好这张我也不要了，我就直接生成8万个。8万个随机的数，然后呢，这个N。这边结束，也来一个end。好，直接在这个地方就输出耗时为多少print f。个位好，我们写一个叫快速。啊，快速排序法耗时。他。等于多少秒啊，这么多秒。

啊，当然这个是D了，然后呢，我们写上这个N减去一个start，注意在上面呢，我们也不要再输出，哎，上面本身我没有输出，那就无所谓了，这边改成8万。好了，同学们看8万了啊，这个就对上了，这是8万，然后呢，这边我们随机产生了8万个啊数据，8万个数据好，我们看看它的耗时是多少呢？CD点点CD quick short，然后go面点go走。我们看耗时多少。我们的耗时呢，是零秒。说000秒不现实吧，他就是耗时零秒，因为它从秒的单位上看不到，说老师那你整大一点，我可以整到80万。我这边改成80万就完了，80万啊同学们啊。如果你这个，如果你这个按按那个选择排序，它的时间不是按一倍增加。它绝对不是按一倍，不是说啊，不是按十倍增加啊，它越多它它越慢。

因为你一次是增加了一半，你两次就增加好多次了，所以它的增加的倍数可不是那么多，那么我们看快速排序法的80万个数据，它耗时多少呢？走。哦，我们看。我们看一下它这个是还是零秒，感觉好像是不是没有排斥的是吧。是不是他真的没有拍啊？他肯定排了啊，说老师真的，我怎么掉了呀。肯定排了。啊，我再增加。这已经到800万了啊。如果800万还是零的话，我们就要怀疑是不是真的没有牌。排了，确实排了。800万绝对是拍了的啊。你果真走了的？这没问题呀，还是一样的呀，取值等称式，而那点这个嘛，肯定是排过的。人要不相信我随便改一下，肯定是我，我把它打印出来看一下，他不敢打啊，算了，别打了。

走。走。这次肯定这次没有零秒了，至少一到两秒的样子。肯定要耗时了三秒。排了的啊，绝对排了，那么你看800万个数据三秒，那如果是800万数据，你给你调到那个调给那个最快的插入排序，你们可以想象它有多少多少秒时间，看这个三秒四秒啊，我这还有点，因为我的机器可能性能不是很好，八万八百万数据两到三秒，那么我们来分析一下，为什么快速排序法它就快呢？好，首先我要告诉大家啊，千万不要以为你的快速排序法，它是在同时排，没有。没有同时办。因为你你们可以看到它的代码呢，仍然是按照这个递归的方式走的。也就是说他其实也是一步一步做的，你看他进到这里面，他就往里面不停的追，追追追，往里面追，是不是这个道理，然后呢，等他把左边地归完了过后，他才去地归右面的。

是不是道理，也就是说并不是像我们想象的是同时在排，没有，那么为什么他没有同时排，他仍然这么快呢？原因，注意听。它是这样子的，你们要搞清楚它排，进行这个快速排序吧，它这个排序的它的逻辑是什么。他逻辑是怎么走的，来打开这个图，它这样子的，就以我们我们为例啊，这个不要看了，以我们上午讲的那个为例。快速排序法，它是这样子的。他呢，先找到中间一个字。然后。它首先第一点是他从这边扫描，这边同时也在扫描，扫描的时候两个同时交换。这一下就比以前那个比以前传统的方法要快很多了，你以前是找一个。

然后就怎么怎么样，他现在是两个同时找到，找到过两个一交换，这光这一个就省很多时间，第二个等到他扫描完了过后，他这一半呢，这半呢，这个逻辑又在进行，这样子又在这样子减半，也就是他的整个这个比较指数是在没没没扫描的一个一个一个中轴的时候，它是按一半的这个一半这个这个方式在减少比较的次数。这就很猛啊。也就是说你们以前那个像插入排序法，它总是找一个往里面排，找一个，那么它它插入一个数，下一次呢，就减少一次的一个一个一个比较，是这意思吧，就说你比如说我们按那个选择排序法来说，选择排序法是怎么找的，他是先找。零到N减一，最小的，最小或者最大的数给它填进去，然后呢，填完一个数过后，它比较的下一次比较的次数只仅仅是减少了。

一次而已。等到它再去，再去查出第二个最最大或者最小数过后呢，它下一次比较次数又在减少一次而已，但是我们快速排序法不是这样子的，它是这样子的啊，他先把这个地方。找到过后。一零取位，取位过后呢，这边折半，折半过后呢，虽然他还在比较，但是它仍然是按照这个两段两段的进行交换，所以说他每次呢，是按这个一半的这个方式来减少比较次数，所以说。他这个递减的，递减的速度会很快。递减速度很快，所以说它的整个这个效率呢，就会很高。OK，所以说它的原因是因为根本原因就是减少了。比较和交换的次数，它是减少了这个东西，但是呢，他这个对程序的耗费的资源也是很厉害的，因为他开了很多的站，那么每开一个站呢，都会吃掉一些资源，所以他耗费资源会比较大。

啊，所以说你可以看到，待会儿如果我们打开这个任务管理器，你让我再来运行一下，你会发现它的CPU，还有这个内存呢，会耗费的比较厉害，我们来看一下走。好，同学们可以看到你看。你看刚才已经称了一下，到了60，现在基本上维持在50左右，CPU利用的还是很很很多的，因为他不仅在开这个站嘛，但是如果我来我我来用这个选选择排序法，你们来看看选择排序法它的这个对CPU的耗费率啊，我们看看它又是怎么用的。好，Go run命点，够跑一下。你看。诶，他也上去了一点是吧。你看他。它还是维持在40左右，你看也也就40左右，30左右，它它并不像那个快速排序法耗费那么那么厉害，说他对CPU的这个耗费呢，相对来说并没有快速排序法啊，那么呃那么多，因为它是它这个是没有开战嘛，好，这个原因呢，我就给大家分析到这里啊，大家再去体会一下，就是要理解。

这个快速排序法，它快的根本原因就是它减少了比较和交换的次数，而且是按这个除以二的这个倍数递减的。如果说如果说别人跟你讲说快速排序法，是不是因为同时在排，不不是这样子的，如果同时排的话，那就更快。如果你有一个能力啊，你让他给我们开携程，就是把这个快速排序法结合携程来做，那这个速度还会提高。但是但是有一个问题，因为一个数组它有它有这个锁的这个关系，它同步，所以说应该也很难做到，但是你们可以去玩一玩。啊，可以可以想办法去玩一玩啊，我我没去玩这个东西啊，因为你几个，比如说四个学程同时去排一个数组。

但是呢，这个系统里面他要对这个速度进行加速，所以当有一个携程在操作的时候，可能另外一个携程就操作不了，但是也不一定，我没去试过，如果有同学有兴趣，可以说我把这个数组看成呃，就是让几个学生同时来排。你看看能不能把它搞定啊，你可以可以去试一试，那效率就会在这个系统再增加，好了，同学们，那关于这个就是排序的一个效率问题呢，就给大家啊讲解到这里。