我们知道排序有很多种，常见的如希尔排序，插入排序，选择排序，堆排序等等，而快速排序也是排序家族中的一员。因为其在大多数情况下有着优秀的综合性能，快速排序的快速也算是实至名归，接下来就为大家讲解快速排序的思想与实现。
快速排序通过多次比较与交换来完成排序。而这个过程又被分为了多次重复单趟排序，接下来我们先从每一趟的排序讲起。
快速排序的单趟排序思想是：
在一个无序数组中取一个数key，每一趟排序的最终目的是：让key的左边的所有数小于key，key的右边都大于key（假设排升序）。
先不考虑这一步怎么实现，我们接着往下看。
以下面的数组为例，可以观察到的是，在完成单趟排序后，无论key的左边和右边是否有序，key都来到了它在整个数组有序时应该来到的位置，也就是这个数组的第四个位置。所以对于key来说，它已经被排好序了。
接下来，我们对key的左右区间进行单趟排序，可以预见的是，每次排序都固定好了一个数。而当我们对细分的左右区间进行单趟排序，最终整个数组都会化为有序。
下面是快速排序的整体框架：
这个方法取自于快排的发明者本人
其单趟排序的思路是：取区间中最左或最右边的元素为key，定义两个变量，这里假设是p和q，q从区间的最右边向左走，找到比key小的元素就停下。p从最左边向右走，找到比key大的元素就停下。然后交换p和q所指向的元素。下面是p与q单次交换的示意图：
重复上面的过程，直到pq相遇，交换key和pq相遇位置的元素。
这样，单趟排序就完成了。
可以看出，经过pq的不断交换，比key小的值换到了左边，比key大的值换到了右边。最终将key换至中间就完成了单趟排序。
这里的key可以取最左边的值，此时必须让最右边的q先走。因为在最后一个循环时，若是q向左走，撞上了p，p此时指向的元素是上一个循环结束后交换的值，这个值比key小。若是p向右走，撞上了q，那么在这个循环，q先走，并且q停下来了，所以q的位置是一个比key小的值。若让左边的p先走，则可能在最后交换key的步骤将一个大于key的值交换到最左边。具体原因不进行分析。
若要取最右边的值做key，则要让最左边的p先走，原因同上。
下面是代码实现：
这个方法单趟排序的思路是：取最左或最右边的元素为key，假设把这个位置“挖空”，让最右边的q向左走，直到遇到比key小的数，将其放到key的位置，自己的位置变“空”。直到pq相遇，那么这个位置就是最终的坑位，再将key填入这个坑位，就完成了一趟排序。
单趟交换示意图：
代码实现：
取最左边的数为key，定义两个快慢指针，都从key的下一位往右走，fast每走一步判断一下它指向的元素是否小于key，若小于则交换fast和slow位置的元素，并且让slow向前走，直到fast走到底，结束循环。最后让slow和key位置的值交换。再返回key的位置。
代码实现：
注意这里的slow初始位置和fast不同，因为交换元素时要使用前置++，若使用后置++则要改写为下面的写法。因为如果每次交换都采用后置++，最终slow的位置会在期望位置的下一位，所以与key交换时要回退一位。而上面的更简洁，故采用上面的写法。
我们知道快速排序的思路就是将区间用key划分为左右两个小区间，再进行递归。
要用非递归的方式实现快速排序，我们可以借助栈来完成。
对于一个区间，我们可以化为栈中的两个元素进行表示：
比如表示[0,4]区间，我们可以先入0再入4。在取出时，我们先取到4，再取到0，这样就算是取出区间了（要注意出栈顺序与入栈顺序相反）。
具体的实现思路是：
先将整个区间入栈，然后进入循环体：取出区间，进行一趟快速排序，得到左右区间，再将左右区间入栈。直到整个栈为空就退出循环。
这样在每次循环中，就取出了要排序的区间，再将左右区间入栈，在之后的循环中排序，直到所有区间都被拆分排序到不可再拆分。
代码实现：
面对完全有序的数组，快速排序每趟排序后，key的位置都在边缘，每层递归都只能固定一个数，时间复杂度变成了O(N^2)。
面对这种情况，我们可以在取key时动手脚。每次取key我们不再只取最左或最右的值。而是对比最左、最右、中间的三个元素，取三个元素中，值在另外两者中间的元素作为key。这样，就打乱了有序数组，大大加快了快速排序在面对这种情况时的速度。