引言：众所周知，快速排序算法是基于分治策略的一个排序算法，基本的算法在数据结构或算法设计与分析中都有讲解，本文不再赘述。本文主要总结的是快速排序的优化过程，即从一个基本的快速排序如何根据其中的缺陷一步一步优化来的。以下共有四个快排算法(qSort1、qSort2、qSort3、qSort4)依次由浅入深讨论。（动图源于网络）

运行结果如下：

由此可以发现第一个问题：如果是输入的是有序数组，则在划分基准上每次都会取边缘元素为划分基准(eg.1,2.3,4,5,6)，致使快速排序最坏情况下时间复杂度由O(nlogn)降低至O(n²)。很不划算，有辱盛名。为解决有序数组下划分不均匀问题，而诞生了随机化优化，即在数组中随机选择一个元素和第一个元素交换位置，除此外后面算法程序和前面一样。

运行结果如下：

附插入排序代码：

通过随机化优化解决了上述的问题一，即可使取得的基准为边缘元素的几率（尤其是在输入有序数组的情况下）变得很低，但基础快排法还遗留了另一个问题，也就是第二个问题：即使取得了合适的基准，但如果与此基准相同的元素过多，则会出现划分的某一端过多/少的情况（eg.小于等于基准的元素集中在左侧，大于基准的元素集中在右侧，则若与基准相同的元素过多，则划分下左侧元素会远多于右侧元素数量）。为避免在与基准相同元素过多情况下，划分的某一端元素数量出现极端化，从而诞生了二路快排法。

运行结果同上。
之所以称为二路快排是因为其中是不同于前两个算法的双向扫描，即通过两个索引分别从左和右向中扫描。这样做的好处是等于基准的元素可以均匀的被划分在基准两侧而不是极端的全部在一侧。此举在具有相同元素过多的情况下性能会远比基础快排好。这样在最坏的情况下时间复杂度依旧是O(nlogn)。在此通过qSort2和qSort3的递进下我们分别解决了基础快排法遗留下的两个问题。
但是产生了二路快排法后，我们很容易发现，当出现相同元素过多的情况下，二路快排所做的只是将与基准相同的元素均匀的划分在基准两侧，与基准相同的元素还需要经历后续的划分，那为何不直接把与基准相同的元素全部集中到一起，然后直接划分除此之外的两部分呢？答案是肯定的！为此，诞生了三路快排法。

运行结果同上。
通过将与基准相同的元素聚集在一起的方式，使在相同元素较多的情况下划分次数大大减少，极大的提高快排整体的效率。

在此，我将前几个优化过程中的快排算法总结如下：
1.基础快排法：易出现划分时某一侧数量极端化。
2.随机化快排法(+插排)：在前者的基础上考虑极端化，但未考虑与基准相同元素过多时，相同元素全部被划分在某一侧的问题。
3.二路快排法：在前者的基础上通过双向扫描，使与基准相同的元素均匀被划分在两侧，在一定程度上减少划分次数。
4.三路快排法：在前者的基础上考虑相同元素聚集，根本的减少冗余元素划分，在重复元素很多的情况下能极大的减少划分次数。