367_尚硅谷_Go核心编程_数据结构和算法-快速排序法.avi原创

好，我们接着那个刚才讲的这个插入排序呢，接着往下说。那下面呢，还有一个排序法也是需要大家掌握的啊，还有一个排序法也是需要家掌握的，什么排序法呢？叫快速排序法，叫quick shot。那么这个排序法呢？同学们先看一下它呢？它实际上是对冒泡排序的一种改进。他的思想。就会用到我们这个递归，它会用到递归，它什么意思呢？大家看一下它的基本思想是这样子的，通过。一趟排序，将要排序的数据分割成独立的两个部分，就每一次先把它分成两个部分，其中一部分的数据，所有数据都比另外一部分的数据要小。当然也如果是你是从大到小，或者从小到大，你这个不一样的情况，你比较条件可能发生变化，然后呢，再按此方法对这两部分数据分别进行快速排序。整个排序过程中可以。

递归。进行。以达到整个数据变成有序数列。那这句这话说完了过后，大家可能也不是很清楚他说的什么意思，所以说呢，我这里画了一个图，这边有个图帮助大家理解，大家看一下这个图，这个图呢，还是比较清楚的，把它这个关系理清楚了，但所以先看到啊，它以11为基准，它以这这个图呢，它是以最后这个数为基准。但是不一定每每一个都是以这个最后一个数啊，比如说待会儿我们看的这个案例呢，我是以中间这个数。为这个中中轴，就是以它为这个支点进行分，进行这个分割的，那么如果它是以这个11为为基准分解，它是怎么分解呢？他先把11比11小的数，它它这边是从小到大排啊同学们看它是从从小到大排，它会先把比11小的数扔在这个11的这边。

但是注意听这句话啊，并不是他把这个扔小比11小的数扔到这边过后，这个就是一个有序的，它仍然不是一个有序的。他没那么强大，就说它只是只能把比11小的扔在11的左边，然后呢，比11大的扔在11的。右边因为它是从小到大牌嘛。那么紧接着呢，它进行这个分解，他又把这个呢当做刚才的一个思路，又以这个最后的一个五为这个基准，也就叫为为轴点，然后呢，比五小的人在坐边，比五大的人在这边，然后再把这个分割好的过后呢，再以这个八最后这个数为基准，然后比八大的又怎么分到比八大的分在八的这个。呃，右面比把小的分在左边，因为没有了它就不分了，这样子就会二五八二五八十就出来了，同样这边呢，也是一样的道理。

它总是这样做的，那么其实整个过程呢，是一个递归的过程，这个理解起来就比刚才咱们前面的选择和插入呢，要困难很多了。因为这边用到了很多递归，它用到递归了啊，那么我们看一下这个代码它是怎么实现的啊，它代码是怎么实现的，我们看一下。那么根据刚才这个思路呢，我这个待会儿我们做这么一个案例，什么案例呢？大家看到这有一个数组。有六个数，然后呢，我们要求从小到大排。我们要求从小到大排，注意啊，我们就按它的这个思路从小到大排，那么要求使用快速排序，要求使用快速排序，那么这段代码呢，它在这里，我们先来看一下它大体是怎么实现的，来同学们看一下啊，然后呢，我们把它给它做一个说明，那新建一个文件夹叫。

Quick。Quick shot，然后呢，我新建一个文件叫命顶购。A就叫main.go。OK，然后呢，我们打一个包，Package主包，对，然后呢，Import。For mind，然后我们写一个主函数。好，那同样我们刚才把这个数组呢也写过来。R等于好，然后呢，我们这个数组是六个元素，六个元素。走一个。啊，这个一个元素直接往这写就可以了，我们看是哪六个元素啊。啊负九啊负九，那么先把这个放到这儿啊，先把这个放到这quick。好，放到这儿，我们先把这个数组也粘过来，有这么六个数，我们待会儿看一下的效果。

