快速排序的思想

快速排序的核心思想在于分治法。挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。然后递归对基准元素两边的元素继续依次排序。

因此快速排序的由3个步骤组成

1.挑选一个基准元素

2.将基准元素安置到准确的位置

3.将基准元素两侧的数重复1，2步骤递归排序

下面针对各个步骤进行分析

挑选基准元素

快速排序的时间复杂度会受到基准元素的影响，在理想的情况的下，每一轮排序后(除却最后一轮)，基准元素两侧都应该是非空的，即算法复杂度为O(nlogn)。但是因为无法保证这一点，因此在一定情况下，快速排序的时间复杂度可能退化为O(n^2)。一般情况下直接选择左侧第一个数作为基准元素即可。

按照基准元素多轮排序(理想情况)

按照基准元素多轮排序(最差情况)

找到基准元素准确位置

找到基准元素位置，我们常用的有两种方法，挖坑法与指针交换法。

挖坑法

指针交换法

可以看到，挖坑法和指针交换法的区别，就在于右侧遍历的时候遇到不符合顺序的元素时的处理方式，挖坑法会即刻调整，指针交换法会留待左侧遇到不符合顺序的元素时进行交换。

为什么要从右侧开始处理

直接说结论，如果基准元素为左侧第一个，则需要从右侧开始处理。

以上图为例，正序排序，先左侧的话，会到9停下，换到右侧也会到9停下，此时因为左右侧相等，将基准元素6放置到9的位置，此时排序就错乱了。交换完成并不能保证所有左边的值都小于基准数，因此当key设置在左侧时应当从右开始向左查找，如果想先从左往右查找，只需把基准元素设置在右侧即可。

递归转非递归

快速排序使用到了分治理法的思想，对于分治法，我们最常使用的处理方法即递归。但是递归会到栈深度的加深，因此我们可以使用非递归的方式。原理也十分简单，使用堆栈保存递归所想保存的状态即可

代码示例

指针交换法

填坑法

递归与非递归调用