三路快速排序是雙路快速排序的進一步改進版本，三路排序算法把排序的資料分為三部分，分别為小于 v，等于 v，大于 v，v 為标定值，這樣三部分的資料中，等于 v 的資料在下次遞歸中不再需要排序，小于 v 和大于 v 的資料也不會出現某一個特别多的情況），通過此方式三路快速排序算法的性能更優。
時間和空間複雜度同随機化快速排序。
三路快速排序算法是使用三路劃分政策對數組進行劃分，對處理大量重複元素的數組非常有效提高快速排序的過程。它添加處理等于劃分元素值的邏輯，将所有等于劃分元素的值集中在一起。
三、過程圖示
我們分三種情況進行讨論 partiton 過程，i 表示周遊的目前索引位置：
（1）目前處理的元素 e=V，元素 e 直接納入藍色區間，同時i向後移一位。
（2）目前處理元素 e<v，e 和等于 V 區間的第一個位置數值進行交換，同時索引 lt 和 i 都向後移動一位
（3）目前處理元素 e>v，e 和 gt-1 索引位置的數值進行交換，同時 gt 索引向前移動一位。
最後當 i=gt 時，結束周遊，同時需要把 v 和索引 lt 指向的數值進行交換，這樣這個排序過程就完成了，然後對 <V 和 >V 的數組部分用同樣的方法再進行遞歸排序。
源碼包下載下傳：Download
package runoob;
/**
* 三路快速排序
*/
public class QuickSort3Ways {
//核心代碼---開始
// 遞歸使用快速排序,對arr[l...r]的範圍進行排序
private static void sort(Comparable[] arr, int l, int r){
if (l >= r) {
return;
}
// 随機在arr[l...r]的範圍中, 選擇一個數值作為标定點pivot
swap( arr, l, (int)(Math.random()*(r-l+1)) + l );
Comparable v = arr[l];
int lt = l; // arr[l+1...lt] < v
int gt = r + 1; // arr[gt...r] > v
int i = l+1; // arr[lt+1...i) == v
while( i < gt ){
if( arr[i].compareTo(v) < 0 ){
swap( arr, i, lt+1);
i ++;
lt ++;
}
else if( arr[i].compareTo(v) > 0 ){
swap( arr, i, gt-1);
gt --;
else{ // arr[i] == v
swap( arr, l, lt );
sort(arr, l, lt-1);
sort(arr, gt, r);
}
//核心代碼---結束
public static void sort(Comparable[] arr){
int n = arr.length;
sort(arr, 0, n-1);
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
// 測試 QuickSort3Ways
public static void main(String[] args) {
// 三路快速排序算法也是一個O(nlogn)複雜度的算法
// 可以在1秒之内輕松處理100萬數量級的資料
int N = 1000000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
sort(arr);
SortTestHelper.printArray(arr);
}