好，我们把它这个逻辑给他讲清楚，来看一下负九。负，九七十八零二十三，负。五百六十七七十，我这些数据都设计都是有道理的啊，待会可以看到一些效果，然后呢，它是怎么来做的呢？看一下它的代码。它代码是这样子的，这个就是快速排序。啊，快速。啊，快速排序，快速排序，我们首先看它有这么三个变量，一个是left。就是。代表你这个进行排序的时候，你的数组最左边的下标是多少，我这做一个说明。啊，做一个说明。啊，第一个呢，大家可以看到这个left表示数组最左边的下边，当然它如果是在往里面这个分割的时候呢，就是小块的数组的最左边的啊，它这个是不停的变化的，表示数组左边的。

左边的下标，对左边的下标。那么同样这个。这个这个right呢，表示数组右边的下标。哎，没问题，那么紧接着呢，这个三，这个三就是你要进行。这个进行排序的这个速度，而且呢，用的是指针类型，对这个是A，这个A就是表示要对表示要排序的，要排序的。排序的这个数组。好，然后呢，大家看到上来过后呢，做了个L和R，那么把这个是先付给它，付了它过后呢，这个地方大家看到这个，呃，这个这个这个中轴啊，这个palet palet它这个是干什么呢。这这个它是找到这一个中间的这个数。哦，找到中间这个数，所以说这个地方。

Pit是一个中轴，这个呢，翻译成这个英文就是中轴的意思。中之中轴啊，这个轴。中轴。哎，中轴。哎，这个轴是这个轴啊，中轴是欧轴，还没有这个轴呢。对，这个中轴啊，中轴，那么它也翻译出来也叫支点，有些有些地方翻译出这个英文呢，叫支点。支点就说它相对是总感觉就是以这个地方为中轴开始左右分，那么你也可以认为它是个支点左右分，那么这个时候呢，大家可以看到它是找这个时候我我们这用的是left加right除以中间，它是相把中间这个数当成一个支点。啊，把中间这个数当成一个支点，然后呢，这个temp是个是个临时值，下面看这里面逻辑啊大家看，那么这个地方怎么理解呢？这个地方是L小于R，就代表我只要这个L小于这个R的情况下，我就不停的去进行这个找，那么for循环结束以后，它的目标是干什么呢？是要把底这个这个中轴的这个是p pit啊，这是pit是吧。

啊，还是啊，就是比这个数。小小的全部扔在左边，比这个数大的在它的右边。这个负循环的目的，目的是先写到这。For循环的这个结果或者目标。目标是将比。这个PTPT的这个小的比。比这个小的数。小的数放到放到这个左边。

左边。哦。左边。好，同样他要还要把比这个pit大的数呢放在右边。那么他是怎么放的啊？注意看这句话。比大的数放在它的右边。它它是怎么放的呢？大家看它是这样子的，大开这边一一步走，只要我这个L小于R，我就不停走，什么时候我算是结束呢？就是你这个L要么大于R，要么等于R，我就算结束了，因为它是两头走。那这句话呢，大家看到这句话是大家看什么意思呢？就是说他要从这个PT的左边找到一个比它大的数，这有点不好理解，因为你要交换嘛。它是怎么交换的呢？他是这样子的。先从。先从这个pivot的pivot的左边。

左边找到。啊，注意啊，找到比找到大于等于。大于大于等于。这个PT的一个值。你看啊，是不是这意思，就是不停的找，只要你这个左边这个数小于它，我就不停的找，我就L就加加加加加加到什么时候呢，我要找到一个比你大或者等于的数，我才停下来。那为什么这么干呢？大家看他这样做的目的，我我还是还是把这个数组拿过来啊，这样不拿这个数组很难讲清楚，那么我把这个数组先放到这来。好，这个这是我们这个。要进行排序的这个数组，它现在相当于是这样一种感觉，把它放大一点。现在你要理解成它有两个指针，一个是左边的指针，一个是右边的指针，它现在现在他先找到哪一个字呢？找到中间这个指。

