1. 写在前面
本文将从0开始编写快速排序的代码。希望阅读者最好要自己作图，思考执行过程，自己动手实现代码，如果默写代码，甚至背诵代码，就是本末倒置了。
2. 文章结构
主要讲解一路快排，二路快排和三路快排的实现过程，作图略。对于快排的复杂度以及其它背景知识可自行学习。
3. 关于快排
过程：选择一个参考点，以从小到大排序为例，那么在一次快排之后，在参考点左侧的数据都比参考点小，在参考点右侧的数据都比参考点大，每次快排之后的参考点也就是分割点。这个过程如何做到呢?我们选择一个参考点，将它置于整个数组的左端(右端)，在扫描的过程中，把比参考点大的数据放在参考点右侧，比参考点小的数据放在参考点左侧。
思路：由于快排是典型的分治算法，那就与归并排序的思路相同，我们将采用递归的方法解决问题，当整个问题的所有子问题都被解决时，原问题也就得到了解决。
解决问题的关键：找出快速排序算法的分割点(partition),用以将原问题划分成若干子问题,再对每个子问题分别使用快速排序，最后解决问题，与归并排序不同的是，它并不是每次都将数组分割成大小相同的两个部分，一方面，参考点的选择会极大影响算法的效率，另一方面，这也为我们的优化提供了可能。
参考点的选择：对于参考点的选择是随机的，只是在二路快排中参考点所处的位置对开始扫描的方向有些约束，这是由于排序规则(从小到大排序还是从大到小排序)限定的,一般情况下，我们选择数组第一个元素为参考点，若要选择数组最后一个元素为参考点，则要注意二路快排代码中每次快排优先扫描的方向。示例代码均采用从小到大的顺序进行编写
4.一路快排
首先，选取数组第一个元素作为参考点，此外，我们需要几个指针(数组下标,下同)，指针lo和hi，表示每个子数组的低位和高位,指针i指向当前正在被考察的元素，显然,对于i有i∈[lo,hi]，由3我们知道，在每次快排的过程中，我们需要确定分割点的位置，我们设这个指针为j。很显然，此时数组被分割成三个部分：从lo到j，当前正在考察的元素i，从i+1到hi。当正在考察的元素比参考点小时，我们将它与j+1位置的元素交换位置。因为：j表示的是参考点的位置，由3我们知道j+1位置的元素一定是大于参考点的，经过这次交换,有一个比参考点小的元素跑到参考点后一个位置，此时，只需要对参考点的指针+1即可，这相当于小于参考点的区域增加了一个元素，而对于比参考点大的元素，则跑到了数组右端，满足题设。随着数组的遍历的进行，参考点j表示的下标也不断更新，当整个数组遍历完毕时，指针j指向的就是参考点的位置，最后，我们交换参考点的数据与j指向的数据，一次快排就完成了。
5 二路快排
为什么需要二路快排? 因为在处理近乎有序的数组时，一路快排的速度会大大降低(因为一路快排的分割特点，导致分割有序数组时将会产生高度不平衡的二叉树结构，使得算法的时间复杂度退化成O(N2))
处理过程 二路快排是指有两个指针，我们设它们分别为left和right，从数组两端分别开始扫描，left指针从左向右寻找比参考点大的元素，right指针从右想左寻找比参考点小的元素，当两个指针出现重叠或交叉时，参考点的位置就确定了。在这个过程中,如果左右指针都找到了合适的元素而没有出现交叉，那么久交换左右指针元素的位置，如果出现了交叉，就交换先开始扫描方向的指针与参考点的位置。
注意 两个指针哪个先进行扫描? 答案是从参考点的对立方向开始扫描。
我们先来看看，如果从参考点同向扫描会出现什么情况:选取数组第一个元素为参考点，此时left指针从lo+1开始扫描寻找比参考点大的元素，如果此时参考点的元素就是数组最小的元素，那么left指针立刻找到一个比参考点大的元素并且停下来，然后right指针开始扫描，直到参考点的位置停下来，此时交换left指针(指向比参考点大的元素)和参考点(最小值)的位置，出现了参考点左侧元素比参考点大的情况，不合题意。选择对立方向开始扫描，不管左指针在与right指针碰撞时能否找到比参考点大的元素，right指针都已经找到了比参考点小的元素，在它们碰撞时(left=right)交换left与参考点的值，则不会出现违背题意的情况。
6 三路快排
为什么需要三路快排，二路快排已经能满足需要了，可是由于它的分割方法，导致它在处理含有大量重复元素的数组时，仍然将这些数放置在数组的一端(大于等于参考数或小于等于参考数)，由此一来，还是会产生高度不平衡的二叉树。三路快排便应运而生了。
处理过程 三路快排将数组分割成三个部分:即 小于参考点的，等于参考点的，大与参考点的。处理思想和一路快排类似，只是对等于参考点的元素不做交换处理，提高了效率，具体过程请读者根据一路快排的过程进行分析，下面给出代码。
7 算法优化
我们知道在处理小数组时，插入排序比快速排序更快，那么我们就可以在数组规模较小时使用插入排序来代替快速排序，而不是无视数组规模，在递归调用的过程中,全部调用快速排序算法。