封裝成類：
package com.roc.algorithms.sort;
/**
* 三向切分快速排序
* 適合有較多重復(fù)元素的排序算法
*
* @author imroc
*/
public class ThreeWayQuickSort {
public static void sort(int[] a) {
sort(a, 0, a.length - 1);
}
//在lt之前的(lo~lt-1)都小于中間值
//在gt之前的(gt+1~hi)都大于中間值
//在lt~i-1的都等于中間值
//在i~gt的都還不確定（最終i會大于gt溪掀，即不確定的將不復(fù)存在）
private static void sort(int[] a, int lo, int hi) {
if (lo >= hi) {
return;
}
int v = a[lo], lt = lo, i = lo + 1, gt = hi;
while (i <= gt) {
if (a[i] < v) {
swap(a, i++, lt++);
} else if (a[i] > v) {
swap(a, i, gt--);
} else {
i++;
}
}
sort(a, lo, lt - 1);
sort(a, gt + 1, hi);
}
private static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
測試：
int[] a = {9, 0, 6, 5, 8, 2, 1, 7, 4, 3};
System.out.println(Arrays.toString(a));
ThreeWayQuickSort.sort(a);
System.out.println(Arrays.toString(a));
輸出：
[9, 0, 6, 5, 8, 2, 1, 7, 4, 3]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