也就现在这个P就是零。那为什么它是零呢？你想一想嘛。因为你这边传这边最左边是零，这边最右边这个呢是呃，应该是几呢。应该是五啊，零加五除以二。等于二二点多，然后呢，取整就应该是二，所以说它中间这个值P的相当于是零，那么零它怎么做呢？它先从P的左边找到一个大于等于P方的值，那相当于说现在呢，他就找到了。这个值。78。诶，他先找到这个78，他找到78的目标是干什么呢？各位同学，他找到这个目标就是希望在从右边找一个比它小的数，然后两者交换。啊，两者交换，那接着我们看他的思路，他下面的思路呢，因为不同的快速排序法，它还有微小的差别，明白我意思吧，就说说韩老师讲这个爆泡的这个快速排序法，你可能在别的地方你会发现，诶好像跟我有点区别。

这是有可能的。因为它思路只是一样，就说你要完全一样也不一定，比如有些地方他说是等号，下面就会有变化。好，所以你先看我这个思路，看我这个思路啊好，那现在呢，这一头，这一头又是什么意思呢？我这写的什么意思呢？先要从，再从这个标题，先从啊就就从吧，这边是从PT的右面。右右右边注意听啊，右边找到一个小于等于。因为你大于嘛，那小于小于等于。这个P的值。啊，比如如果找不到我就二一直减减，那也就是说如果根据我的情况下呢，大家应该领回到这边还有一个指针。他要找到一个小于这个零的，显然找到了。567负的567。

好，找到这两只过后呢，同学们看，只要我找不到，我就一直找他说老师一，如果一直找不到是什么意思，一直找不到那说明。已经达到目的了，就不要再找了。如果你发现，诶，这边零左边这个数全都。全都比他大，那不就已经达到目的了吗？对不对，所以他是这样子的，好，那现在你像一听找的话，找找找好最后就找到了，找到一定会找到，找到过后呢，他做了一个判断，如果这个L大于等于R，如果这个L大于等于R，说明他们已经找到了，已已经一一直扫描扫扫扫扫到中间了，那说明已经把这个就就完成了。好，所以说这地方呢，如果是如果满足这个条件，说明我们这个，呃，就是两头分割的这个任务已经怎么样完成了啊，说明说明这个如果L大于等于R。就表明表明这个任务完成了，任务完成就针对这一次的这个分割啊，针对这一次的啊，表明。

表明。表明。本次。本次这个分解任务，分解任务完成，那么我就干什么呢？我就break。好，那如果说没有达到效果，那说明什么呢？那就交换，那交换什么意思呢？这样子就会产生一个交换的动作，这个交换呢，咱们可以也也直接写成写成这个一句话啊，这我还用的是传统的交换方式，大家可以把它改一改，这个就交换。那如果是交换，针对我这边来看呢，其实就是78和负的负的567交换，也就是说如果这样子的话呢，这边就变成了这个德行。它就变成什么样子了呢？大家可以看到。就我我不动，原来这个东西啊，相对于说78。变成了负的。567，而我们的这一个负的500负，负的这个567的位置变成了78。

他交换了吗？那这样子不就说已经达到一个效果是什么呢？就说这个小的扔到这边，大的扔到这边来了吗？对是这个意思啊，然后呢，这个你这个做完了没有呢？没有做完，因为你有可能后面还有这个数对不对，所以说他又把它做完了，过后他又去判断。他又做了一个判断，说如果PL等于这个的话，如果等于的话，我可以再往前面再冲一步，啊，这个是相当于是优化了一下，又做了一个优化。再优化就是因为如如果说啊，就说你交换完了过后，你会发现诶，他们两个还相等，那说明下一次就不要不要再比较了，因为它已经等于它，因为相等的情况下，我们也不交换。就这意思啊，相等情况下也不交换优化了一下，好整个地方做完了以后，接着再来看你这个LLR小不小，如果不小于我就继续，我就继续这个指针，因为你指针到这了，继续往下面这边我这边移动，这边我这边移动啊，当然我这个数因为比较少，看不出来这个效果了啊，你原来在78就继续移动，那么仍然跟我们这个零进行比较，因为你。

