三路快速排序法Quick Sort 3 Ways对具有大量重复键值的数组进行排序时，前篇使用了双路快速排序进行优化，进而使用了经典的实现方式——三路快速排序法。
三路快速排序的思想其实很简单。 我们到目前为止实现的快速排序是将整个排列分为2个部分，“=v”的部分和“=v”的部分。 三路快速排序将整个数组分为三个部分：“v”部分、“=v”部分和“v”部分。 可以想象，这样分割成三个部分后，在递归过程中，不对“=v”的部分进行管理，而只是对“v”的部分和“v”的部分继续递归相同的快速排序。
那么，我们来看看以下3个快速排序的具体想法吧。
在下图中，我们处理了整个数组。 在处理过程中的某个时刻，情况可能如下
整个排列分为三个部分。
关于“v”的部分，使用了“lt”的索引，指向“v”部分中最后一个元素的地址arr[l 1.lt]v。
关于“v”的部分，使用了“gt”的索引，指向“v”部分的第一个元素的地址arr[gt.r]v。
如果当前处理中的要素是位置“I”的要素，则arr[lt 1.i-1]=v。
现在处理’ I ‘这个位置的要素。 根据情况进行研究。 有几种这样的可能性。
第一种可能性是最简单的情况，目前正在处理的元素’ e==v ‘，该元素’ e ‘直接并入’=v ‘的部分，并且对应的’ I ‘处理下一个元素。
在第二种情况下，当前处理的元素’ ev ‘只交换当前元素’ e ‘和’=v ‘部分的第一个元素。 在这种情况下，“e”是“v”部分的最后一个元素，橙色的“v”部分增加了一个元素，相应的“lt”索引必须向后移动一个位置。 然后，继续’ I ‘处理下一个元素。
在第三种情况下，当前处理的元素’ ev ‘只是交换元素’ e ‘和” gt-1 “位置的元素。 在这种情况下，元素’ e ‘是’ v ‘部分的第一个元素，而紫色’ v ‘对于一个元素，相应的’ gt ‘索引必须前移一个位置。 但是，索引’ I ‘指向不需要移动且仍然未处理的元素。 此未处理的元素已从“gt-1”位置替换。
讨论了这三种情况。 基于此逻辑，处理完整个数组后，整个数组应该如下图所示。 分为三个部分‘v’部分、‘=v’部分和‘v’部分，同时索引‘lt’指的是‘v’部分的最后一个元素，索引‘gt’指的是‘v’部分的第一个元素。 索引’ I ‘和索引’ gt ‘重叠时，是对整个数组的操作完成时
最后，只需交换“l”位置的元素和“lt”位置的元素，“v”就是“=v”部分的第一个元素。
此时，整个数组如上图所示，接下来只需对“v”部分和“v”部分进行递归快速排序。 “=v”的部分已经放置在整个数组的适当部分，不需要任何处理。 这种方式的优点是不需要重复操作等于’ v ‘的大量元素，不需要一次考虑很多元素。 如果’=v ‘部分的元素非常多，这种优化就会非常明显。
另外，如果在交换了“l”位置的要素和“lt”位置的要素之后不再维持“lt”的索引，则对应的“v”部分为arr[l.lt-1]v，“v”部分为arr[gt.r]v 这种边界的处理，必须特别注意。
以上3路快速排序的想法已经介绍完毕。 具体的代码实现如下所示。
package com.zeng.sort； /** *三路快速排序* @ authors ks * */public class quick sort3ways {/* * *针对数组arr排序* @ param arr */public void quick sort3wart 对数组区间arr[left.right]进行排序，将其关闭在区间之前*首先使用partition过程将arr[left.right]设置为v，==v， 先分为v三个部分再递归地针对v，v的两个部分分别排序* @ param arr * @ param left * @ param right */privatevoidquicksort3ways (int [ ] arr，)
lt;= 15){insertionSort(arr, left, right);return;}//partition过程//优化：随机化快速//随机取一个元素和第一个元素交换位置，作为标记元素swap(arr, left, (int)(Math.random() * (right – left + 1) + left));int v = arr[left];//定义并初始化下标索引，使得三部分区间为空int lt = left; //arr[left+1…lt] < vint gt = right + 1; //arr[gt…right] > vint i = left + 1; //arr[lt + 1, i) == vwhile(i < gt){if(arr[i] < v){swap(arr, i, lt + 1);lt ++;i ++;}else if(arr[i] > v){swap(arr, gt – 1, i);gt –;}else{ //arr[i] == vi ++;}}swap(arr, left, lt);quickSort3Ways(arr, left, lt – 1); //继续对 <v 部分进行快速排序quickSort3Ways(arr, gt, right); //继续对 >v 部分进行快速排序}/** * 插入排序算法，对数组中子数组[left, right]进行排序. * @param arr * @param left * @param right */private void insertionSort(int[] arr, int left, int right){for(int i = left + 1; i <= right; i ++){int e = arr[i];int j = i;for(; j > left && arr[j – 1] > e; j –){arr[j] = arr[j – 1];}arr[j] = e;}}/** * 交换数组中两个元素的值 * @param arr * @param i * @param j */private void swap(int[] arr, int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}
优化后的测试结果如下：
对一百万条随机的数据进行排序
MergeSort: 1000000 true 211ms
QuickSort: 1000000 true 97ms
QuickSort2: 1000000 true 106ms
QuickSort3: 1000000 true 129ms
对一百万条近乎有序的数据进行排序
MergeSort: 1000000 true 44ms
QuickSort: 1000000 true 38ms
QuickSort2: 1000000 true 32ms
QuickSort3: 1000000 true 68ms
对一百万条拥有大量重复元素的数据进行排序
MergeSort: 1000000 true 124ms
QuickSort: 1000000 true 31766ms
QuickSort2: 1000000 true 49ms
QuickSort3: 1000000 true 17ms
从上面的测试结果可以看出，对于拥有大量重复元素的数组进行排序时，三路快速排序算法比二路快速排序算法效率要比双路快速排序和归并排序的效率高很多，这就是三路快速排序的重要优势。
在其他两个测试情况中，三路快速排序要微微的慢与双路快速排序，但是整体上依然是在一个数量级上的，这点差距是完全可以接受的，并且都是好于归并排序的，这也是快速排序叫快速的原因。虽然时间复杂度都是O(nlogn)级别的排序算法，但是快速排序在性能上是要比归并排序要好的。
另外双路快速排序和三路快速排序各有优劣，一般系统级别的排序都会选着三路快速排序，就是因为三路快速排序在处理存在有重复键值的时候优势非常大，再处理没有重复键值数组的时候，它的速度也可以得到保证。
我们分析和学习快速排序的过程，从一点一点快速排序基础的思想，到遇到一个问题，换一种方式，解救一个问题，这个整个思路是非常重要的。如果在面试过程中，面试官让你谈谈对快速排序的看法，大家能够按住这个时候一点一点的介绍和改进快速排序算法，对每一种方式它们的得失有一个很好的分析，说能你对快速排序的理解已经非常深刻了，同时也会给面试官留下非常深刻的影响。
这里我们对快速排序的分析就告一段落了，虽然快速排序算法还有一些其他优化策略，这里就不一一列举出来，我们分析的这几点就是比较常见的优化策略。
