我们这几位排序算法的大咖，压轴的BOSS，快速排序——正式出场！
问题
使用快速排序算法对列表中随机生成的10个数据进行从小到大排序，即最小的数字在最上面，最大的数字在最下面。
分析
快速排序是我们讲解的这几种排序算法中最优秀的一种，当然理解起来也更困难一些。它的基本思想是，从要排序的列表最左端选择第一个元素为基准，经过一轮排序，把这于这个基准的元素移动到基准左边，而大于基准的元素移动到基准右边，这样，这个基准元素把原来的列表分成了左、右两个分区，左边分区都是比它小的元素，右边都是比它大的元素，那么它的位置就已经排好了；然后呢，我们对基准元素左边的分区和右边分区分别再重复上述操作（就是再选择各自的基准，把数据分别放到它左边和右边的过程），并且以递归的方式调用下去，每一轮排序都会使一个基准元素放到正确的位置上。当所有的分区不能再划分的时候，排序完成。
这个过程的确没有冒泡、选择、插入那么直观，我们还是请出五人小队，通过实例来感受一下吧。
这次老师和鸭子想改进一下排队的方法，毕竟他们试过了三种排队方式了，还没找到特别满意的。他们决定从两头同时进行。在排序刚开始的时候，老师（蜻蜓）站在最左边，鸭子站在最右边。他们商定，就以第一位欢欢为基准，第一轮要先给欢欢找好位置，让所有比欢欢低的都站在他左边，而所有比他高的都站到右边去：
鸭子的任务是从右向左寻找第一个比基准（欢欢）低的同学位置，只要找到就先停下来，他发现他站的位置上图图就比欢欢要低，所以他就站在图图的位置不动了；而老师就没有这么幸运了，他的目标是从左向右寻找第一个比欢欢高的同学位置，直到找到最后，图图的位置上，也没找到谁比欢欢高，于是鸭子和老师站在了相同的位置上（最后一位同学图图的位置）：
这个时候，整个队伍都被老师和鸭子走了一遍，相遇在图图的位置，这个位置就是欢欢的合适位置，于是欢欢和图图交换了位置，第一轮排序就结束了。此时欢欢把队伍分成了两个分区，左边是比他低的，右边是比他高的（当然，没人比他高，所以右边的分区是空的），下面我们只要对左右两个分区再分别执行上面的操作就可以了，老师和鸭子站在了左边分区的两头，基准选择是图图：
历史总是惊人的相似——鸭子又一次偷懒了，他站的位置就是第一个比图图这个基准低的同学！而老师呢，又一次不辞辛苦地走到格格的位置也没有找到比图图高的同学：
和第一轮一样，让图图和格格换位置，第二轮结束，图图再次把剩下的队伍分成了左右两个区，左边都是比他低的同学，右边都是比他高的同学（当然，是空的，欢欢不属于这一轮的范围）。图图归位，老师和鸭子再次站到第三轮的队伍两头：
事情发生了变化，这次队伍的基准是第一位的格格，鸭子从左向左找比格格低的同学，一直到了第一位也没有找到，而老师没有动，因为他们已经相遇了：
这种情况下，找到的位置和基准位相同，意思是不需要做任何交换。于是格格归位了，她把分区分成了左右两个，左边是比她低的（为空），右边是比她高的（只有可可和乐乐，图图欢欢是上面几轮排好的，不在这轮排序范围内）。老师和鸭子站在了可可和乐乐的位置，并以可可为基准：
现在可可是基准 ，按上述的方法，还是鸭子先从右向左找第一个比可可低的，他不需要动；而老师向右找，与鸭子相遇也没找到比可可高的，他们同时站在了乐乐的位置上：
老规矩，基准元素要和找到的元素换位置，老师和鸭子站在了可可分成的左区间（只有一个乐乐）的位置上：
当区间只有一个元素的时候，无法再进行分区了，所以我们不用再找基准元素，它们的位置都相当于排好了：
回顾一下，每一轮以当前分区的第一位为基准元素（刚开始分区就是整个列表），然后分别从当前分区左中两端出发，从右端出发寻找第一个比基准元素小的元素，而从左端出发寻找第一个比基准元素大的元素，如果它们碰头了，这个位置是分区点，就把分区点的元素与基准元素互换；如果没有碰头，把刚刚找到的两个元素互换（我们上面的例子没出现这种情况，老师和鸭子都是直接碰头了），然后继续向左向右找，直至老师和鸭子碰头找到基准点，执行基准元素和基准点位置的元素互换操作。这样完成第一轮。
接下来的递归调用，就是把第一轮基准元素分隔原始列表形成的左分区、右分区用上述方法继续递归排序，直到各个分区不能再分（比如是空或只有一个元素为止）。
编程
快速排序的代码要复杂一些，我们定义了基准、基准位、左、右变量，刚开始的时候调用从1到数组项目数作为左右两端进行第一轮排序；在每轮排序中先寻找分区点（从左右两个方向分别逼近），找到之后交换基准元素与基准点位置元素互换，然后基准点分成的左右分区进行递归的快速排序调用：
你可以找几张带数字的卡牌自己描述一下上述过程，以便真正理解快速排序。
程序执行效果：
总结
到此，四种排序算法全部讲完，由于快速排序牵涉递归调用，我们就不再计算它的调用次数了，有点复杂。我们将在下一节的内容呢，再对上面几节讲到的排序算法进行综合评比测试，看看谁才是真正的排序冠军。