刚才只交换了一次嘛，那有可能还有还有第二，还有第三个你输出很大吗？所以说呢，这个地方就相当于说继续比较好，整个这个for循环结束了，注意听啊，整个这个for循环结束以后，大家应该想到一件事情，什么事情呢？就是你的左右两边已经搞定了。就针对这一次左右那边就搞定了，那有时候同学说老师是不是这样的，我可以把它注销，我们看一下。就说如果啊，同学们，如果我把下面的代码注销，大家可以可以准确的体会到，我们输出来数组就应该是负的，负九负。567023 78和70，看一下这个效果对不对。那下面把这个理解了过后呢，你就知道下面的代码是什么含义了，不然你看不懂这个代码。你看不懂，这这个我刚说清楚了啊，那现在我们来玩一把，看看是不是这样子的啊，同学们注意听。

好，我们调用一下快速排序法，注意听讲啊。调用。快速。快速排序，但大家看那因为这边呢，它是呃左和右码，那那肯定左边最早应该是零，右边最早是它的长度减去一个一对不对，所以说呢，这个quick。我们就可以这样来玩了。走，然后呢，我这边传了一个零进去。传了一个零进去，然后它的长度呢，就是它的数组的长度怎么样减去一个一，因为它下边呢是长度减一，紧接着把这个数组本身传进去，好传进去过后呢，各位同学我们来看一下它的效果，我输出啊同学们我就直接在输出，大家看一下就可以了，因为它这边还没涉及到递归。说说我直接输出。好，我们看看主函数里面的啊，就是就就这样写，写到这吧，大家看主函数里面的，因为我是呃引用传递，所以说它是可以变化的。

啊，我写个me。好，我们来看看整个这样排序完了过后，是不是跟我们想象的分析的一样，是不是变成了就是78和负的，呃，567发生交换，因为你这个23不交换了，23本身就比零大，而且他这边也找不到了，它就它就停下来了。啊，如果你如果说这边找不到，这边还有怎么办呢？他就会把这个中间轴进行移动。啊，因为它它现在跟中间组进行变化了，好，那现在呢，我们来玩一把，看看这个效果对不对，保存一下啊同学们看。把这个理解大家都好，下面就好理解了。CD点点到我们的quick short go run。命，点歌走。好，我们看效果，同学们看，这个跟我们分析的是完全一样的，你看啊，它原先把圆心给你打出来，先把最早这个打出来啊，不然你理解不了，好，这个是最早的初始的。

初始的数组呢，打印出来大家看一下。跑起来。跑起来，我们看原先最早的时候是。这样子的，现在呢，78和负的，呃，561进行交换了，它变这儿来了，它变这来了。因为这个23是本身大于它，后面这边也没数了，就退出了，第一次就搞定了，但是你这样搞定没有意义。为什么没有意义呢？因为你这个零左边的这个地方。仍然不是从小到大，同样你零右边这边他也不是从小到大是不是。你你因为你本身你你还得保证这里面的这个它的小这个数字里面人要保持这个规律，那怎么办呢？最经典的写法就是一个什么呀。这样的写法，大家先看这段代码，能理解这句话意思就是说我向左递归，如果我把这个打开，那么它就能保证零，左边的应该递归下去，就变成一个有序的了，这个是向左递归。

