當待排序元素序列中有大量的重復排序碼時，簡單的快速排序算法的效率將會降到非常之低。一種直接的想法就是將待排序列分成三個子序列：一部分是排序碼比基准元素排序碼小的；一部分是與基准元素排序碼等值的；一部分是比基准元素排序碼大的，如下圖所示：
圖1 快速排序的三路劃分
但是，如果我們直接據此思想去編寫實現算法的話，會讓我們面臨很大的困難。與基准元素等值的元素到底有多少？以及如何最快速有效地確定劃分的邊界？所以，完成這樣的三路劃分是非常困難的，甚至比兩路劃分過程更加復雜。
我們可以基於以下的思想實現三路劃分：在劃分的過程中，掃描時將遇到的左子序列中與基准元素排序碼等值的元素放到序列的最左邊，將遇到的右子序列中與基准元素排序碼等值的元素放到序列的最右邊。這樣，我們會得到如下所示的序列劃分圖：
圖2 三路劃分的實現方法
當兩個掃描指針相遇時，排序碼相等的元素的確切位置就知道了。然後我們只要將所有排序碼與基准元素等值的元素與掃描指針指向的元素開始依次交換，就可以得到三路劃分的結果了。
這個方法不僅有效地處理了待排序元素序列中的重復值問題，而且在沒有重復值時它也能保持算法原來的性能。其優點是：
第一，如果元素序列中沒有重復值，這個方法可以保持算法的效率，因為沒有額外的工作要做；
第二，在每次話劃分的過程中，都可以將與基准元素排序碼相等的元素分割出來，所有擁有相同排序碼值的元素不會參加多次劃分。
代碼
private void quickSort(int[] a, int left, int right) {
if (right <= left)
return;
/*
* 工作指針
* p指向序列左邊等於pivot元素的位置
* q指向序列右邊等於Pivot元素的位置
* i指向從左向右掃面時的元素
* j指向從右向左掃描時的元素
*/
int p, q, i, j;
int pivot;// 錨點
i = p = left;
j = q = right - 1;
/*
* 每次總是取序列最右邊的元素為錨點
*/
pivot = a[right];
while (true) {
/*
* 工作指針i從右向左不斷掃描，找小於或者等於錨點元素的元素
*/
while (i < right && a[i] <= pivot) {
/*
* 找到與錨點元素相等的元素將其交換到p所指示的位置
*/
if (a[i] == pivot) {
swap(a, i, p);
p++;
}
i++;
}
/*
* 工作指針j從左向右不斷掃描，找大於或者等於錨點元素的元素
*/
while (left <= j && a[j] >= pivot) {
/*
* 找到與錨點元素相等的元素將其交換到q所指示的位置
*/
if (a[j] == pivot) {
swap(a, j, q);
q--;
}
j--;
}
/*
* 如果兩個工作指針i j相遇則一趟遍歷結束
*/
if (i >= j)
break;
/*
* 將左邊大於pivot的元素與右邊小於pivot元素進行交換
*/
swap(a, i, j);
i++;
j--;
}
/*
* 因為工作指針i指向的是當前需要處理元素的下一個元素
* 故而需要退回到當前元素的實際位置，然後將等於pivot元素交換到序列中間
*/
i--;
p--;
while (p >= left) {
swap(a, i, p);
i--;
p--;
}
/*
* 因為工作指針j指向的是當前需要處理元素的上一個元素
* 故而需要退回到當前元素的實際位置，然後將等於pivot元素交換到序列中間
*/
j++;
q++;
while (q <= right) {
swap(a, j, q);
j++;
q++;
}
/*
* 遞歸遍歷左右子序列
*/
quickSort(a, left, i);
quickSort(a, j, right);
}
private void quick(int[] a) {
if (a.length > 0) {
quickSort(a, 0, a.length - 1);
}
}
private void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
