面试重点---快速排序

快排单趟

快速排序是我们面试中的重点，这个知识点也很抽象，需要我们很好的掌握，而且快速排序的代码也是非常重要，需要我们懂了还不行，必须要手撕代码，学的透彻。

在研究快速排序之前，我们首先看一个动画，先自己看几遍，看能不能看懂它在干什么。

这个动画就是我们快排的总体过程，如果你没有看懂也不用急，我用文字来帮助你理解这个过程。我们定义了一个key，他是6这个数字，然后L和R分别在数组的最左边和最右边，首先让R先走，让R找到比key小的数，第一个找的是5，然后不动，再让L向右移动，找到比key大的数，不动，将L和R交换，再继续移动，直到L和R相遇，相遇之后，与key交换，就达到了下面这幅图的效果。

 仔细观察可以发现，我们的6到达了它应该到达的位置，并且，6的左边都比6小，6的右边都比6大。这是我们快排的单趟过程。

快排的全过程

上面我们研究了快排的单趟，而我们怎么将它的单趟结合起来，让整个数组的顺序都排好呢？下面我们来看一组图，演示一下快排的全过程。

这就是快速排序的全过程，是不是很熟悉，就是我们之前二叉树里面接触的递归，有没有想起来呢？

这就是我们实现快排的过程。

key的选取

首先我们思考一个问题，当我们的数组是有序的，那么，效率会发生什么变化呢？

是不是就像上图一样，我们这个时间复杂度就从N*logN变成了N^2呢？效率瞬间就下降了一个层次，为了避免这样的情况发生，我们思考的解决方案就是将我们选取的k不固定的选在第一个，这样就避免了上图的样子，效率也会蹭蹭往上涨，那么，k 用什么办法选呢？

第一种方法就是随机选取，第二种方法就是取中间值，我个人认为还是第二种科学一点，第二种方法的k值是可控的，科学的，不是随机生成的。 

全部代码见下篇文章。