但地位条件也是要满足，Left要小于二，如果你left不停的变成，因为它里面传递嘛，不停的往里面传，最后left就有可能变大。变道后，如果它大于R的宿命就不要在，不要再玩了，这是向左递归。向。向左。左左啊。左递归。好保证左边的A是这边呢，肯定是向右递归。向右递归。向右递归，保证保证我们这个右边的也是一个有序的，因为它下去过后还要继续分割啊，大家要理解好，那么我们来给他打开看一下是不是这样子的，我先这样子啊，我先只保证一个向左递归，把这个打开，这个地方是什么意思呢？同学们看啊，这个地方也是做了一个处理，就说如果你如果你这个地方交换完B过后，L和R的还相等，那就再错一位啊，这个这个再错一位就再再移动一下，如果。

如果这个L等于R，说明这次就说这个不用再比较了，再再错一位，再错一位，再错一位，再移动一位，再移动一位，这次就不要再比较了，再移动一下。移动一位。一位。啊，移动移动下。好，那么现在如果我这样打开过后，同学们可以分析一下我们这个代码结果是什么，我我给大家看啊，我给分析出来它应该是这样子的，就说零。这边就是它的这边会变成一个有序的，但是这边仍然是没有动过，因为我是只往左边进行递归了，那么这边处理完了过后，它应该是这样子的。负的。它应该变成这样子啊，如果我的代码没有变化的话，它应该是只动了。啊。它只动了这个零这边，那么这个边就变成了负的567567，而这个呢，变成九了。

因为它能保证它是一个有序的，就它保证了右左边这个是个有序的，因为我的数据量比较少啊，所以大家看这样子，但是这边没有动了。这边仍然是保存二三七十八和70，因为你没有向右递归，你没有向右递归，所以说当我这样处理完了过后，你们可以马上看到一个效果，就是这个结果，就是刚才结果，就是老师分析出来的这样一个结果。好，我们看代码这样子对不对啊，来同学们我们执行一下，看我们分析到底有没有道理，因为这个东西一讲，大家应该还是很好理解的啊，很好理解走来跑一个你们看一下效果。好，同学们可以看到这样的处理过后呢，你会发现它处理完了过后变成这个了，果然是保证了它零左边的是一个有序的了，同样右边也是一样的道理，如果我把这个打开，那么它右边也是一个有序的了，那右边有序，那说明两个都是有序的了，看代码。

好，同学们看右边也打开了看这边同学们可以看到诶，二三七十七十八，原先是二三七十八七十，这边是二三七十七十八，其实就是很简单。但是你要说往里面一一步一步的把它分析出来，还是不太不太好分析的，因为它是递归，你这个画图不好画了，就只能这个时候要需要一点点想象的能力。想象能力，还有这句话呢，呃，就是同学们要注意啊，这个要加上，不加上它有可能是一个死的递归，为什么呢？因为你如果等相等的话，你不移动，它一直卡在那个地方的，动不了，它一比较相等它，它就它就卡在这了，所以说这个地方这一句话是非常重要的，因为你你相等，你不移动，它一比较又相等，它就卡在那边不动了，因为你这方是你是这样一个条件，所以说这个地方是必须加上，你不加上啊，你把这个去掉，你会发现它是一个，它是一个死循环。你看。他会死在这个地方。

你，你看死了没有。你看他死了没有？他为什么还没死啊，死了。你看他一定会在这个56行要出现一个大问题。啊，所以说这地方是不能乱动的啊，56行其实就是在它向左递归的时候，发现一个死龟，因为它推不出来，因为他这没有发生一个减减和加加，它卡这了啊说这地方这句话呢，大家要去好好的理解一下啊，要需要一点想象的能力，好，那这个呃，写完了过后呢，我们来看看把数据量扩大一点，他这个还是不是对的啊，他是不是对的，因为我们毕竟只是把这个逻辑给他讲了吗？逻辑讲了，那现在他到底行不行呢？我们把数据量扩大一点啊来同学们。好，我把这个数据量扩大一点走，呃，负123。90。负的23是二百二的20，负的23，好，现在一共有九个数据。

