day07_数组/16-尚硅谷-Java语言基础-算法：快速排序的说明

行，那这个冒泡排序完了以后呢，诶，咱们再往下看一下，下边呢，我这又放了一个叫快速排序。哎，快速排序，这个快速排序呢，我们那会儿也提到过了哈，诶它的典型的特点就是快，所以干才这个名字就叫快速排序啊，这个比其他的这个排序方式呢都快啊，这也是咱们这个计算机底层，通常呢，咱们如果调一些现成的排序方法，通常呢都是使用的叫快速排序了啊，然后这个快速排序呢，也是列为20世纪呢十大算法之一啊，你可见它的地位还是很高的啊，而且呢，呃，发明这个算法的这个人Tony是吧？诶他呢还获得这个图灵奖了。哎，就是这个算法呢，确实是很经典的一个算法，好，那么我们下边就来学习一下它的这个经典是吧？哎，涉及到这个排序的一个思想啊，这块呢，我们就详细的不说了，嗯，这个关于快速排序呢，嗯，我就带着大家呢，把这个代码呢简单看一下就行，关键呢，就是咱们先把这个排序的思想呢，稍微捋顺一下啊，你看人家是怎么设计这个算法的啊，对于真正这个做算法的这个人来讲，其实他们本质更像是一个数学家啊，只要你把这个算法的思想都描述清楚了，剩下的写的事呢。

随便找个程序员都会写啊，就是这种的哈，你像我们这个大这个读研生的时候，在实验室里边就都是就是呃，导师这块呢，带着博士，博士呢就是看一些论文啊，做一些研究啊是吧，然后呢，有很多的一些项目数据，呃，想好怎么做以后呢，咔，抛给这个硕士生写去吧，是吧，哎，就干一些体力活啊，当然了，慢慢的这个想读博的这些人呢，慢慢的你也得诶读一些论文是吧，读这些论文，然后你开始这个不管要能够去写这个代码，你也得去多参与点这样一些算法的一些设计，是吧，就是这种啊。所以呢，你会大学看到很多计算机系的一些导师啊，有可能大家很多都是计算机系的哈，你就说哎，我们学院的这个导师都不会写代码啊，你感觉一脸鄙视的感觉是吧，真正这种大师呢，可能还真就不会写代码啊，就是他更多的研究的是一些算法层面的东西了啊，那在他们看来，这个写代码的工作不就是一个体力活嘛啊，你找个成员，找一个学生去写就可以了啊，属于这种啊。

好，来看一下这个叫快速排序哈，嗯，这样看啊，这四个看完以后呢，看这仨这个快速排序它是这样来设计的，呃，从五开始，一直到后边这个七，这是我们要排序的这个数组啊，首先的话呢，我们定一个叫por啊，就选一个，选一个值先啊，这个值的话呢，其实你选这里边的任何一个都可以，只不过呢，我们不妨呢，就取第一个了，我取第一个以后，后边呢，我定义两个指针。这个P的后边这个我叫漏。然后呢，从最后往前这个叫氦，一个低指针，一个高指针啊接着要接着的话呢，我这个漏呢指针不断往右走，然后这个氦的指针呢，不断往左走，这个漏的指针我们要求它指向这元素呢，一定要比我们这个一开始你指的这个p word上呢要小，而我们这个氦指的指针呢，要比我们这个大，诶比如说第一项二小小就接着往后走，就走到九这儿了，然后这个七呢比五大好，就往前走，走到五这，五这呢跟他一样啊，就不用管了啊，再往前走，走到一这了。

也就是说呢，呃，你就从前往后走就就完了，直到什么时候停止呢，就是首次出现，对于漏来讲啊，首次出现的比五大了啊，对于氦来讲的话呢，首次出现比五小了，这不就出现这个位置了吗？对，出现以后的话呢，我把这个一跟九呢对调一下，说白了就是我们想把这个P过，找完以后，我想把后边这个呃数组元素呢P成两半啊，一半呢是一，呃不一定是这个1/2 1/2的关系了啊，P成两半，这一半呢是比五小的，一半是比五大的，就想做这个事儿，嗯。

