制作不易，三连支持一下吧！！！

前两篇博客介绍了插入和选择排序，这篇博客我们将会介绍一个非常重要的排序算法——快速排序，它的实践价值要大远远于前两种排序。

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

动图展示如下：

这里再简单解释一下：

我们一般选取最左或最后边的值作为基准值（key），如果我们选择最左边的值为key，且我们要排成升序序列，那我们就让最右边先走（为了保证相遇位置的值一定比key小），找到比key小的位置停下来，然后左边再走，找到比key大的位置停下来，两者交换，循环上述操作，直至left和right相遇，再将相遇位置的值与key交换，这样就完成了单趟排序。

key位置的元素就排到了合适的位置。 

之后递归左右区间即可。

代码实现：

挖坑法是在hoare大佬版本的基础上为了好让大家理解而改进的一种思路，因为hoare版本如果以最左边的值做key，则必须要让右边先走，让最右边的值做key，则必须要让左边先走，否则会出现错误。 而如果是挖坑法，则无需关心这个问题。大家自然而然会按正确的方式实现。

动图演示如下: 

通俗一点解释：

我们将key位置的值保存下来，将那个位置视为一个坑位，右边先走，找到比key小的值就填到坑位中，坑位就更新到新的位置，左边再找大，再更新坑位的位置，直到left和right相遇，将原来key中的值放到坑位中就完成了单趟排序。

这样我们就避免了考虑哪边先走的问题，因为如果左边为坑，我们自然而然的就会让右边先走！

代码实现如下：

前后指针版本是这三种方法里面最值得推荐的一种，因为它实现出来非常的简单。

动图演示如下：

 简单解释一下：

定义两个指针prev和cur，如果啊a[cur]比key位置的值小，就让prev前进一步，并交换cur和prev位置的值，如果a[cur]比key位置的值大，就只++cur。

最后，prev和cur之间的值就是整个序列中比key位置的值大的值。prev之前的值就是比key位置的值小的值。

代码实现如下： 

之前的三种方法虽然思路略有不同，但本质都是分治递归的思想，这种思想比较容易理解，但是递归深度过深可能会导致栈溢出，因此，我们必须掌握非递归的实现，以适用于所有场景。 

从递归改成非递归的方法一般有两种：

• 直接改成循环——例如：斐波那契数列
• 借助于栈或队列的结构。

我们这里就是要借助于栈的数据结构。

整体思路就是压栈，每次取出一个区间进行单趟排序，然后再入栈，如果区间不存在或只有一个元素就不再入栈，直至栈为空时，排序就完成了。 

代码实现如下： 

从分治的角度看，快速排序是一种二叉树结构的排序，有些大佬觉得最后几层占了整个递归次数的百分之八九十，消耗有些大，所以当区间长度小于一定数量（一般是10）时就直接用直接插入排序就好了。

也就是说最小子问题不再是区间不存在或只有一个值了，而是区间长度小于10.

快速排序在序列有序时，效率是不高的，时间复杂度不再是O（N*logN），而是O（N^2）。

为了尽量避免出现最坏的情况，我们可以采用三数取中的方法，防止key是最大或最小的值。

以hoare版本为例，加入三数取中后，就是这样：