把它扩成九，然后呢，我在这边也把它扩成一个九，大家看代码对不对。好，我们玩一把。好，我们玩一把，好我们发现呢，是没有任何问题的啊，没有认为是从小到大，那有些同学老是我不想从小到大，我想从大到小应该给哪个值呢？同学们可以看到，其实关键点就在这个地方。哎，你把这个改改一下就可以了，就是你因为你是你是你是从左边找到最大的，那反过来就是找一个反过来找吗？是不是反过来找，那就说从左边找到一个小于等于它的再交换不就是反过来了吗？那就是说只需要把这个改成这个符号，把这个改成这个符号就可以，一样的道理。因为我刚才把这个道理已经讲清楚了，对对，如果你这样改的话呢，就相当于从左边找一个比它大的数，再再再去再去交换啊好，那看这个时候就应该是从小到从大到小。看这个对不对呢，我们发现是没有问题的，看是是正确的啊正确的好，那我还是把它改回去啊，因为我代码呢注释呃，就配不上了。

好，这个是小于啊，同学们看。好，这个理解起来呢，有一定难度。有一定难度啊，还有一点就是这个周呃，中轴支点呢，你也可以不用这个中间，但是一般来讲用中间呢会效率高一点啊，效率会高一点，好了同学们关于派快速排序法的一个一个讲解呢，我就先说到这儿，大家呃，大家看看就是其实也不是很难。就是这个东西也不是很难，就是需要一点想象能力，就是我已经把这个就说把这个去掉，当你看不懂别人代码的时候，我教大家一个方法啊，我叫他我我一般是怎么样呢？就是如果我看不懂别人的代码，这也是很正常的，因为有些代码确实很难，我我一个最简单方法，我就是把这个看不懂的先。注销掉你看不懂吗？你你干脆不看嘛。

诶，你把它一注销你就发现哦，它原来就这个数，好下面的你就相对容易理解了哦，它的意思就是一个向左向右，那么向左向右不是又相当于把这个代码又执行一遍吗？哎，不是又是那样分割吗？诶进去过它又再往下递归，不是又把那个小的再进行分割吗？以此类推啊，以此类推，好同学们，我把代码整理到这里啊，同学们。好，我把这个代码给各位同学整理到我们的笔记中去，那这块呢，就是我们的快速排序的一个实例，刚才我也讲了啊，左右取消左右是这个结果，取消右递归这个结果，取消左递归是这个结果，我们证明了一下他的观点。好，同学们，我把快速排序法的一个应用实例，包括它的一个讲解给大家整理到我们的笔记里面去。呃，这个快速排序法呢，你。啊，我先把它整理到这里，同学们好，这是标题三。标题三，快速排序。

那么快速排序它到底有多快呢？我们一会儿可以整一个试验啊，可以这样说，800万的一个数据，800万的，800万的一个无序的数组，只需两秒。全部拍完。只需两秒，它可能不是世界上最快的，但是它已经非常非常快的了啊，只需两秒，800万的一个无需的速度，只需两秒什么概念？大家可以想象啊。那如果说老师，那如果800万的这个无序的数组用冒泡会花多少时间呢？你可以直接去吃饭了啊，吃完饭回来他还在排啊，就就就就这个区别，好，我先把它整理到，待会儿我们再做试验啊，好，然后呢，这是快速排序法的。一个示意图啊，这个示意图呢，还是比较重要的，同学们。好，这个这个还是比较重要的啊，来，我把这个示意图呢，给大家放在我们的笔记里边去对。

好的。好，然后呢，快速排序法的一个应用实例，诶对一个应用实例，我们也把它整理到这里好吧，诶OK。好，然后呢，我们把这个代码给大家整理到这里。好代码实现。快速啊快速。排序。排序。排序法的一个代码实现。好的，我也把它整理到这儿啊，同学们。那么快速排除一下代码实现呢？呃，因为这个呃，代码里相对比较多一点，我就直接给它放到笔记里面去了啊好的同学们。放到这里来。好，那同学们关于这个快速排序的这个讲解呢，就给大家介绍到这里。