到九跟一这这不交换了，交换完以后呢，这个漏呢，再往后走，出现三没事，出现八了，八这停一下，然后这个九往前走，零零不用管，四也不用管啊，零零用管了哈，到零这的话呢，你这个0比5小，所以它俩呢再换一下。哎，这不是交换了，交换完以后呢，我们这个漏再往后走，4比5小哈，再往后走，走到八点停，然后这个氦的话呢，呃，它本来就在八呢，它往前走，往前一走呢，发现正好比五这个还小，上到这也停一下，这个时候呢，我们出现它俩呢，本身应该漏不能大于这个，Hi，结果发现大于了，那这呢，其实也是我们这一轮循环的一个终止了，相当于你从今往后呢，大家该便利的就都便利过了啊在这个位置的时候。这个高位这个就不用管了，那就大就大了，然后这个氦呢，本身比这个五还小，那这时候我让这个四呢跟五交换一下。交换完以后，我们五就出现在这儿了，五的左边都是比五小的，五的右边呢都是比五大的，或者不不小于五的。啊，是这种情况。

好，那就相当于我们这个经过一轮以后，这个这个数组有可能很长啊，经过一轮以后呢，其实我们就把它劈成了两半啊，一半呢是这块，一半呢是这块，然后接下来怎么做呢。接下来你就把这个把这个看成是两部分两个数组了啊，我再针对于前面这个数组呢，我再诶定义一个漏，定一个氦，哎，再这样走一遍，然后这块呢，也选其中的一个元素，再取它后边的叫漏，这个叫氦，哎，这块呢，独立的再去运算一下，这个再去运算一下，运算完以后呢，这一半是不是又劈成两半。这个A劈成两半，然后再劈两半，哎，这个速度呢，为什么快呢，你像一开始是有一个111个数组，然后呢，一一轮完以后呢，变成俩了，然后再来一轮以后呢，变成四个了。再来一轮呢？是不是八个了，一变二嘛，乘以200，那不这相当于二的平方，下边是二点三次方嘛，哎，如果你这要很大的话，二十四次方，五次方，这不是其实很快的就把这个，呃，你要比的这个数呢，就摊的很细了，这呢又是一个指数级的。

哎，所以它这个增长的很快，那进而这个排序起来呢，速度也很快啊，你看我下边又放了个图，那那这是原始的这个数组啊，然后呢，49放这以后第一趟完了，这不是一个又变成俩了，再来一趟呢，这个这个又变成俩，这个又变成俩，然后下面呢，再去两个，再往下拆拆，哎，它其实每一次呢，就跟这个细胞分裂一样。一个细胞变成俩，俩变成四个，四个变成八个，然后这个快速的这样去去分裂它到后边的话，越长越快，越长越快。哎，你这个速度要是很大的话呢，其实很快的就给你弹成到一个元素的时候了，所以它的效率很高。啊，效率很高啊，诶详细的这个算法呢，就不带着大家去写了哈，你要是想关注这个具体的排序怎么实现，给大家发的这个资料有个salt salt里边呢，呃，这个对象这块呢，咱们还没有讲啊，先不用看它讲完面向对象以后呢，你再看，这是考虑这个稳定性的情况啊，然后关于这个整数型的数组排序，这个你打开这呢，我就列出来了，我们这诶实用排序，实用排序里边呢，关于这个快开叫quick s，对，你把它打开或这呢，我就不开了，直接把它呢CTRLC一下。

粘过来。粘过来的话呢，这个名这块有点问题是吧，改成一个Java啊。好，呃，这呢就是咱们这个叫快排的一个实现，下面呢，这不还有个例子，这是这个数据啊，排之前，然后呢，Quick so排之后，这呢，咱们涉及到方法了啊哎，咱们下一章来重点说这个面向对象的方法。嗯，核心的代码呢，就是这块啊。哎，就这块，哎在这里边大家可能会发现一个问题，尤其是可能预习过的同学就知道啊，这一个方法，我们在这个方法里边呢，你看自己又掉自己了，哎把这种自己吊自己的这种呢，我们称作叫递归方法。

啊叫递归调用，哎，后边的时候呢，我们呃，再提这个问题啊，哎，这就是快排的一个实现啊，就不带着大家看了，大家呢，也不建议你现在去研究它哈，这个等到这个后期找工作的时候呢，哎，你可以再看一看啊，你叫突击也行，叫怎么也行哈，应该说叫复习啊，就是大家呢，以后哪怕说你这个真正工作过一两年了，然后后边你想换工作了，那大家呢，通常也都是，比如你这个工作你给辞了，辞了以后呢，想再找工作，最好呢，也是先复习几天啊，你其实有好多问题，你开发中不用的啊，你再找工作呢，还得需要熟悉熟悉，像这种快排啊啥的肠挨考的，那你就得看一看啊好，呃，那关于这个快排呢，我们就说到这儿啊。