从做到右遍历数组一次，维护一个指针lt使得a[low…lt-1]中的元素都小于v，一个指针gt使得a[gt+1…high]中的元素都大于 v，一个指针i使得a[lt…i-1]中的元素都等于v，a[i…gt]中的元素都还为确定，一开始i和lo相等。
使得i递增，对于a[i]：
a[i]小于v，将a[lt]和a[i]交换，将lt和i加一
a[i]大于v，将a[gt]和a[i]交换，将gt减一
a[i]等于v，将i加一
最后使数组呈现下图中的情况：
实现代码：
public void quickSort3Way(Integer[] a,Integer low,Integer high) {
if(low >= high)
return;
Integer lt = low;
Integer i = low + 1;
Integer gt = high;
while(i<=gt) {
if(a[i] < a[lt]) {
change(a,i,lt);
i++;
lt++;
} else if(a[i] > a[lt]) {
change(a,i,gt);
//这里不能使用i--，因为交换a[gt]和a[i]后，现在的a[i]并没有确定位置，如果使用i++,就将跳过交换后该元素的排序
gt--;
} else {
i++;
}
print("a",a);
}
quickSort3Way(a,low,lt-1);
quickSort3Way(a,gt+1,high);
}
运行结果：
init: [2 ,1 ,5 ,9 ,0 ,6 ,8 ,7 ,3]
a: [1 ,2 ,5 ,9 ,0 ,6 ,8 ,7 ,3]
a: [1 ,2 ,3 ,9 ,0 ,6 ,8 ,7 ,5]
a: [1 ,2 ,7 ,9 ,0 ,6 ,8 ,3 ,5]
a: [1 ,2 ,8 ,9 ,0 ,6 ,7 ,3 ,5]
a: [1 ,2 ,6 ,9 ,0 ,8 ,7 ,3 ,5]
a: [1 ,2 ,0 ,9 ,6 ,8 ,7 ,3 ,5]
a: [1 ,0 ,2 ,9 ,6 ,8 ,7 ,3 ,5]
a: [1 ,0 ,2 ,9 ,6 ,8 ,7 ,3 ,5]
a: [0 ,1 ,2 ,9 ,6 ,8 ,7 ,3 ,5]
a: [0 ,1 ,2 ,6 ,9 ,8 ,7 ,3 ,5]
a: [0 ,1 ,2 ,6 ,8 ,9 ,7 ,3 ,5]
a: [0 ,1 ,2 ,6 ,8 ,7 ,9 ,3 ,5]
a: [0 ,1 ,2 ,6 ,8 ,7 ,3 ,9 ,5]
a: [0 ,1 ,2 ,6 ,8 ,7 ,3 ,5 ,9]
a: [0 ,1 ,2 ,6 ,5 ,7 ,3 ,8 ,9]
a: [0 ,1 ,2 ,5 ,6 ,7 ,3 ,8 ,9]
a: [0 ,1 ,2 ,5 ,6 ,3 ,7 ,8 ,9]
a: [0 ,1 ,2 ,5 ,3 ,6 ,7 ,8 ,9]
a: [0 ,1 ,2 ,3 ,5 ,6 ,7 ,8 ,9]
a: [0 ,1 ,2 ,3 ,5 ,6 ,7 ,8 ,9]
result: [0 ,1 ,2 ,3 ,5 ,6 ,7 ,8 ,9]